Facebook Pixel

1391. Check if There is a Valid Path in a Grid

MediumDepth-First SearchBreadth-First SearchUnion FindArrayMatrix
Leetcode Link

Problem Description

You have an m x n grid where each cell contains a street piece represented by a number from 1 to 6. Each number represents a different type of street connection:

  • Street type 1: Connects left ↔ right cells (horizontal street)
  • Street type 2: Connects upper ↔ lower cells (vertical street)
  • Street type 3: Connects left ↔ lower cells (L-shaped, opening down-left)
  • Street type 4: Connects right ↔ lower cells (L-shaped, opening down-right)
  • Street type 5: Connects left ↔ upper cells (L-shaped, opening up-left)
  • Street type 6: Connects right ↔ upper cells (L-shaped, opening up-right)

Your task is to determine if there's a valid path from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1) by following only the existing street connections. You cannot modify any streets - you must use them as they are.

For a path to be valid:

  • It must start at position (0, 0)
  • It must end at position (m-1, n-1)
  • You can only move between cells if their street pieces connect properly (e.g., if you're in a cell with street type 1 that connects left-right, you can only move to adjacent cells on the left or right if those cells have compatible street connections pointing back)

The solution uses a Union-Find (Disjoint Set Union) approach. It iterates through each cell and checks which directions that cell's street connects to. For each valid connection direction, it verifies if the adjacent cell has a compatible street type that would allow the connection. If compatible, it unions the two cells in the disjoint set. Finally, it checks if the starting cell (0, 0) and ending cell (m-1, n-1) belong to the same connected component, which would indicate a valid path exists.

Return true if such a valid path exists, otherwise return false.

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 problem involves a grid where each cell represents a street piece that connects to adjacent cells. This forms a graph where cells are nodes and street connections are edges.

Is it a tree?

  • No: The grid structure with various street connections can form cycles and doesn't follow a tree structure (which would have no cycles and exactly one path between any two nodes).

Is the problem related to directed acyclic graphs?

  • No: The street connections are bidirectional (if cell A connects to cell B, then B also connects to A), and the graph can contain cycles.

Is the problem related to shortest paths?

  • No: We only need to determine if ANY valid path exists from start to end, not the shortest one.

Does the problem involve connectivity?

  • Yes: The core question is whether there's a connected path from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1) following valid street connections.

Disjoint Set Union

  • According to the flowchart, connectivity problems lead to DSU (Disjoint Set Union), which is exactly what the solution uses.

Alternative Path - Small Constraints: If we had answered "no" to connectivity and moved to "Does the problem have small constraints?":

  • Yes: The grid dimensions are typically reasonable for DFS traversal.
  • DFS/backtracking: This would lead us to use DFS to explore the path from start to end.

Conclusion: The flowchart correctly identifies this as a graph connectivity problem. While the provided solution uses DSU (Union-Find), DFS is equally valid here. Both approaches can determine if there's a connected path through the valid street connections from start to end. DFS would traverse from (0,0) following valid connections until it either reaches (m-1, n-1) or exhausts all possibilities.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

When we look at this problem, we need to find if there's a path from the top-left to bottom-right corner. The key insight is that each street piece has specific connection points - some connect left-right, some up-down, and others form L-shapes with various orientations.

The challenge is that we can't just move freely between adjacent cells. We can only move if both cells have compatible connections. For example, if we're in a cell with street type 1 (horizontal), we can move right only if the right cell has a street that accepts connections from the left (types 1, 3, or 5).

This is fundamentally a connectivity problem - we need to know if two points in our grid are connected through valid street paths. Two approaches naturally come to mind:

DFS Approach: We could start at (0, 0) and explore all valid paths by following the street connections. At each cell, we check which directions our current street allows us to go, then verify if the adjacent cell in that direction has a compatible street. We continue exploring until we either reach (m-1, n-1) or exhaust all possibilities.

Union-Find Approach: Instead of actively searching for a path, we can build the connectivity information for the entire grid upfront. We treat each cell as a node and connect (union) cells that have compatible street connections. After processing all cells, we simply check if the start and end cells belong to the same connected component.

The Union-Find approach is elegant because:

  1. We process each cell once and determine all its valid connections
  2. The compatibility check is straightforward - for each direction a street points, we verify the adjacent cell has a reciprocal connection
  3. The final answer is a simple check: find(start) == find(end)

The solution maps each 2D cell position (i, j) to a 1D index i * n + j for the Union-Find structure, making it easier to manage the parent array. This preprocessing approach builds a complete picture of the grid's connectivity before answering the path existence question.

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

Solution Approach

The solution implements a Union-Find (Disjoint Set Union) data structure to solve the connectivity problem. Let's walk through the implementation step by step:

1. Initialize the Union-Find Structure

p = list(range(m * n))

Each cell (i, j) is mapped to a unique ID i * n + j. Initially, each cell is its own parent, meaning no connections have been established yet.

2. Find Operation with Path Compression

def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

This recursively finds the root parent of a cell and applies path compression to optimize future lookups.

3. Direction-Specific Connection Functions

The solution defines four helper functions to check connections in each direction:

  • left(i, j): Checks if the current cell can connect to its left neighbor. The left cell must have street types 1, 4, or 6 (streets that have a right-facing connection).

  • right(i, j): Checks if the current cell can connect to its right neighbor. The right cell must have street types 1, 3, or 5 (streets that have a left-facing connection).

  • up(i, j): Checks if the current cell can connect to its upper neighbor. The upper cell must have street types 2, 3, or 4 (streets that have a downward connection).

  • down(i, j): Checks if the current cell can connect to its lower neighbor. The lower cell must have street types 2, 5, or 6 (streets that have an upward connection).

Each function performs a union operation if the connection is valid:

p[find(i * n + j)] = find(neighbor_position)

4. Process Each Cell Based on Street Type

The main loop iterates through each cell and calls the appropriate connection functions based on the street type:

  • Type 1 (horizontal): Check left and right connections
  • Type 2 (vertical): Check up and down connections
  • Type 3 (L-shape left-down): Check left and down connections
  • Type 4 (L-shape right-down): Check right and down connections
  • Type 5 (L-shape left-up): Check left and up connections
  • Type 6 (L-shape right-up): Check right and up connections

5. Check Final Connectivity

return find(0) == find(m * n - 1)

After processing all cells and establishing all valid connections, we check if the start cell (0, 0) (index 0) and end cell (m-1, n-1) (index m*n-1) belong to the same connected component.

The algorithm runs in O(m * n * Ξ±(m * n)) time, where Ξ± is the inverse Ackermann function (practically constant), making it nearly linear in the grid size. The space complexity is O(m * n) for the parent array.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Consider a 2Γ—3 grid:

[[1, 2, 1],
 [4, 1, 3]]

Let's visualize what each street type looks like:

Row 0: [1:━━, 2:┃ , 1:━━]
Row 1: [4:β”“ , 1:━━, 3:β”— ]

Step 1: Initialize Union-Find

  • Map each cell (i,j) to index i*3+j:
    • (0,0) β†’ 0, (0,1) β†’ 1, (0,2) β†’ 2
    • (1,0) β†’ 3, (1,1) β†’ 4, (1,2) β†’ 5
  • Parent array: p = [0, 1, 2, 3, 4, 5] (each cell is its own parent initially)

Step 2: Process Each Cell

Cell (0,0) - Street type 1 (horizontal ━━):

  • Connects left ← and right β†’
  • Check left: Out of bounds, skip
  • Check right to (0,1): Street type 2 (vertical), doesn't accept left connections βœ—
  • No unions performed

Cell (0,1) - Street type 2 (vertical ┃):

  • Connects up ↑ and down ↓
  • Check up: Out of bounds, skip
  • Check down to (1,1): Street type 1 (horizontal), doesn't accept up connections βœ—
  • No unions performed

Cell (0,2) - Street type 1 (horizontal ━━):

  • Connects left ← and right β†’
  • Check left to (0,1): Street type 2 (vertical), doesn't accept right connections βœ—
  • Check right: Out of bounds, skip
  • No unions performed

Cell (1,0) - Street type 4 (L-shape β”“):

  • Connects right β†’ and down ↓
  • Check right to (1,1): Street type 1 accepts left connections βœ“
    • Union: p[find(3)] = find(4) β†’ p[3] = 4
  • Check down: Out of bounds, skip
  • Parent array: p = [0, 1, 2, 4, 4, 5]

Cell (1,1) - Street type 1 (horizontal ━━):

  • Connects left ← and right β†’
  • Check left to (1,0): Street type 4 accepts right connections βœ“
    • Already connected (both have root 4)
  • Check right to (1,2): Street type 3 accepts left connections βœ“
    • Union: p[find(4)] = find(5) β†’ p[4] = 5
  • Parent array: p = [0, 1, 2, 4, 5, 5]

Cell (1,2) - Street type 3 (L-shape β”—):

  • Connects left ← and down ↓
  • Check left to (1,1): Street type 1 accepts right connections βœ“
    • Already connected (both have root 5)
  • Check down: Out of bounds, skip

Step 3: Check Connectivity

  • Start cell (0,0) has index 0: find(0) = 0
  • End cell (1,2) has index 5: find(5) = 5
  • Since 0 β‰  5, there's no valid path
  • Return false

The grid has two disconnected components:

  • Component 1: Cell (0,0) alone
  • Component 2: Cells (0,1), (0,2) alone
  • Component 3: Cells (1,0), (1,1), (1,2) connected

Since the start and end cells are in different components, no valid path exists from (0,0) to (1,2).

Solution Implementation

1class Solution:
2    def hasValidPath(self, grid: List[List[int]]) -> bool:
3        """
4        Check if there's a valid path from top-left to bottom-right in a grid.
5        Each cell contains a street piece (1-6) with specific connection patterns:
6        1: horizontal (left-right)
7        2: vertical (up-down)
8        3: left-down corner
9        4: right-down corner
10        5: left-up corner
11        6: right-up corner
12        """
13        rows, cols = len(grid), len(grid[0])
14      
15        # Initialize parent array for Union-Find
16        # Each cell is initially its own parent
17        parent = list(range(rows * cols))
18      
19        def find(node: int) -> int:
20            """Find the root parent of a node with path compression."""
21            if parent[node] != node:
22                parent[node] = find(parent[node])  # Path compression
23            return parent[node]
24      
25        def connect_left(row: int, col: int) -> None:
26            """Connect current cell with left neighbor if compatible."""
27            # Check if left neighbor exists and can connect from right
28            # Streets 1, 4, 6 have right openings
29            if col > 0 and grid[row][col - 1] in (1, 4, 6):
30                current_root = find(row * cols + col)
31                left_root = find(row * cols + col - 1)
32                parent[current_root] = left_root
33      
34        def connect_right(row: int, col: int) -> None:
35            """Connect current cell with right neighbor if compatible."""
36            # Check if right neighbor exists and can connect from left
37            # Streets 1, 3, 5 have left openings
38            if col < cols - 1 and grid[row][col + 1] in (1, 3, 5):
39                current_root = find(row * cols + col)
40                right_root = find(row * cols + col + 1)
41                parent[current_root] = right_root
42      
43        def connect_up(row: int, col: int) -> None:
44            """Connect current cell with upper neighbor if compatible."""
45            # Check if upper neighbor exists and can connect from bottom
46            # Streets 2, 3, 4 have bottom openings
47            if row > 0 and grid[row - 1][col] in (2, 3, 4):
48                current_root = find(row * cols + col)
49                up_root = find((row - 1) * cols + col)
50                parent[current_root] = up_root
51      
52        def connect_down(row: int, col: int) -> None:
53            """Connect current cell with lower neighbor if compatible."""
54            # Check if lower neighbor exists and can connect from top
55            # Streets 2, 5, 6 have top openings
56            if row < rows - 1 and grid[row + 1][col] in (2, 5, 6):
57                current_root = find(row * cols + col)
58                down_root = find((row + 1) * cols + col)
59                parent[current_root] = down_root
60      
61        # Process each cell in the grid
62        for row in range(rows):
63            for col in range(cols):
64                street_type = grid[row][col]
65              
66                # Connect neighbors based on street type
67                if street_type == 1:  # Horizontal street
68                    connect_left(row, col)
69                    connect_right(row, col)
70                elif street_type == 2:  # Vertical street
71                    connect_up(row, col)
72                    connect_down(row, col)
73                elif street_type == 3:  # Left-down corner
74                    connect_left(row, col)
75                    connect_down(row, col)
76                elif street_type == 4:  # Right-down corner
77                    connect_right(row, col)
78                    connect_down(row, col)
79                elif street_type == 5:  # Left-up corner
80                    connect_left(row, col)
81                    connect_up(row, col)
82                else:  # street_type == 6, Right-up corner
83                    connect_right(row, col)
84                    connect_up(row, col)
85      
86        # Check if start (0,0) and end (m-1,n-1) are connected
87        start_root = find(0)
88        end_root = find(rows * cols - 1)
89        return start_root == end_root
90
1class Solution {
2    // Union-Find parent array to track connected components
3    private int[] parent;
4    // The input grid representing street types
5    private int[][] grid;
6    // Number of rows in the grid
7    private int rows;
8    // Number of columns in the grid
9    private int cols;
10
11    /**
12     * Checks if there is a valid path from top-left to bottom-right corner.
13     * Each cell contains a street type (1-6) with different connection patterns:
14     * 1: horizontal street connecting left and right
15     * 2: vertical street connecting up and down
16     * 3: street connecting left and down
17     * 4: street connecting right and down
18     * 5: street connecting left and up
19     * 6: street connecting right and up
20     * 
21     * @param grid 2D array where each cell contains a street type (1-6)
22     * @return true if there's a valid path from (0,0) to (m-1,n-1)
23     */
24    public boolean hasValidPath(int[][] grid) {
25        this.grid = grid;
26        this.rows = grid.length;
27        this.cols = grid[0].length;
28      
29        // Initialize Union-Find structure
30        // Each cell is initially its own parent
31        parent = new int[rows * cols];
32        for (int i = 0; i < parent.length; ++i) {
33            parent[i] = i;
34        }
35      
36        // Process each cell in the grid
37        for (int i = 0; i < rows; ++i) {
38            for (int j = 0; j < cols; ++j) {
39                int streetType = grid[i][j];
40              
41                // Connect current cell with adjacent cells based on street type
42                if (streetType == 1) {
43                    // Horizontal street: connects left and right
44                    connectLeft(i, j);
45                    connectRight(i, j);
46                } else if (streetType == 2) {
47                    // Vertical street: connects up and down
48                    connectUp(i, j);
49                    connectDown(i, j);
50                } else if (streetType == 3) {
51                    // L-shaped street: connects left and down
52                    connectLeft(i, j);
53                    connectDown(i, j);
54                } else if (streetType == 4) {
55                    // L-shaped street: connects right and down
56                    connectRight(i, j);
57                    connectDown(i, j);
58                } else if (streetType == 5) {
59                    // L-shaped street: connects left and up
60                    connectLeft(i, j);
61                    connectUp(i, j);
62                } else {
63                    // streetType == 6
64                    // L-shaped street: connects right and up
65                    connectRight(i, j);
66                    connectUp(i, j);
67                }
68            }
69        }
70      
71        // Check if start and end cells are in the same connected component
72        return find(0) == find(rows * cols - 1);
73    }
74
75    /**
76     * Find operation with path compression for Union-Find.
77     * 
78     * @param x the element to find the root of
79     * @return the root of the set containing x
80     */
81    private int find(int x) {
82        if (parent[x] != x) {
83            // Path compression: make x point directly to root
84            parent[x] = find(parent[x]);
85        }
86        return parent[x];
87    }
88
89    /**
90     * Attempts to connect current cell with the cell to its left.
91     * Connection is valid if left cell exists and has a street that connects to the right.
92     * 
93     * @param i row index of current cell
94     * @param j column index of current cell
95     */
96    private void connectLeft(int i, int j) {
97        // Check if left cell exists and has compatible street type
98        // Street types 1, 4, 6 have connections to the right
99        if (j > 0 && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
100            // Union the two cells
101            parent[find(i * cols + j)] = find(i * cols + j - 1);
102        }
103    }
104
105    /**
106     * Attempts to connect current cell with the cell to its right.
107     * Connection is valid if right cell exists and has a street that connects to the left.
108     * 
109     * @param i row index of current cell
110     * @param j column index of current cell
111     */
112    private void connectRight(int i, int j) {
113        // Check if right cell exists and has compatible street type
114        // Street types 1, 3, 5 have connections to the left
115        if (j < cols - 1 && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
116            // Union the two cells
117            parent[find(i * cols + j)] = find(i * cols + j + 1);
118        }
119    }
120
121    /**
122     * Attempts to connect current cell with the cell above it.
123     * Connection is valid if upper cell exists and has a street that connects downward.
124     * 
125     * @param i row index of current cell
126     * @param j column index of current cell
127     */
128    private void connectUp(int i, int j) {
129        // Check if upper cell exists and has compatible street type
130        // Street types 2, 3, 4 have connections downward
131        if (i > 0 && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
132            // Union the two cells
133            parent[find(i * cols + j)] = find((i - 1) * cols + j);
134        }
135    }
136
137    /**
138     * Attempts to connect current cell with the cell below it.
139     * Connection is valid if lower cell exists and has a street that connects upward.
140     * 
141     * @param i row index of current cell
142     * @param j column index of current cell
143     */
144    private void connectDown(int i, int j) {
145        // Check if lower cell exists and has compatible street type
146        // Street types 2, 5, 6 have connections upward
147        if (i < rows - 1 && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
148            // Union the two cells
149            parent[find(i * cols + j)] = find((i + 1) * cols + j);
150        }
151    }
152}
153
1class Solution {
2public:
3    vector<int> parent;  // Union-Find parent array
4  
5    bool hasValidPath(vector<vector<int>>& grid) {
6        int rows = grid.size();
7        int cols = grid[0].size();
8      
9        // Initialize Union-Find structure
10        // Each cell is initially its own parent
11        parent.resize(rows * cols);
12        for (int i = 0; i < parent.size(); ++i) {
13            parent[i] = i;
14        }
15      
16        // Lambda function to connect current cell with left neighbor if compatible
17        auto connectLeft = [&](int row, int col) {
18            // Check if left neighbor exists and has right-facing connection
19            // Street types 1, 4, 6 have right-facing connections
20            if (col > 0 && (grid[row][col - 1] == 1 || 
21                           grid[row][col - 1] == 4 || 
22                           grid[row][col - 1] == 6)) {
23                parent[find(row * cols + col)] = find(row * cols + col - 1);
24            }
25        };
26      
27        // Lambda function to connect current cell with right neighbor if compatible
28        auto connectRight = [&](int row, int col) {
29            // Check if right neighbor exists and has left-facing connection
30            // Street types 1, 3, 5 have left-facing connections
31            if (col < cols - 1 && (grid[row][col + 1] == 1 || 
32                                   grid[row][col + 1] == 3 || 
33                                   grid[row][col + 1] == 5)) {
34                parent[find(row * cols + col)] = find(row * cols + col + 1);
35            }
36        };
37      
38        // Lambda function to connect current cell with upper neighbor if compatible
39        auto connectUp = [&](int row, int col) {
40            // Check if upper neighbor exists and has down-facing connection
41            // Street types 2, 3, 4 have down-facing connections
42            if (row > 0 && (grid[row - 1][col] == 2 || 
43                           grid[row - 1][col] == 3 || 
44                           grid[row - 1][col] == 4)) {
45                parent[find(row * cols + col)] = find((row - 1) * cols + col);
46            }
47        };
48      
49        // Lambda function to connect current cell with lower neighbor if compatible
50        auto connectDown = [&](int row, int col) {
51            // Check if lower neighbor exists and has up-facing connection
52            // Street types 2, 5, 6 have up-facing connections
53            if (row < rows - 1 && (grid[row + 1][col] == 2 || 
54                                   grid[row + 1][col] == 5 || 
55                                   grid[row + 1][col] == 6)) {
56                parent[find(row * cols + col)] = find((row + 1) * cols + col);
57            }
58        };
59      
60        // Process each cell in the grid
61        for (int row = 0; row < rows; ++row) {
62            for (int col = 0; col < cols; ++col) {
63                int streetType = grid[row][col];
64              
65                // Connect to neighbors based on street type
66                // Type 1: horizontal street (left-right)
67                if (streetType == 1) {
68                    connectLeft(row, col);
69                    connectRight(row, col);
70                }
71                // Type 2: vertical street (up-down)
72                else if (streetType == 2) {
73                    connectUp(row, col);
74                    connectDown(row, col);
75                }
76                // Type 3: L-shaped street (left-down)
77                else if (streetType == 3) {
78                    connectLeft(row, col);
79                    connectDown(row, col);
80                }
81                // Type 4: reversed L-shaped street (right-down)
82                else if (streetType == 4) {
83                    connectRight(row, col);
84                    connectDown(row, col);
85                }
86                // Type 5: reversed L-shaped street (left-up)
87                else if (streetType == 5) {
88                    connectLeft(row, col);
89                    connectUp(row, col);
90                }
91                // Type 6: L-shaped street (right-up)
92                else {
93                    connectRight(row, col);
94                    connectUp(row, col);
95                }
96            }
97        }
98      
99        // Check if start cell (0,0) and end cell (m-1,n-1) are connected
100        return find(0) == find(rows * cols - 1);
101    }
102  
103    // Find operation with path compression for Union-Find
104    int find(int x) {
105        if (parent[x] != x) {
106            parent[x] = find(parent[x]);  // Path compression
107        }
108        return parent[x];
109    }
110};
111
1let parent: number[] = [];  // Union-Find parent array
2
3function hasValidPath(grid: number[][]): boolean {
4    const rows: number = grid.length;
5    const cols: number = grid[0].length;
6  
7    // Initialize Union-Find structure
8    // Each cell is initially its own parent
9    parent = new Array(rows * cols);
10    for (let i = 0; i < parent.length; i++) {
11        parent[i] = i;
12    }
13  
14    // Function to connect current cell with left neighbor if compatible
15    const connectLeft = (row: number, col: number): void => {
16        // Check if left neighbor exists and has right-facing connection
17        // Street types 1, 4, 6 have right-facing connections
18        if (col > 0 && (grid[row][col - 1] === 1 || 
19                       grid[row][col - 1] === 4 || 
20                       grid[row][col - 1] === 6)) {
21            parent[find(row * cols + col)] = find(row * cols + col - 1);
22        }
23    };
24  
25    // Function to connect current cell with right neighbor if compatible
26    const connectRight = (row: number, col: number): void => {
27        // Check if right neighbor exists and has left-facing connection
28        // Street types 1, 3, 5 have left-facing connections
29        if (col < cols - 1 && (grid[row][col + 1] === 1 || 
30                               grid[row][col + 1] === 3 || 
31                               grid[row][col + 1] === 5)) {
32            parent[find(row * cols + col)] = find(row * cols + col + 1);
33        }
34    };
35  
36    // Function to connect current cell with upper neighbor if compatible
37    const connectUp = (row: number, col: number): void => {
38        // Check if upper neighbor exists and has down-facing connection
39        // Street types 2, 3, 4 have down-facing connections
40        if (row > 0 && (grid[row - 1][col] === 2 || 
41                       grid[row - 1][col] === 3 || 
42                       grid[row - 1][col] === 4)) {
43            parent[find(row * cols + col)] = find((row - 1) * cols + col);
44        }
45    };
46  
47    // Function to connect current cell with lower neighbor if compatible
48    const connectDown = (row: number, col: number): void => {
49        // Check if lower neighbor exists and has up-facing connection
50        // Street types 2, 5, 6 have up-facing connections
51        if (row < rows - 1 && (grid[row + 1][col] === 2 || 
52                               grid[row + 1][col] === 5 || 
53                               grid[row + 1][col] === 6)) {
54            parent[find(row * cols + col)] = find((row + 1) * cols + col);
55        }
56    };
57  
58    // Process each cell in the grid
59    for (let row = 0; row < rows; row++) {
60        for (let col = 0; col < cols; col++) {
61            const streetType: number = grid[row][col];
62          
63            // Connect to neighbors based on street type
64            // Type 1: horizontal street (left-right)
65            if (streetType === 1) {
66                connectLeft(row, col);
67                connectRight(row, col);
68            }
69            // Type 2: vertical street (up-down)
70            else if (streetType === 2) {
71                connectUp(row, col);
72                connectDown(row, col);
73            }
74            // Type 3: L-shaped street (left-down)
75            else if (streetType === 3) {
76                connectLeft(row, col);
77                connectDown(row, col);
78            }
79            // Type 4: reversed L-shaped street (right-down)
80            else if (streetType === 4) {
81                connectRight(row, col);
82                connectDown(row, col);
83            }
84            // Type 5: reversed L-shaped street (left-up)
85            else if (streetType === 5) {
86                connectLeft(row, col);
87                connectUp(row, col);
88            }
89            // Type 6: L-shaped street (right-up)
90            else {
91                connectRight(row, col);
92                connectUp(row, col);
93            }
94        }
95    }
96  
97    // Check if start cell (0,0) and end cell (m-1,n-1) are connected
98    return find(0) === find(rows * cols - 1);
99}
100
101// Find operation with path compression for Union-Find
102function find(x: number): number {
103    if (parent[x] !== x) {
104        parent[x] = find(parent[x]);  // Path compression
105    }
106    return parent[x];
107}
108

Time and Space Complexity

Time Complexity: O(m * n * Ξ±(m * n))

The algorithm uses Union-Find (Disjoint Set Union) to determine if there's a valid path from the top-left to bottom-right corner. Breaking down the time complexity:

  • The outer nested loops iterate through all cells: O(m * n)
  • For each cell, we perform at most 2 union operations (based on the street type)
  • Each union operation involves two find operations
  • With path compression, each find operation has an amortized time complexity of O(Ξ±(m * n)), where Ξ± is the inverse Ackermann function
  • The inverse Ackermann function grows extremely slowly and is practically constant (≀ 4) for all reasonable input sizes

Therefore, the overall time complexity is O(m * n * Ξ±(m * n)), which is effectively O(m * n) for practical purposes.

Space Complexity: O(m * n)

The space complexity consists of:

  • The parent array p which stores m * n elements: O(m * n)
  • The recursion stack for the find function with path compression: O(log(m * n)) in the worst case, but this is dominated by the parent array
  • Other variables use constant space: O(1)

The dominant factor is the parent array, giving us a total space complexity of O(m * n).

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

Common Pitfalls

1. Incorrect Bidirectional Connection Validation

A critical pitfall in this problem is assuming that if a cell has an opening in a certain direction, it can automatically connect to its neighbor. The connection requires both cells to have compatible openings facing each other.

Incorrect Implementation:

def connect_left(row: int, col: int) -> None:
    # WRONG: Only checking if left neighbor exists
    if col > 0:
        current_root = find(row * cols + col)
        left_root = find(row * cols + col - 1)
        parent[current_root] = left_root

Why it fails: If the current cell has street type 1 (horizontal), it has a left opening. But if the left neighbor has street type 2 (vertical), there's no right opening to connect back. The path would be invalid.

Correct Implementation:

def connect_left(row: int, col: int) -> None:
    # Must verify the neighbor has a compatible street type
    if col > 0 and grid[row][col - 1] in (1, 4, 6):
        current_root = find(row * cols + col)
        left_root = find(row * cols + col - 1)
        parent[current_root] = left_root

2. Forgetting Path Compression in Find Operation

Inefficient Implementation:

def find(x):
    # Without path compression - can lead to TLE
    while parent[x] != x:
        x = parent[x]
    return x

Optimized Implementation:

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # Path compression
    return parent[x]

Path compression ensures that future find operations are nearly O(1), preventing time limit exceeded errors on large grids.

3. Incorrect Cell-to-Index Mapping

Common Mistake:

# WRONG: Using i + j * rows instead of i * cols + j
cell_id = row + col * rows

Correct Mapping:

cell_id = row * cols + col

The correct formula ensures each cell gets a unique ID from 0 to (rows Γ— cols - 1). Using the wrong formula can cause cells to map to the same ID or out-of-bounds indices.

4. Not Handling Single Cell Grid

When the grid is 1Γ—1, the start and end are the same cell. The algorithm should return true regardless of the street type, since you're already at the destination.

Solution: The Union-Find approach handles this naturally since find(0) == find(0) will always be true.

5. Mixing Up Street Type Connections

It's easy to confuse which street types connect in which directions. For example:

  • Street type 3 connects left and down (not left and up)
  • Street type 5 connects left and up (not right and up)

Best Practice: Create a reference map or use clear comments:

# Street connections reference:
# 1: [left, right]
# 2: [up, down]
# 3: [left, down]
# 4: [right, down]
# 5: [left, up]
# 6: [right, up]

6. Union Operation Direction Matters for Optimization

While the direction of union doesn't affect correctness, always unioning in the same direction can create long chains:

Suboptimal:

parent[current_root] = left_root  # Always making left the parent

Better (with rank/size optimization):

# Union by rank or size to keep trees balanced
if rank[current_root] < rank[left_root]:
    parent[current_root] = left_root
elif rank[current_root] > rank[left_root]:
    parent[left_root] = current_root
else:
    parent[left_root] = current_root
    rank[current_root] += 1

Though not implemented in the base solution for simplicity, this optimization can improve performance on very large grids.

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

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

DFS Fundamentals

https assets algo monster 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 As the name suggests

BFS Fundamentals

https assets algo monster 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 Breadth First Search BFS

DSU/Union Find Fundamentals

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

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More