LeetCode 1391 - Check if There is a Valid Path in a Grid

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

The problem presents a grid where each cell represents a street segment with a specific orientation, denoted by a number from 1 to 6. Each number encodes which directions the street in that cell connects to neighboring cells. For example, 1 connects left and right, while 2 connects up and down, and the other numbers represent corners that connect two orthogonal directions. The task is to determine if there is a valid path from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1) following these street connections. You are not allowed to modify the grid.

The input is a 2D array of size m x n, with constraints up to 300 x 300, which indicates that any solution must be efficient enough to handle a grid of up to 90,000 cells. A naive solution that explores every path recursively without pruning could be too slow. The output is a boolean indicating whether a valid path exists.

Important edge cases include:

A single cell grid (1x1) which should trivially return true.
Grids with dead ends where the initial street does not connect to any valid neighbor.
Narrow corridors, like 1 x n or m x 1, which test boundary connectivity.

Understanding the street connections and their allowed movements is crucial. The mapping of street types to valid neighbor connections must be handled carefully.

Approaches

The brute-force approach would be to perform a recursive depth-first search (DFS) starting from (0,0), exploring every possible move according to the current street type. This guarantees correctness because it will eventually explore all valid paths, but it is inefficient due to repeated exploration and the potential exponential number of paths in larger grids.

The optimal approach is to use either DFS or BFS with connectivity constraints. For each cell, we only move to neighbors that have a street segment connecting back to the current cell. This ensures we do not traverse invalid paths and prevents revisiting cells using a visited set. Union-Find could also be applied by connecting adjacent compatible streets and checking if the start and end are connected, but DFS/BFS is simpler and more intuitive for path traversal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(m*n))	O(m*n)	Recursively explores all paths, exponential in grid size
Optimal (DFS/BFS)	O(m*n)	O(m*n)	Visits each cell at most once, checks connectivity constraints

Algorithm Walkthrough

Define a mapping for each street type to the directions it connects. For example, 1 connects left and right, 2 connects up and down, etc. Each direction can be represented as (dx, dy) coordinates.
Initialize a visited matrix of the same size as grid to track which cells have already been explored.
Start BFS (or DFS) from (0, 0). Add it to the queue (for BFS) or call DFS recursively.
For each current cell (x, y), iterate over its possible connected directions according to its street type.
For each potential move (nx, ny) = (x+dx, y+dy), check:

It is within the grid boundaries.
The neighbor’s street type connects back to the current cell.
The neighbor has not been visited.

If all conditions are satisfied, mark (nx, ny) as visited and enqueue it for further exploration.
Continue until the queue is empty or the bottom-right cell (m-1, n-1) is reached.
If (m-1, n-1) is visited by the end of traversal, return true; otherwise, return false.

Why it works: Each move only proceeds along streets that are mutually connected, ensuring that no invalid paths are explored. By marking visited cells, we prevent infinite loops or revisiting the same path. BFS guarantees that we explore all reachable cells efficiently, and the presence of the end cell in the visited set confirms a valid path.

Python Solution

from typing import List
from collections import deque

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        if not grid:
            return False
        
        m, n = len(grid), len(grid[0])
        
        # Mapping street type to valid moves: (dx, dy) pairs
        directions = {
            1: [(0, -1), (0, 1)],     # left, right
            2: [(-1, 0), (1, 0)],     # up, down
            3: [(0, -1), (1, 0)],     # left, down
            4: [(0, 1), (1, 0)],      # right, down
            5: [(0, -1), (-1, 0)],    # left, up
            6: [(0, 1), (-1, 0)],     # right, up
        }
        
        # Reverse mapping to check if neighbor connects back
        opposite = {
            (0, -1): (0, 1),
            (0, 1): (0, -1),
            (-1, 0): (1, 0),
            (1, 0): (-1, 0),
        }
        
        visited = [[False] * n for _ in range(m)]
        queue = deque([(0, 0)])
        visited[0][0] = True
        
        while queue:
            x, y = queue.popleft()
            if x == m - 1 and y == n - 1:
                return True
            for dx, dy in directions[grid[x][y]]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                    if opposite[(dx, dy)] in directions[grid[nx][ny]]:
                        visited[nx][ny] = True
                        queue.append((nx, ny))
        return False

The Python implementation first defines mappings for movement directions and their opposites to ensure mutual street connectivity. It then initializes BFS with the start cell and explores each neighbor according to the street rules. The visited matrix ensures we do not revisit cells. The algorithm returns true if the bottom-right cell is reached.

Go Solution

package main

func hasValidPath(grid [][]int) bool {
    m, n := len(grid), len(grid[0])
    
    directions := map[int][][]int{
        1: {{0, -1}, {0, 1}},
        2: {{-1, 0}, {1, 0}},
        3: {{0, -1}, {1, 0}},
        4: {{0, 1}, {1, 0}},
        5: {{0, -1}, {-1, 0}},
        6: {{0, 1}, {-1, 0}},
    }
    
    opposite := map[[2]int][2]int{
        {0, -1}: {0, 1},
        {0, 1}: {0, -1},
        {-1, 0}: {1, 0},
        {1, 0}: {-1, 0},
    }
    
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    
    queue := [][2]int{{0, 0}}
    visited[0][0] = true
    
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        x, y := curr[0], curr[1]
        if x == m-1 && y == n-1 {
            return true
        }
        for _, dir := range directions[grid[x][y]] {
            nx, ny := x+dir[0], y+dir[1]
            if nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] {
                if _, ok := directions[grid[nx][ny]]; ok {
                    for _, ndir := range directions[grid[nx][ny]] {
                        if ndir[0] == opposite[[2]int{dir[0], dir[1}][0]] && ndir[1] == opposite[[2]int{dir[0], dir[1}][1]] {
                            visited[nx][ny] = true
                            queue = append(queue, [2]int{nx, ny})
                            break
                        }
                    }
                }
            }
        }
    }
    
    return false
}

In Go, the BFS queue is implemented as a slice of integer pairs. The logic for direction mapping and checking connectivity is identical to the Python solution. Go requires explicit initialization of slices and nested loops to check for matching opposite directions.

Worked Examples

Example 1:

grid = [[2,4,3],
        [6,5,2]]

Start at (0,0), type 2 (up/down), moves to (1,0) (down), type 6 connects up (matches), then move to (1,1) type 5 (left/up) connects left, finally move to (1,2) type 2 (up/down), bottom-right reached. Returns true.

Example 2:

grid = [[1,2,1