1970. Last Day Where You Can Still Cross

HardDepth-First SearchBreadth-First SearchUnion FindArrayBinary SearchMatrix

Problem Description

The problem poses a scenario where we have a landmass represented by a binary matrix with 1s as water and 0s as land. We start with a matrix that is all land on day 0 and each day one cell gets flooded and turns into water. The goal is to determine the last day when it's possible to traverse from the top row to the bottom row entirely walking on land cells only. You may begin your traverse from any cell on the top row and must reach any cell on the bottom row, moving only up, down, left, or right.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

Yes: The grid in the problem can be viewed as a graph where each cell represents a node. Edges exist between adjacent cells (up, down, left, right).

Is it a tree?

No: The graph representing the grid can have loops due to multiple pathways (cells) connected, and potentially many connected components, especially considering various states of flooding over days. It is hence not a tree structure.

Is the problem related to directed acyclic graphs (DAGs)?

No: The structure and nature of the problem revolves around a grid with undirected connectivity between the cells and does not involve acyclic properties or directiveness pertinent to DAGs.

Is the problem related to shortest paths?

No: The goal is to find a day where it's still possible to cross from one side to another and not about finding the shortest path across.

Does the problem involve connectivity?

Yes: The main challenge in the problem is to determine if there is a path (connectivity) that allows crossing from one side of the grid to the other, despite cells being blocked over time due to rising water.

Does the problem have small constraints?

Given that the problem might not explicitly specify small constraints that simplify the approach like smaller grids or unique scenarios, we would not immediately opt for methods ideally used in such conditions, which may include naive or brute force approaches.

With these considerations: The question involves checking connectivity in an evolving grid, suggesting methods like DFS or BFS are suitable for exploring possible paths in the grid as it changes from day to day.

Conclusion: The flowchart suggests using DFS for this connectivity problem in an evolving (non-static) grid environment.

Intuition

To solve this problem, we observe that traversing the entire land can be interpreted as finding a path between the top and bottom that is not cut by water. Therefore, as the days progress and more cells are flooded, we must continuously monitor when such a path becomes impossible.

The intuition behind the solution is to use a technique called "Union-Find" or "Disjoint Set Union (DSU)" to dynamically track connectivities between land cells. This data structure allows us to efficiently merge land regions and check if a continuous path from top to bottom exists.

The solution iterates from the last day to the first day (reverse flood order), treating each day's cell conversion from water to land and connecting it with other land cells adjacent to it. By doing this in reverse, we can find the moment just before the land cells' connections are severed to the point that top-to-bottom traversal is no longer possible.

For efficiency, the solution introduces two virtual nodes, 'top' and 'bottom,' to represent the connections of all the top row cells and bottom row cells, respectively. This allows for an immediate check if there's a connection from any top cell to any bottom cell representing a valid path. As soon as we discover that the 'top' and 'bottom' nodes are connected, we've found the last day when the path was possible.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Binary Search patterns.

Solution Approach

The solution uses the Union-Find or Disjoint Set Union (DSU) algorithm to keep track of the connectivity between cells as land gets flooded with water. Here is a step-by-step explanation:

Initialization: We initialize a parent list p where each cell's index has itself as a parent. We also have a grid [[False] * col for _ in range(row)] which shows the status of each cell (land or water), and two variables top and bottom as virtual nodes to represent the top and bottom rows of the matrix.
Union-Find: The find function is a classic part of Union-Find that recursively finds the representative (root) of the group a node belongs to. If a node's parent is itself, it's the root; otherwise, we recursively call find on its parent, implementing path compression by setting the parent directly to the root for efficiency.
Reverse Flooding Process: We iterate over cells in reverse order. As we're moving backward, we pretend to dry each flooded cell to see when a path last existed from top to bottom.
Making Connections: We mark grid[i][j] as land, and for each adjacent land cell, we union the current cell with the adjacent cells by setting the parent of the current cell's root to be the root of the adjacent cell.
Linking to Virtual Nodes: If a cell is in the top row, we union it with the top node. Similarly, for the bottom row cells, we union them with the bottom node.
Checking Connectivity: After each union, we check if the top node is connected to the bottom node by checking if they have the same parent. If yes, we found the last day where it's possible to walk from top to bottom.
Return the Last Day: The first day (in reverse order) when top and bottom are connected is the answer. If no such day is found, we return 0, implying that it was always possible to cross from the top to the bottom of the matrix.

In this implementation, DSU is used effectively to manage the merging of the land areas and allows us to query connectivity status between the virtual top and bottom nodes in nearly constant time due to path compression.

The given Python code demonstrates an efficient method to solve the problem using these principles. The function check is a helper function to determine whether a neighboring cell is within bounds and is land (True).

By initializing the DSU with extra two nodes for top and bottom, we avoid checking every possible path from the top to bottom row every time, reducing the complexity significantly.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Day 0 (initial state):

0: Land
1: Water

Matrix (binary grid):
0 0
0 0

Flooded cells by day:
Day 1: (0,0)
Day 2: (1,0)

(Note: Day count starts from 1)

Problem: Identify the last day when it was possible to traverse from the top row (first row) to the bottom row (second row) on land before the given matrix is entirely flooded.

Steps:

Initialization:
- Parent list p is initialized with each cell pointing to itself.
- Grid is all False initially (all land).
- Virtual nodes top and bottom are introduced.
Matrix after Day 2:
```
1 0
1 0
```
There is no way to go from the top to bottom, as the leftmost column is completely water. Our goal is to find when this disconnection happened.
Reverse Flooding Process: We iterate from the last flooded cell to the first one:
- Day 2 cell (1,0) dries up. Grid now looks like this:
```
1 0
0 0
```
  Still no top to bottom path since the first column is disconnected at the top.
- Day 1 cell (0,0) dries up. Grid now looks like this:
```
0 0
0 0
```
  There is now a clear path from the top row to the bottom row.
Making Connections and Linking to Virtual Nodes:
- On drying cell (0,0), we connect it to its adjacent land cells (right cell (0,1)) and to the virtual node top.
- On drying cell (1,0), we link it to its adjacent cell (right cell (1,1)).
Checking Connectivity:
- After the flooding is reversed on Day 2, we still cannot go from the top to the bottom.
- After the flooding is reversed on Day 1, top and bottom are now connected, indicating a path is possible.
Return the Last Day:
- The last day when the top and bottom are connected is Day 1. Before Day 1, there is no connectivity after the flood; therefore, the water barrier is placed on Day 1.

For larger matrices, the approach is similar, but with more connections and cells to union and find. Using the Union-Find algorithm allows us to efficiently check connectivity without manually inspecting each potential path, which would be much slower. The two virtual nodes effectively represent all possible starting and ending points, streamlining the process.

Solution Implementation

1from typing import List
2
3class Solution:
4    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
5        # Total number of cells in the grid
6        total_cells = row * col
7        # Parent array for Union-Find with two extra elements for top and bottom virtual nodes
8        parent = list(range(total_cells + 2))
9        # Grid to represent if a cell is filled with water (False) or not (True)
10        grid = [[False] * col for _ in range(row)]
11        # Constants to represent the virtual top node and the bottom node
12        top_virtual_node, bottom_virtual_node = total_cells, total_cells + 1
13
14        # Function to find the root of a set in Union-Find
15        def find(x):
16            if parent[x] != x:
17                parent[x] = find(parent[x])
18            return parent[x]
19
20        # Function to check if the neighboring cell is valid and already filled
21        def is_valid_and_filled(i, j):
22            return 0 <= i < row and 0 <= j < col and grid[i][j]
23
24        # Iterate the cells starting from the last day, going backwards
25        for day in range(len(cells) - 1, -1, -1):
26            # Convert from 1-indexed to 0-indexed
27            i, j = cells[day][0] - 1, cells[day][1] - 1
28            # The current cell is now filled
29            grid[i][j] = True
30            # Directions for neighboring cells [right, left, down, up]
31            directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
32          
33            # Union current cell with its neighboring filled cells
34            for dx, dy in directions:
35                next_i, next_j = i + dx, j + dy
36                if is_valid_and_filled(next_i, next_j):
37                    parent[find(i * col + j)] = find(next_i * col + next_j)
38          
39            # Union with top virtual node if it's the first row
40            if i == 0:
41                parent[find(i * col + j)] = find(top_virtual_node)
42            # Union with bottom virtual node if it's the last row
43            if i == row - 1:
44                parent[find(i * col + j)] = find(bottom_virtual_node)
45          
46            # If top and bottom virtual nodes are connected, return the current day
47            if find(top_virtual_node) == find(bottom_virtual_node):
48                return day
49      
50        # If no connection is ever made, return 0
51        return 0
52

1class Solution {
2    private int[] parent; // Union-find array to track connected components
3    private int rowCount; // Number of rows in the grid
4    private int colCount; // Number of columns in the grid
5    private boolean[][] grid; // Representation of the grid's current state
6    private final int[][] directions = new int[][] {{0, -1}, {0, 1}, {1, 0}, {-1, 0}}; // 4 directional vectors
7
8    // Method to determine the latest day to cross the river
9    public int latestDayToCross(int row, int col, int[][] cells) {
10        int n = row * col;
11        this.rowCount = row;
12        this.colCount = col;
13        this.parent = new int[n + 2];
14        // Initialize the union-find structure
15        for (int i = 0; i < parent.length; ++i) {
16            parent[i] = i;
17        }
18        this.grid = new boolean[row][col];
19        int top = n, bottom = n + 1; // Virtual top and bottom nodes
20      
21        // Process cells in reverse order
22        for (int k = cells.length - 1; k >= 0; --k) {
23            int r = cells[k][0] - 1; // Adjusted row index (0-based)
24            int c = cells[k][1] - 1; // Adjusted column index (0-based)
25            grid[r][c] = true; // Set the current cell to be available
26            // Connect current cell with its adjacent available cells
27            for (int[] direction : directions) {
28                int nextR = r + direction[0];
29                int nextC = c + direction[1];
30                if (isInsideGrid(nextR, nextC)) {
31                    union(getIndex(r, c), getIndex(nextR, nextC));
32                }
33            }
34            // Connect to virtual top and bottom nodes if applicable
35            if (r == 0) {
36                union(getIndex(r, c), top);
37            }
38            if (r == rowCount - 1) {
39                union(getIndex(r, c), bottom);
40            }
41            // If top node and bottom node are connected, return current day
42            if (find(top) == find(bottom)) {
43                return k;
44            }
45        }
46      
47        return 0; // If there is no way to cross, return 0
48    }
49
50    // Find method for union-find, with path compression
51    private int find(int x) {
52        if (parent[x] != x) {
53            parent[x] = find(parent[x]);
54        }
55        return parent[x];
56    }
57  
58    // Union method for union-find, connects two elements
59    private void union(int x, int y) {
60        parent[find(x)] = find(y);
61    }
62
63    // Helper function to determine if a cell is within the grid
64    private boolean isInsideGrid(int r, int c) {
65        return r >= 0 && r < rowCount && c >= 0 && c < colCount && grid[r][c];
66    }
67
68    // Helper function to convert 2D cell indices to 1D union-find index
69    private int getIndex(int r, int c) {
70        return r * colCount + c;
71    }
72}
73

1#include <vector>
2
3using namespace std;
4
5class Solution {
6public:
7    // Parent array for Disjoint Set data structure (Union-Find)
8    vector<int> parent;
9    // Array to represent the four directional moves (left, right, down, up)
10    int dirs[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
11    // Member variables to store the number of rows and columns of the grid
12    int totalRows, totalCols;
13
14    // Method to determine the latest day it's possible to cross the river
15    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
16        // Total number of cells and setting class variables
17        int totalCells = row * col;
18        totalRows = row;
19        totalCols = col;
20        // Resize parent array to accommodate all cells and two virtual nodes
21        parent.resize(totalCells + 2);
22
23        // Initialize the parent array such that each node is its own parent
24        for (int i = 0; i < parent.size(); ++i) {
25            parent[i] = i;
26        }
27
28        // Grid to keep track of the filled cells
29        vector<vector<bool>> grid(row, vector<bool>(col, false));
30        // Define two virtual nodes representing the top and bottom of the grid
31        int virtualTop = totalCells, virtualBottom = totalCells + 1;
32
33        // Iterate from the last day to the first (reverse flooding)
34        for (int k = cells.size() - 1; k >= 0; --k) {
35            // Get the actual row and column index from the cells vector
36            int i = cells[k][0] - 1, j = cells[k][1] - 1;
37            // Fill the cell
38            grid[i][j] = true;
39
40            // Connect the current cell with its adjacent filled cells
41            for (auto &dir : dirs) {
42                // Check if an adjacent cell is filled and valid
43                if (isValid(i + dir[0], j + dir[1], grid)) {
44                    // Union-find merge operation
45                    parent[find(i * col + j)] = find((i + dir[0]) * col + j + dir[1]);
46                }
47            }
48
49            // Connect the current cell to the virtual top if it's on the first row
50            if (i == 0) {
51                parent[find(i * col + j)] = find(virtualTop);
52            }
53            // Connect the current cell to the virtual bottom if it's on the last row
54            if (i == row - 1) {
55                parent[find(i * col + j)] = find(virtualBottom);
56            }
57
58            // If virtual top and bottom are connected, it's possible to cross the grid, return the day
59            if (find(virtualTop) == find(virtualBottom)) {
60                return k;
61            }
62        }
63        // If no such day exists, return 0
64        return 0;
65    }
66
67    // Helper function to check if a cell is within the grid bounds and is filled
68    bool isValid(int i, int j, vector<vector<bool>>& grid) {
69        return i >= 0 && i < totalRows && j >= 0 && j < totalCols && grid[i][j];
70    }
71
72    // Union-Find 'find' operation with path compression
73    int find(int x) {
74        // Recursively find the ultimate parent of x
75        if (parent[x] != x) {
76            parent[x] = find(parent[x]);
77        }
78        return parent[x];
79    }
80};
81

1// Type representing the direction moves
2type Direction = [number, number];
3
4// Initialize the parent array for the disjoint-set data structure (Union-Find).
5let parent: number[];
6
7// Initialize the array that represents the directional moves: left, right, down, up.
8const dirs: Direction[] = [[0, -1], [0, 1], [1, 0], [-1, 0]];
9
10// Declare variables to store the number of rows and columns of the grid.
11let totalRows: number;
12let totalCols: number;
13
14// Function to determine the latest day it is possible to cross the river.
15function latestDayToCross(row: number, col: number, cells: number[][]): number {
16    const totalCells = row * col;
17    totalRows = row;
18    totalCols = col;
19
20    // Resize the parent array to accommodate all cells plus two virtual nodes.
21    parent = Array.from({ length: totalCells + 2 }, (_, index) => index);
22
23    // Create a grid to keep track of which cells are filled.
24    const grid: boolean[][] = Array.from({ length: row }, () => new Array<boolean>(col).fill(false));
25    // Define two virtual nodes representing the top and bottom of the grid.
26    const virtualTop = totalCells;
27    const virtualBottom = totalCells + 1;
28
29    // Iterate from the last day to the first (reverse process of flooding).
30    for (let k = cells.length - 1; k >= 0; --k) {
31        const i = cells[k][0] - 1;
32        const j = cells[k][1] - 1;
33
34        // Mark the cell as filled.
35        grid[i][j] = true;
36
37        // Connect the current cell with its adjacent filled cells.
38        for (const dir of dirs) {
39            // Check if an adjacent cell is filled and exists within grid bounds.
40            if (isValid(i + dir[0], j + dir[1], grid)) {
41                union(i * col + j, (i + dir[0]) * col + (j + dir[1]));
42            }
43        }
44
45        // Connect the cell on the top row to the virtual top node.
46        if (i === 0) {
47            union(i * col + j, virtualTop);
48        }
49
50        // Connect the cell on the bottom row to the virtual bottom node.
51        if (i === row - 1) {
52            union(i * col + j, virtualBottom);
53        }
54
55        // If the top and bottom are connected, return the current day.
56        if (find(virtualTop) === find(virtualBottom)) {
57            return k;
58        }
59    }
60
61    // If no such day exists where one can cross, return 0.
62    return 0;
63}
64
65// Helper function to check if a cell is within the grid bounds and is filled.
66function isValid(i: number, j: number, grid: boolean[][]): boolean {
67    return i >= 0 && i < totalRows && j >= 0 && j < totalCols && grid[i][j];
68}
69
70// Union-Find 'find' operation with path compression.
71function find(x: number): number {
72    if (parent[x] !== x) {
73        parent[x] = find(parent[x]);
74    }
75    return parent[x];
76}
77
78// Union function that merges two subsets represented by x and y.
79function union(x: number, y: number): void {
80    parent[find(x)] = find(y);
81}
82

Time and Space Complexity

The provided Python code defines a function latestDayToCross that finds the latest day you can cross from the top to the bottom of a grid by stepping only on cells that are present. It implements a version of the Union-Find algorithm to keep track of connected components within the grid.

Time Complexity

The time complexity of the function is determined by iterating over the list cells in reverse and performing Union-Find operations for each cell to determine connectivity. The main components influencing the time complexity are:

The initial loop over cells runs in reverse, which results in O(m) complexity where m is the number of elements in cells.
Inside this loop, several constant-time operations are carried out, such as value assignments and boolean checks.
The find function is called multiple times inside the loop. The time complexity of the find method is near-constant on average, due to path compression, but strictly it’s O(log*(n)) per call, where log* is the iterated logarithm and n is the number of cells in the grid. However, in practice, for most cases this can be considered almost O(1).
The loop inside the main loop iterates a constant number of times (at most 4), doing constant work each time and calling the find function.

Combining all these, the total average time complexity is O(mα(n)), with m being the length of the cells array and α(n) being the Inverse Ackermann function which is very slow-growing and treated as almost O(1) for all practical purposes.

Space Complexity

The space complexity of the latestDayToCross function comprises several components:

The parent array p, which is a list of size n + 2 where n is the number of cells in the grid, hence O(n).
The grid, which stores a row x col sized grid of the cells, leading to O(n) space.
Constant amount of space for variables like top, bottom, i, j, and the for loop variables.

Thus, the total space complexity is O(n), where n is the product of row and col.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following shows the order of node visit in a Breadth-first Search?

I don’t know