#1970

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Last Day Where You Can Still Cross

Find the last day to walk from top to bottom in a flooded matrix by using binary search and graph traversal techniques.

array binary search depth first search breadth first search union find

Problem Statement

You are given a matrix with rows and columns where initially, all cells are land. Each day, a new cell gets flooded with water according to a list of coordinates. The goal is to find the last day when it is still possible to walk from the top row to the bottom row, using only the land cells. You can start from any land cell in the top row and walk to any land cell in the bottom row, moving up, down, left, or right.

The challenge involves determining this last day using an efficient algorithm. A key aspect of solving this problem is to search for the valid answer space. Binary search can help narrow down the possible days, while graph traversal techniques such as BFS or DFS can validate the existence of a path across flooded cells.

Examples

Example 1

Input: row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]

Output: 2

The above image depicts how the matrix changes each day starting from day 0. The last day where it is possible to cross from top to bottom is on day 2.

Example 2

Input: row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]

Output: 1

The above image depicts how the matrix changes each day starting from day 0. The last day where it is possible to cross from top to bottom is on day 1.

Example 3

Input: row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]

Output: 3

The above image depicts how the matrix changes each day starting from day 0. The last day where it is possible to cross from top to bottom is on day 3.

Constraints

2 <= row, col <= 2 * 104
4 <= row * col <= 2 * 104
cells.length == row * col
1 <= ri <= row
1 <= ci <= col
All the values of cells are unique.

Solution Approach

Binary Search on the Day

Binary search over the day values can be used to check for the last possible day when a valid path exists. By testing if a path exists on day X, we can adjust the search space until we find the last day where it's still possible to cross.

Breadth-First Search (BFS)

Once a day is chosen, BFS can be applied to explore the matrix and check if a path exists from the top to the bottom. BFS ensures that we explore all possible paths efficiently, given the constraints of the problem.

Depth-First Search (DFS)

Alternatively, DFS can be used to explore each path from top to bottom for a given day. While it may use more space compared to BFS, DFS can still be effective in validating the existence of a valid path in the flooded matrix.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used, but the binary search component will reduce the number of days checked, leading to a time complexity of O(log(row * col)). For each day, BFS or DFS would take O(row * col), resulting in an overall time complexity of O(log(row * col) * (row * col)) in the worst case. Space complexity is O(row * col) due to the space needed for BFS or DFS traversal.

What Interviewers Usually Probe

Candidate demonstrates an understanding of binary search and how to apply it to a range of possible answers.
Candidate applies BFS/DFS to verify paths through a grid, indicating solid knowledge of graph traversal algorithms.
Candidate identifies optimization opportunities through binary search, showing problem-solving skills in narrowing down search spaces.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the search space by not using binary search on the valid days.
Incorrect path validation by using inefficient graph traversal techniques or not accounting for the matrix's changing state over days.
Overcomplicating the solution with unnecessary checks or missing edge cases like when the matrix is fully flooded.

Follow-up variants

Use Union-Find to handle connectivity checks across the matrix during water flooding.
Apply dynamic programming or memoization to speed up the path search process for each day.
Solve the problem by iterating through all days and performing BFS/DFS for each day, though less optimal than binary search.

FAQ

How does binary search help in solving the Last Day Where You Can Still Cross problem?

Binary search allows us to optimize the search for the last possible day to cross the matrix, reducing the number of days we need to check.

Can I use DFS instead of BFS for the Last Day Where You Can Still Cross problem?

Yes, DFS can be used instead of BFS to explore paths through the matrix. Both methods work, but BFS may be more space-efficient in this case.

What happens if I don't use binary search to narrow down the days?

Without binary search, you'd need to check every single day for a valid path, resulting in much higher time complexity.

How can I ensure my BFS or DFS is efficient for large matrices?

You can ensure efficiency by optimizing the path validation process, using visited nodes and limiting the search space to only land cells.

What are the key graph algorithms used in the Last Day Where You Can Still Cross problem?

The key algorithms are BFS or DFS for path validation and binary search for narrowing down the possible days.

terminal

Solution

Solution 1: Binary Search + BFS

We note that if we can walk from the top row to the bottom row on day $k$, then for any $0 < k' < k$, we can also walk from the top row to the bottom row on day $k'$. This exhibits monotonicity, so we can use binary search to find the largest $k$ such that we can walk from the top row to the bottom row on day $k$.

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        def check(k: int) -> bool:
            g = [[0] * col for _ in range(row)]
            for i, j in cells[:k]:
                g[i - 1][j - 1] = 1
            q = [(0, j) for j in range(col) if g[0][j] == 0]
            for x, y in q:
                if x == row - 1:
                    return True
                for a, b in pairwise(dirs):
                    nx, ny = x + a, y + b
                    if 0 <= nx < row and 0 <= ny < col and g[nx][ny] == 0:
                        q.append((nx, ny))
                        g[nx][ny] = 1
            return False

        n = row * col
        l, r = 1, n
        dirs = (-1, 0, 1, 0, -1)
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

Solution 2: Union-Find

We can first initialize all land cells as $1$, then traverse the array $\textit{cells}$ in reverse order, turning each corresponding land cell into $0$ and merging it with the adjacent land cells (up, down, left, right). We also need to maintain two virtual nodes $s$ and $t$, representing the virtual nodes for the top row and the bottom row, respectively. If $s$ and $t$ are connected in the union-find set, it means we can walk from the top row to the bottom row on day $i$.

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        def check(k: int) -> bool:
            g = [[0] * col for _ in range(row)]
            for i, j in cells[:k]:
                g[i - 1][j - 1] = 1
            q = [(0, j) for j in range(col) if g[0][j] == 0]
            for x, y in q:
                if x == row - 1:
                    return True
                for a, b in pairwise(dirs):
                    nx, ny = x + a, y + b
                    if 0 <= nx < row and 0 <= ny < col and g[nx][ny] == 0:
                        q.append((nx, ny))
                        g[nx][ny] = 1
            return False

        n = row * col
        l, r = 1, n
        dirs = (-1, 0, 1, 0, -1)
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

Continue Practicing

#1631 path with minimum effort #1905 count sub islands #778 swim in rising water