LeetCode Solutions Blog

Last Day Where You Can Still Cross

Number: 2101

Difficulty: Hard

Paid? No

Companies: Google, Apple

Problem Description

Given a binary matrix of dimensions row x col with initially all cells as land (0), cells become water (1) day by day in the order provided by the array cells. The goal is to determine the last day on which there is still a valid path from any cell in the top row to any cell in the bottom row, moving only in the four cardinal directions and only through land cells.

Key Insights

The problem is essentially about determining connectivity on a grid that changes over time.
A binary search can be used on the day index because if it is possible to cross on a certain day, it may still be possible on earlier days.
For a given day, use BFS/DFS (or Union Find) on the grid to check if there is a path from the top row to the bottom row.
The grid state for each day is constructed by marking the cells flooded up to that day.
Alternatively, union-find can be used to maintain connectivity as cells switch from land to water.

Space and Time Complexity

Time Complexity: O((row * col) * log(row * col)) – binary search over the days with grid traversal each time. Space Complexity: O(row * col) – storing the grid and auxiliary data structures for BFS/DFS or union-find.

Solution

We use a binary search approach on the number of days. For a given day, we simulate the grid by marking the first mid cells as water. We then perform a BFS starting from all land cells in the top row, checking if we can reach any cell in the bottom row. By adjusting our binary search bounds based on the BFS result, we can efficiently find the last day where a path exists. The key trick here is to reverse the typical thinking: instead of trying every day sequentially, we leverage binary search to reduce the number of full grid checks.

Code Solutions

# Python solution using binary search and BFS

from collections import deque

def latestDayToCross(row, col, cells):
    # Directions for moving in the grid: up, down, left, right
    directions = [(0,1), (0,-1), (1,0), (-1,0)]
    
    # Check if it's possible to cross on a given day (0-indexed days in cells).
    def canCross(day):
        # Create grid representation (0: land, 1: water)
        grid = [[0] * col for _ in range(row)]
        # Mark water cells for the first 'day' days in cells list
        for i in range(day):
            r, c = cells[i]
            grid[r-1][c-1] = 1  # convert 1-based to 0-based index
            
        # Queue for BFS; add all land cells in the top row
        queue = deque()
        visited = [[False] * col for _ in range(row)]
        for j in range(col):
            if grid[0][j] == 0:
                queue.append((0, j))
                visited[0][j] = True

        # BFS traversal
        while queue:
            x, y = queue.popleft()
            # Check if reached bottom row
            if x == row - 1:
                return True
            # Visit neighbors
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < row and 0 <= ny < col and not visited[nx][ny] and grid[nx][ny] == 0:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
        return False

    # Binary search: find the last day where crossing is possible.
    lo, hi = 1, len(cells)  # days are counted as how many cells have been flooded.
    result = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if canCross(mid):
            result = mid  # mid day is possible, try for later day
            lo = mid + 1
        else:
            hi = mid - 1
    return result

# Example usage:
if __name__ == "__main__":
    row = 2
    col = 2
    cells = [[1,1],[2,1],[1,2],[2,2]]
    print(latestDayToCross(row, col, cells))  # Expected output: 2