How do you solve Last Day Where You Can Still Cross on LeetCode?

Last Day Where You Can Still Cross (LeetCode #1970) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log d) time complexity and O(n) space complexity. Key insight: Binary search can significantly reduce the number of checks needed.

What is the brute force solution for Last Day Where You Can Still Cross?

The brute force approach for Last Day Where You Can Still Cross is Brute Force, with O(n²) time complexity and O(1) space complexity. We can simulate each day by flooding the cells and checking if there's a path from the top to the bottom. This approach is straightforward but inefficient as it checks every day individually. The optimal Optimal Solution approach improves this to O(n log d).

What are the interview tips for Last Day Where You Can Still Cross?

Explain your thought process clearly while coding. Consider edge cases, such as the smallest or largest matrices. Practice similar problems to get comfortable with BFS/DFS.

What are common mistakes when solving Last Day Where You Can Still Cross?

Not resetting the matrix for each day check. Confusing 0-based and 1-based indexing.

#1970

Last Day Where You Can Still Cross

Hard

ArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindMatrixBinary SearchGraph Traversal (BFS/DFS)

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log d)
Space	O(1)	O(n)

💡

Intuition

Time O(n log d)Space O(n)

We can use binary search to efficiently find the last day we can cross by checking if a path exists for a range of days. This reduces the number of checks we need to perform.

⚙️

Algorithm

5 steps

1Step 1: Initialize binary search bounds (left = 0, right = number of days).
2Step 2: For each mid-point, create a matrix and flood the cells up to that day.
3Step 3: Use BFS or DFS to check if a path exists from the top to the bottom.
4Step 4: If a path exists, move the left bound up; otherwise, move the right bound down.
5Step 5: Return the last successful day.

solution.py40 lines

1# Full working Python code
2from collections import deque
3
4def can_cross(matrix, row, col):
5    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
6    queue = deque()
7    for c in range(col):
8        if matrix[0][c] == 0:
9            queue.append((0, c))
10    visited = set(queue)
11
12    while queue:
13        r, c = queue.popleft()
14        if r == row - 1:
15            return True
16        for dr, dc in directions:
17            nr, nc = r + dr, c + dc
18            if 0 <= nr < row and 0 <= nc < col and (nr, nc) not in visited and matrix[nr][nc] == 0:
19                visited.add((nr, nc))
20                queue.append((nr, nc))
21    return False
22
23
24def last_day_to_cross(row, col, cells):
25    left, right = 0, len(cells) - 1
26    last_day = 0
27
28    while left <= right:
29        mid = (left + right) // 2
30        matrix = [[0] * col for _ in range(row)]
31        for i in range(mid + 1):
32            r, c = cells[i]
33            matrix[r - 1][c - 1] = 1
34        if can_cross(matrix, row, col):
35            last_day = mid + 1
36            left = mid + 1
37        else:
38            right = mid - 1
39
40    return last_day

ℹ

Complexity note: The time complexity is O(n log d) where n is the number of days and d is the number of cells. We perform a binary search on the days and for each day, we check the path using BFS.

1Binary search can significantly reduce the number of checks needed.
2Using BFS/DFS helps efficiently determine if a path exists.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.