Last Day Where You Can Still Cross

Hard

Amazon

1 view

Topics:

Binary SearchArraysGraphs

You are given a 1-based binary matrix where 0 represents land and 1 represents water. You are given integers row and col representing the number of rows and columns in the matrix, respectively.

Initially on day 0, the entire matrix is land. However, each day a new cell becomes flooded with water. You are given a 1-based 2D array cells, where cells[i] = [r_i, c_i] represents that on the i-th day, the cell on the r_i-th row and c_i-th column (1-based coordinates) will be covered with water (i.e., changed to 1).

You want to find the last day that it is possible to walk from the top to the bottom by only walking on land cells. You can start from any cell in the top row and end at any cell in the bottom row. You can only travel in the four cardinal directions (left, right, up, and down).

Return the last day where it is possible to walk from the top to the bottom by only walking on land cells.

Example 1:

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

Output: 2

Explanation: The last day where it is possible to cross from top to bottom is on day 2.

Example 2:

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

Explanation: The last day where it is possible to cross from top to bottom is on day 3.

Can you provide an efficient algorithm to solve this problem, considering the constraints where 2 <= row, col <= 2 * 10^4, 4 <= row * col <= 2 * 10^4, cells.length == row * col, and all the values of cells are unique?

Last Day Where You Can Still Cross

Hard

Amazon

1 view

Topics:

Binary SearchArraysGraphs

You are given a 1-based binary matrix where 0 represents land and 1 represents water. You are given integers row and col representing the number of rows and columns in the matrix, respectively.

Initially on day 0, the entire matrix is land. However, each day a new cell becomes flooded with water. You are given a 1-based 2D array cells, where cells[i] = [r_i, c_i] represents that on the i-th day, the cell on the r_i-th row and c_i-th column (1-based coordinates) will be covered with water (i.e., changed to 1).

You want to find the last day that it is possible to walk from the top to the bottom by only walking on land cells. You can start from any cell in the top row and end at any cell in the bottom row. You can only travel in the four cardinal directions (left, right, up, and down).

Return the last day where it is possible to walk from the top to the bottom by only walking on land cells.

Example 1:

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

Output: 2

Explanation: The last day where it is possible to cross from top to bottom is on day 2.

Example 2:

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

Explanation: The last day where it is possible to cross from top to bottom is on day 3.

Can you provide an efficient algorithm to solve this problem, considering the constraints where 2 <= row, col <= 2 * 10^4, 4 <= row * col <= 2 * 10^4, cells.length == row * col, and all the values of cells are unique?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid (number of rows and columns), and what is the range of these dimensions?
Are the cells in the grid represented by 0s and 1s, or some other representation, and what do the values signify?
Is the river guaranteed to flow from the top row to the bottom row, or can there be islands or disconnected regions of land that would prevent crossing even on the first day?
Are the `cells` coordinates 1-indexed or 0-indexed, and what does the order of coordinates in each `cell` represent (row, column) or (column, row)?
If it's impossible to cross on any day (even day 1), what should I return?

Brute Force Solution

Approach

The brute force approach involves checking every single day to see if a path exists from the top to the bottom of the grid without touching water. We simulate the submersion process day by day and for each day, we check if crossing is still possible.

Here's how the algorithm would work step-by-step:

Start by considering the first day.
Imagine the grid with only the cells from the first day submerged.
See if you can find a path from the top to the bottom of the grid that only steps on land cells (cells that are not submerged).
If a path exists, it means you can still cross on the first day. Now, repeat the process for the second day.
This time, imagine the grid with the cells from the first and second days submerged.
Again, check if there is a path from the top to the bottom using only land cells.
Keep repeating this process, one day at a time. For each day, check if there is a path to cross.
The last day where you can still find a path from top to bottom is your answer.

Code Implementation

def last_day_to_cross_brute_force(row, col, cells):
    last_possible_day = 0

    for day in range(1, len(cells) + 1):
        flooded_grid = [[0] * col for _ in range(row)]

        # Simulate flooding the grid up to the current day
        for current_day in range(day):
            current_row, current_col = cells[current_day][0] - 1, cells[current_day][1] - 1
            flooded_grid[current_row][current_col] = 1

        # Check if a path exists on the current day
        if can_cross(flooded_grid):
            last_possible_day = day

    return last_possible_day

def can_cross(flooded_grid):
    row = len(flooded_grid)
    col = len(flooded_grid[0])
    
    # Start from the top row and try to find a path to the bottom.
    for start_col in range(col):
        if flooded_grid[0][start_col] == 0:
            visited = [[False] * col for _ in range(row)]
            if depth_first_search(flooded_grid, 0, start_col, visited):
                return True
    return False

def depth_first_search(flooded_grid, current_row, current_col, visited):
    row = len(flooded_grid)
    col = len(flooded_grid[0])

    # If we reached the bottom row, we can cross
    if current_row == row - 1:
        return True
    
    # Check boundaries and if the cell is flooded or already visited.
    if current_row < 0 or current_row >= row or current_col < 0 or current_col >= col or \
            flooded_grid[current_row][current_col] == 1 or visited[current_row][current_col]:
        return False

    visited[current_row][current_col] = True

    # Explore all four possible directions.
    if depth_first_search(flooded_grid, current_row + 1, current_col, visited):
        return True
    if depth_first_search(flooded_grid, current_row - 1, current_col, visited):
        return True
    if depth_first_search(flooded_grid, current_row, current_col + 1, visited):
        return True
    if depth_first_search(flooded_grid, current_row, current_col - 1, visited):
        return True

    return False

Big(O) Analysis

Time Complexity

O(row * col * days) – The algorithm iterates through each day, potentially up to the total number of cells in the grid (days). For each day, it simulates the flooded grid and then performs a search (e.g., Depth First Search or Breadth First Search) to determine if a path exists from the top row to the bottom row. In the worst case, the search explores every cell in the grid which is row * col. Therefore, the overall time complexity is O(row * col * days), where 'row' is the number of rows, 'col' is the number of columns, and 'days' is the number of days to consider.

Space Complexity

O(M * N) – The brute force approach simulates the submersion process day by day and for each day, it needs to represent the grid. This grid representation, typically a 2D array, requires space proportional to the number of rows (M) times the number of columns (N) of the grid. Additionally, to check if a path exists, a depth-first search (DFS) or breadth-first search (BFS) might be employed, needing space to keep track of visited cells, which in the worst-case is also proportional to the grid size M * N. Therefore, the overall auxiliary space is O(M * N).

Optimal Solution

Approach

The best way to solve this is to use a technique that lets us efficiently check if we can cross the grid up to a certain day. Instead of checking each day individually, we will use a method to quickly narrow down the possibilities.

Here's how the algorithm would work step-by-step:

Think of this like searching for a number within a specific range, where you have an idea of the highest and lowest values.
Start with the middle day of the range and imagine filling in the grid up to that day with water.
Check if you can make a path from the top of the grid to the bottom without stepping on any water by using a technique that expands outwards from the top row. Think of water flowing downwards.
If a path exists on that day, we know that the last possible day must be later. If no path exists, the last possible day must be earlier. Update our search range accordingly.
Repeat the process, always checking the middle day of our remaining range, until we narrow down the answer to the single best day.

Code Implementation

def last_day_to_cross(row, col, cells):
    left = 1
    right = len(cells)

    def can_cross(day):
        grid = [[0] * col for _ in range(row)]
        for i in range(day):
            row_index, col_index = cells[i]
            grid[row_index - 1][col_index - 1] = 1

        queue = []
        visited = set()

        for column_index in range(col):
            if grid[0][column_index] == 0:
                queue.append((0, column_index))
                visited.add((0, column_index))

        while queue:
            current_row, current_col = queue.pop(0)

            if current_row == row - 1:
                return True

            directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

            for delta_row, delta_col in directions:
                new_row = current_row + delta_row
                new_col = current_col + delta_col

                if 0 <= new_row < row and 0 <= new_col < col and \
                   grid[new_row][new_col] == 0 and (new_row, new_col) not in visited:
                    queue.append((new_row, new_col))
                    visited.add((new_row, new_col))

        return False

    answer = 0
    while left <= right:
        middle = (left + right) // 2

        # Check if a path exists up to day 'middle'.
        if can_cross(middle):

            # If a path exists, try a later day
            answer = middle
            left = middle + 1

        # If no path exists, try an earlier day.
        else:
            right = middle - 1

    # Return the last day a path existed.
    return answer

Big(O) Analysis

Time Complexity

O(row * col * log(row * col)) – The algorithm performs a binary search over the days (possible values), where there are at most row * col days. For each day in the binary search, we perform a Depth-First Search (DFS) or Breadth-First Search (BFS) on the grid to check if a path exists from the top to the bottom, which takes O(row * col) time in the worst case. Therefore, the overall time complexity is O(row * col * log(row * col)).

Space Complexity

O(m * n) – The algorithm utilizes a data structure to keep track of visited locations within the grid of size m x n during the pathfinding check in step 3. This could be a boolean matrix of the same size as the input grid to avoid revisiting cells, or a queue used in a Breadth-First Search (BFS) or Depth-First Search (DFS) for pathfinding which in the worst-case scenario can contain all the cells in the grid. Therefore, the auxiliary space used is proportional to the dimensions of the grid, m and n, resulting in a space complexity of O(m * n).

Edge Cases

Case	How to Handle
Null or empty grid input (rows or cols = 0)	Return -1 immediately, as crossing is impossible with an invalid grid.
Grid is 1x1	If the first cell is flooded on day 1, return 0; otherwise, return the last day.
All cells are flooded on day 1	Return 0, since the crossing is blocked from the very beginning.
No path can ever be formed to cross the grid	Binary search will converge to the last day of the cells array.
Maximum grid size (large rows and cols values)	Ensure that the DFS or BFS used within the binary search does not exceed memory or time limits by optimizing data structures and search strategies.
Integer overflow when calculating cell indices	Use appropriate data types (e.g., long) to prevent integer overflow when mapping row and col to a 1D index.
Cells array contains invalid row/col combinations (out of bounds)	Filter out invalid cells from the input array or add checks during cell processing to prevent array index out of bounds errors.
The last cell in 'cells' is part of a path	The algorithm must still correctly validate this path exists before that last cell appears.