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:

  • 1 represents a street that connects horizontally (left to right).
  • 2 represents a street that connects vertically (up to down).
  • 3 represents a street that connects the left cell to the lower cell.
  • 4 represents a street that connects the right cell to the lower cell.
  • 5 represents a street that connects the left cell to the upper cell.
  • 6 represents 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which two pointer techniques do you use to check if a string is a palindrome?

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 element x as an argument and returns the root element of the subset that x belongs to. If x is not its own parent, the function recursively calls itself with the parent of x until 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 the find function 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.

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

Which algorithm should you use to find a node that is close to the root of the tree?

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.

  1. 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 p might 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).

  2. 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. p state might now look like [0, 0, 2, 0], showing that cells (0, 0), (0, 1), and (1, 1) are now connected.

  3. 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 p remains [0, 0, 2, 0].

  4. 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. p remains [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)
68
1class 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}
124
1class 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};
82
1interface 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}
82
Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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 find and union operations within the loops. There are m rows and n columns, so we have m * n cells in the grid.
    • The find operation is called up to four times per cell (left, right, up, down), which means up to 4 * m * n find operations.
    • However, each find operation takes O(α(m * n)) time due to path compression.
    • The actual time complexity is therefore O(4 * m * n * α(m * n)), which simplifies to O(m * n * α(m * n)).
  • Space Complexity:

    • The parent array p has 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.

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.


Recommended Readings


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.