1391. Check if There is a Valid Path in a Grid
Problem Description
In this problem, we are provided with a grid where each cell represents a segment of a street. The streets are structured in such a way that certain types of streets can connect to others, while some cannot. There are 6 types of street segments represented by integers 1 through 6:
1represents a street that connects horizontally (left to right).2represents a street that connects vertically (up to down).3represents a street that connects the left cell to the lower cell.4represents a street that connects the right cell to the lower cell.5represents a street that connects the left cell to the upper cell.6represents a street that connects the right cell to the upper cell.
The task is to determine if there is a valid path that starts from the top-left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1) of the grid. The movement is restricted to the structure of the streets, meaning one can only move through connected streets, and it's not possible to move diagonally unless specified by the street type. Modifying the streets isn't allowed. The goal is to return true if such a path exists, otherwise return false.
Intuition
The solution employs the union-find algorithm, also known as the disjoint set data structure, which keeps track of elements that are split into one or more disjoint sets. It provides two main operations: find and union. Find checks which subset a particular element is in, and union merges two subsets into a single subset.
Applying this concept to the grid, we can think of each cell as an element in a set. Initially, each cell is in its own set. As we inspect the streets' types, we decide whether to connect the cells into larger sets based on street direction. For instance, if there's a horizontal street (1), it would merge the sets of the left and right adjacent cells. Similarly, a vertical street (2) would unite the sets of the upper and lower adjacent cells, and so on.
The solution iterates through each cell in the grid. Depending on the street type of the current cell, it will unite the sets in the specific directions allowed. After processing the entire grid, if the starting cell (0, 0) and the ending cell (m - 1, n - 1) are part of the same set, it means there is a valid path between them, and hence the function returns true. Otherwise, it returns false, signifying that no path exists that connects the starting cell to the ending cell within the constraints given.
Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Solution Approach
The provided solution approach utilizes the union-find algorithm to determine if a valid path exists in the grid. The algorithm is implemented with the following key functions:
-
find(x): This function takes an elementxas an argument and returns the root element of the subset thatxbelongs to. Ifxis not its own parent, the function recursively calls itself with the parent ofxuntil it finds the root. This is a path compression technique that flattens the structure of the tree, making subsequent find operations faster. -
left(i, j),right(i, j),up(i, j),down(i, j): These functions check if there is a connection from cell(i, j)to its left, right, up, and down adjacent cells respectively. They do so by verifying whether the adjacent cells match the street types that allow such connections. If a connection exists, the function performs a union operation via thefindfunction to merge the sets.
To orchestrate the union-find process, the solution creates an array p that initially contains self-references for every element (indicating that each cell is its own set). The indices in the array are computed by mapping the 2D grid coordinates to a 1D array using the formula index = i * n + j, where i and j are the row and column of the cell, respectively, and n is the number of columns in the grid.
As it iterates over each cell, the solution uses the cell's street type to determine which adjacent cells (if any) should be part of the same set. For example, if the current street type is 1, the solution calls left(i, j) and right(i, j) to connect horizontally adjacent cells. For street type 2, it calls up(i, j) and down(i, j) to connect vertically adjacent cells, and so on for the other street types. After attempting to union adjacent cells based on their street type, all cells that are reachable from the starting cell should theoretically be part of the same set.
In the final step, the algorithm compares the root of the starting cell (0, 0) to the root of the ending cell (m - 1, n - 1). If both cells have the same root, this indicates that there is a path connecting them; hence the function returns true. Otherwise, if the roots are different, it returns false, signifying no valid path exists.
Overall, the solution leverages the union-find technique as a means to model the grid as a series of connected or disjoint sets, effectively reducing the problem of finding a valid path to a set connectivity problem.
Which of the following array represent a max heap?
Example Walkthrough
Let's consider a grid with the following street segments:
1[ 2 [1, 3], 3 [6, 1] 4]
This grid is 2 cells high (m = 2) and 2 cells wide (n = 2), with the following cells:
- Top-left cell is type 1 (a horizontal street).
- Top-right cell is type 3 (connects left to lower).
- Bottom-left cell is type 6 (connects right to upper).
- Bottom-right cell is type 1 (a horizontal street again).
We want to find out if there is a path from the top-left cell (0, 0) to the bottom-right cell (1, 1).
The initial state of our set array p contains self-references: [0, 1, 2, 3] for 4 cells respectively.
-
First, we check cell (0, 0) which has street type 1. It can be connected horizontally, so we check and connect it to cell (0, 1) to the right. Since cell (0, 1) has a street type 3, which connects left to lower, we link cell (0, 0) to cell (1, 0). The updated state of
pmight now look like [0, 0, 2, 3] after the unions, indicating that the top left and top right cells are connected (sharing the same set). -
Next, we check cell (0, 1) which is a type 3 street (left to lower connection). We already have it connected to cell (0, 0), and we connect it to cell (1, 1) below.
pstate might now look like [0, 0, 2, 0], showing that cells (0, 0), (0, 1), and (1, 1) are now connected. -
Moving to cell (1, 0) which is type 6 (connects right to upper), it can be connected back to cell (0, 0) by virtue of the matching street type 3 in the top right cell. We perform a find operation to confirm this connection. The state of
premains [0, 0, 2, 0]. -
Finally, for cell (1, 1) with street type 1, it is connected horizontally to cell (1, 0), but since it's already in the same set after the previous operations, there's no further union to perform.
premains [0, 0, 2, 0].
Now, we check if cell (0, 0) and cell (1, 1) are in the same set. They are in the same set since the root for both elements in p is 0 after the unions.
Since the roots match, there is indeed a path that exists from the starting cell to the ending cell, and so the function will return true.
As this example demonstrated, the grid was interpreted as a series of connections, with the union-find algorithm smartly grouping cells into sets that are connected through valid street types, allowing us to determine the existence of a valid path from the top-left to the bottom-right cell.
Solution Implementation
1class Solution:
2 def hasValidPath(self, grid: List[List[int]]) -> bool:
3 # Get the number of rows and columns in the grid
4 num_rows, num_cols = len(grid), len(grid[0])
5 # Create a parent list for Union-Find data structure
6 parent = list(range(num_rows * num_cols))
7
8 # The 'find' function for the Union-Find data structure
9 def find(x):
10 # Path compression
11 if parent[x] != x:
12 parent[x] = find(parent[x])
13 return parent[x]
14
15 # Connect current cell with the cell to the left
16 def connect_left(i, j):
17 if j > 0 and grid[i][j - 1] in (1, 4, 6):
18 # Union operation
19 parent[find(i * num_cols + j)] = find(i * num_cols + j - 1)
20
21 # Connect current cell with the cell to the right
22 def connect_right(i, j):
23 if j < num_cols - 1 and grid[i][j + 1] in (1, 3, 5):
24 # Union operation
25 parent[find(i * num_cols + j)] = find(i * num_cols + j + 1)
26
27 # Connect current cell with the cell above
28 def connect_up(i, j):
29 if i > 0 and grid[i - 1][j] in (2, 3, 4):
30 # Union operation
31 parent[find(i * num_cols + j)] = find((i - 1) * num_cols + j)
32
33 # Connect current cell with the cell below
34 def connect_down(i, j):
35 if i < num_rows - 1 and grid[i + 1][j] in (2, 5, 6):
36 # Union operation
37 parent[find(i * num_cols + j)] = find((i + 1) * num_cols + j)
38
39 # Traverse each cell in the grid
40 for i in range(num_rows):
41 for j in range(num_cols):
42 # Extract the street type from the grid
43 street_type = grid[i][j]
44
45 # Connect the current cell with the neighboring cells
46 # depending on the street type
47 if street_type == 1:
48 connect_left(i, j)
49 connect_right(i, j)
50 elif street_type == 2:
51 connect_up(i, j)
52 connect_down(i, j)
53 elif street_type == 3:
54 connect_left(i, j)
55 connect_down(i, j)
56 elif street_type == 4:
57 connect_right(i, j)
58 connect_down(i, j)
59 elif street_type == 5:
60 connect_left(i, j)
61 connect_up(i, j)
62 else: # street_type == 6
63 connect_right(i, j)
64 connect_up(i, j)
65
66 # Check if the start and end points are in the same connected component
67 return find(0) == find(num_rows * num_cols - 1)
681class Solution {
2 private int[] parent;
3 private int[][] grid;
4 private int rows;
5 private int cols;
6
7 /**
8 * Checks if there is a valid path in the grid.
9 *
10 * @param grid the grid representation where each cell has a street piece.
11 * @return true if there's a valid path from top-left to bottom-right, false otherwise.
12 */
13 public boolean hasValidPath(int[][] grid) {
14 this.grid = grid;
15 rows = grid.length;
16 cols = grid[0].length;
17 parent = new int[rows * cols]; // array to represent the union-find structure
18
19 // Initialize union-find structure, each cell is its own parent initially
20 for (int i = 0; i < parent.length; ++i) {
21 parent[i] = i;
22 }
23
24 // Union adjacent compatible cells
25 for (int i = 0; i < rows; ++i) {
26 for (int j = 0; j < cols; ++j) {
27 int streetPiece = grid[i][j];
28 switch (streetPiece) {
29 case 1:
30 unionLeft(i, j);
31 unionRight(i, j);
32 break;
33 case 2:
34 unionUp(i, j);
35 unionDown(i, j);
36 break;
37 case 3:
38 unionLeft(i, j);
39 unionDown(i, j);
40 break;
41 case 4:
42 unionRight(i, j);
43 unionDown(i, j);
44 break;
45 case 5:
46 unionLeft(i, j);
47 unionUp(i, j);
48 break;
49 case 6:
50 unionRight(i, j);
51 unionUp(i, j);
52 break;
53 default:
54 break;
55 }
56 }
57 }
58
59 // Check if top left cell and bottom right cell are connected
60 return find(0) == find(rows * cols - 1);
61 }
62
63 /**
64 * Finds the root of x using path compression.
65 *
66 * @param x the node to find the root of.
67 * @return the root of x.
68 */
69 private int find(int x) {
70 if (parent[x] != x) {
71 parent[x] = find(parent[x]);
72 }
73 return parent[x];
74 }
75
76 /**
77 * Union the current cell with the cell to the left if compatible.
78 *
79 * @param i the row index.
80 * @param j the column index.
81 */
82 private void unionLeft(int i, int j) {
83 if (j > 0 && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
84 parent[find(i * cols + j)] = find(i * cols + j - 1);
85 }
86 }
87
88 /**
89 * Union the current cell with the cell to the right if compatible.
90 *
91 * @param i the row index.
92 * @param j the column index.
93 */
94 private void unionRight(int i, int j) {
95 if (j < cols - 1 && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
96 parent[find(i * cols + j)] = find(i * cols + j + 1);
97 }
98 }
99
100 /**
101 * Union the current cell with the cell above if compatible.
102 *
103 * @param i the row index.
104 * @param j the column index.
105 */
106 private void unionUp(int i, int j) {
107 if (i > 0 && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
108 parent[find(i * cols + j)] = find((i - 1) * cols + j);
109 }
110 }
111
112 /**
113 * Union the current cell with the cell below if compatible.
114 *
115 * @param i the row index.
116 * @param j the column index.
117 */
118 private void unionDown(int i, int j) {
119 if (i < rows - 1 && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
120 parent[find(i * cols + j)] = find((i + 1) * cols + j);
121 }
122 }
123}
1241class Solution {
2public:
3 vector<int> parent; // Use 'parent' to represent the disjoint set union data structure.
4
5 // Define a method to find the absolute parent (representative) of the set.
6 int find(int x) {
7 if (parent[x] != x) {
8 parent[x] = find(parent[x]);
9 }
10 return parent[x];
11 }
12
13 // Main function to determine if there is a valid path in the grid.
14 bool hasValidPath(vector<vector<int>>& grid) {
15 int rows = grid.size(); // The number of rows in the grid.
16 int cols = grid[0].size(); // The number of columns in the grid.
17 parent.resize(rows * cols); // Resize the 'parent' vector to fit the grid.
18
19 // Initialize each cell's parent to itself.
20 for (int i = 0; i < parent.size(); ++i) {
21 parent[i] = i;
22 }
23
24 // Lambda function to connect the current cell with the cell to its left.
25 auto connectLeft = [&](int row, int col) {
26 if (col > 0 && (grid[row][col - 1] == 1 || grid[row][col - 1] == 4 || grid[row][col - 1] == 6)) {
27 parent[find(row * cols + col)] = find(row * cols + col - 1);
28 }
29 };
30
31 // Lambda function to connect the current cell with the cell to its right.
32 auto connectRight = [&](int row, int col) {
33 if (col < cols - 1 && (grid[row][col + 1] == 1 || grid[row][col + 1] == 3 || grid[row][col + 1] == 5)) {
34 parent[find(row * cols + col)] = find(row * cols + col + 1);
35 }
36 };
37
38 // Lambda function to connect the current cell with the cell above it.
39 auto connectUp = [&](int row, int col) {
40 if (row > 0 && (grid[row - 1][col] == 2 || grid[row - 1][col] == 3 || grid[row - 1][col] == 4)) {
41 parent[find(row * cols + col)] = find((row - 1) * cols + col);
42 }
43 };
44
45 // Lambda function to connect the current cell with the cell below it.
46 auto connectDown = [&](int row, int col) {
47 if (row < rows - 1 && (grid[row + 1][col] == 2 || grid[row + 1][col] == 5 || grid[row + 1][col] == 6)) {
48 parent[find(row * cols + col)] = find((row + 1) * cols + col);
49 }
50 };
51
52 // Iterate over each cell in the grid to establish connections.
53 for (int row = 0; row < rows; ++row) {
54 for (int col = 0; col < cols; ++col) {
55 int tileType = grid[row][col];
56 if (tileType == 1) {
57 connectLeft(row, col);
58 connectRight(row, col);
59 } else if (tileType == 2) {
60 connectUp(row, col);
61 connectDown(row, col);
62 } else if (tileType == 3) {
63 connectLeft(row, col);
64 connectDown(row, col);
65 } else if (tileType == 4) {
66 connectRight(row, col);
67 connectDown(row, col);
68 } else if (tileType == 5) {
69 connectLeft(row, col);
70 connectUp(row, col);
71 } else { // tileType == 6
72 connectRight(row, col);
73 connectUp(row, col);
74 }
75 }
76 }
77
78 // Check if the start (0,0) cell has the same root as the end (rows-1,cols-1) cell.
79 return find(0) == find(rows * cols - 1);
80 }
81};
821interface DisjointSet {
2 // Use the 'parent' array to represent the disjoint set union data structure.
3 find(x: number): number;
4 union(x: number, y: number): void;
5 hasValidPath(grid: number[][]): boolean;
6}
7
8// Global variable to represent the disjoint set.
9let parent: number[];
10
11// Function to find the absolute parent (representative) of the set for element x.
12function find(x: number): number {
13 if (parent[x] != x) {
14 parent[x] = find(parent[x]);
15 }
16 return parent[x];
17}
18
19// Main function to determine if there is a valid path in the grid.
20function hasValidPath(grid: number[][]): boolean {
21 const rows = grid.length; // The number of rows in the grid.
22 const cols = grid[0].length; // The number of columns in the grid.
23 parent = Array.from({ length: rows * cols }, (_, index) => index); // Initialize each cell's parent to itself.
24
25 // Nested function to connect the current cell with the cell to its left.
26 const connectLeft = (row: number, col: number): void => {
27 if (col > 0 && [1, 4, 6].includes(grid[row][col - 1])) {
28 parent[find(row * cols + col)] = find(row * cols + col - 1);
29 }
30 };
31
32 // Nested function to connect the current cell with the cell to its right.
33 const connectRight = (row: number, col: number): void => {
34 if (col < cols - 1 && [1, 3, 5].includes(grid[row][col + 1])) {
35 parent[find(row * cols + col)] = find(row * cols + col + 1);
36 }
37 };
38
39 // Nested function to connect the current cell with the cell above it.
40 const connectUp = (row: number, col: number): void => {
41 if (row > 0 && [2, 3, 4].includes(grid[row - 1][col])) {
42 parent[find(row * cols + col)] = find((row - 1) * cols + col);
43 }
44 };
45
46 // Nested function to connect the current cell with the cell below it.
47 const connectDown = (row: number, col: number): void => {
48 if (row < rows - 1 && [2, 5, 6].includes(grid[row + 1][col])) {
49 parent[find(row * cols + col)] = find((row + 1) * cols + col);
50 }
51 };
52
53 // Iterate over each cell in the grid to establish connections.
54 for (let row = 0; row < rows; ++row) {
55 for (let col = 0; col < cols; ++col) {
56 const tileType = grid[row][col];
57 if (tileType === 1) {
58 connectLeft(row, col);
59 connectRight(row, col);
60 } else if (tileType === 2) {
61 connectUp(row, col);
62 connectDown(row, col);
63 } else if (tileType === 3) {
64 connectLeft(row, col);
65 connectDown(row, col);
66 } else if (tileType === 4) {
67 connectRight(row, col);
68 connectDown(row, col);
69 } else if (tileType === 5) {
70 connectLeft(row, col);
71 connectUp(row, col);
72 } else { // tileType == 6
73 connectRight(row, col);
74 connectUp(row, col);
75 }
76 }
77 }
78
79 // Check if the start (0, 0) cell has the same root as the end (rows - 1, cols - 1) cell.
80 return find(0) === find(rows * cols - 1);
81}
82What data structure does Breadth-first search typically uses to store intermediate states?
Time and Space Complexity
The given Python code uses Union-Find (Disjoint Set Union) to check if there is a valid path in a grid. Union-Find operations (find and union-by-rank) normally have an amortized time complexity of O(ฮฑ(n)), where ฮฑ(n) is the inverse Ackermann function and is nearly constant (ฮฑ(n) <= 4 for any practical value of n).
-
Time Complexity:
- The time complexity is dictated by the number of calls to the
findand union operations within the loops. There are m rows and n columns, so we have m * n cells in the grid. - The
findoperation is called up to four times per cell (left, right, up, down), which means up to4 * m * nfind operations. - However, each
findoperation takes O(ฮฑ(m * n)) time due to path compression. - The actual time complexity is therefore
O(4 * m * n * ฮฑ(m * n)), which simplifies toO(m * n * ฮฑ(m * n)).
- The time complexity is dictated by the number of calls to the
-
Space Complexity:
- The parent array
phas m * n elements, which is the main space complexity contributor. - Space complexity is therefore
O(m * n)because this array scales linearly with the number of cells in the grid.
- The parent array
In summary, the time complexity is O(m * n * ฮฑ(m * n)) and the space complexity is O(m * n).
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.