Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1391. Check if There is a Valid Path in a Grid - Leetcode Solution

Code Implementation

class Solution:
    # Directions for each street type
    # 1: left<->right, 2: up<->down, 3: left<->down, 4: right<->down, 5: left<->up, 6: right<->up
    STREET_DIRS = {
        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))]
    }

    # For each street type, which directions you can go from here
    STREET_MOVES = {
        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)]
    }

    # For each direction, which street types can connect from that direction
    DIR_TO_STREET = {
        (0, 1): [1, 4, 6],
        (0, -1): [1, 3, 5],
        (1, 0): [2, 3, 4],
        (-1, 0): [2, 5, 6]
    }

    def hasValidPath(self, grid):
        from collections import deque
        m, n = len(grid), len(grid[0])
        visited = [[False]*n for _ in range(m)]
        queue = deque()
        queue.append((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 self.STREET_MOVES[grid[x][y]]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                    # Check if the next cell's street connects back to (x, y)
                    if (-dx, -dy) in self.STREET_MOVES[grid[nx][ny]]:
                        visited[nx][ny] = True
                        queue.append((nx, ny))
        return False
      
class Solution {
public:
    vector<vector<pair<int, int>>> streetMoves = {
        {},
        {{0, -1}, {0, 1}},   // 1
        {{-1, 0}, {1, 0}},   // 2
        {{0, -1}, {1, 0}},   // 3
        {{0, 1}, {1, 0}},    // 4
        {{0, -1}, {-1, 0}},  // 5
        {{0, 1}, {-1, 0}}    // 6
    };

    bool hasValidPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        queue<pair<int, int>> q;
        q.push({0, 0});
        visited[0][0] = true;

        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            if (x == m - 1 && y == n - 1) return true;
            for (auto [dx, dy] : streetMoves[grid[x][y]]) {
                int nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    for (auto [rdx, rdy] : streetMoves[grid[nx][ny]]) {
                        if (nx + rdx == x && ny + rdy == y) {
                            visited[nx][ny] = true;
                            q.push({nx, ny});
                            break;
                        }
                    }
                }
            }
        }
        return false;
    }
};
      
class Solution {
    private static final int[][][] moves = {
        {},
        {{0, -1}, {0, 1}},   // 1
        {{-1, 0}, {1, 0}},   // 2
        {{0, -1}, {1, 0}},   // 3
        {{0, 1}, {1, 0}},    // 4
        {{0, -1}, {-1, 0}},  // 5
        {{0, 1}, {-1, 0}}    // 6
    };

    public boolean hasValidPath(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];
            if (x == m - 1 && y == n - 1) return true;
            for (int[] move : moves[grid[x][y]]) {
                int nx = x + move[0], ny = y + move[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    for (int[] back : moves[grid[nx][ny]]) {
                        if (nx + back[0] == x && ny + back[1] == y) {
                            visited[nx][ny] = true;
                            queue.offer(new int[]{nx, ny});
                            break;
                        }
                    }
                }
            }
        }
        return false;
    }
}
      
var hasValidPath = function(grid) {
    const m = grid.length, n = grid[0].length;
    const moves = [
        [],
        [[0, -1], [0, 1]],    // 1
        [[-1, 0], [1, 0]],    // 2
        [[0, -1], [1, 0]],    // 3
        [[0, 1], [1, 0]],     // 4
        [[0, -1], [-1, 0]],   // 5
        [[0, 1], [-1, 0]]     // 6
    ];
    const visited = Array.from({length: m}, () => Array(n).fill(false));
    const queue = [[0, 0]];
    visited[0][0] = true;

    while (queue.length > 0) {
        const [x, y] = queue.shift();
        if (x === m - 1 && y === n - 1) return true;
        for (const [dx, dy] of moves[grid[x][y]]) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                for (const [rdx, rdy] of moves[grid[nx][ny]]) {
                    if (nx + rdx === x && ny + rdy === y) {
                        visited[nx][ny] = true;
                        queue.push([nx, ny]);
                        break;
                    }
                }
            }
        }
    }
    return false;
};

Problem Description

Given a m x n grid where each cell has a value from 1 to 6 representing a street type, determine if there is a valid path from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1). Each street type allows movement only in certain directions and only connects to specific types in adjacent cells. The path must follow the street rules, and you cannot revisit cells.

  • Each street type connects only to certain adjacent street types and directions.
  • You may only move to a neighbor if the connection is valid in both directions (from and to).
  • There may be only one valid solution or none; you cannot reuse cells.

Thought Process

At first glance, the problem seems similar to finding a path in a maze. However, the twist is that not all adjacent cells are reachable; the type of street in each cell determines which directions you can move and which neighbor types you can connect to. A brute-force approach would try every possible path, but this quickly becomes inefficient as the grid grows.

The key insight is that we don't need to try every permutation of moves. Instead, we can use a systematic search (like BFS or DFS) while checking at each step if the next cell is a valid continuation based on street types. To avoid cycles and redundant work, we keep track of visited cells.

By encoding the allowed moves and their compatibility, we can efficiently check at each step if a move is possible.

Solution Approach

Let's break down the steps to solve the problem efficiently:

  1. Represent Allowed Moves:
    • For each street type (1-6), define which directions you can move (e.g., type 1 allows left and right).
    • For each direction, also know which street types in the neighbor cell can connect back (so the path is continuous).
  2. BFS Traversal:
    • Use a queue to explore the grid starting from (0, 0).
    • For each cell, try all valid moves based on its street type.
    • For each move, check if the neighbor cell is within bounds, not yet visited, and its street type allows a connection back.
    • If yes, mark it visited and add it to the queue.
  3. Early Exit:
    • If you reach the bottom-right cell, return True immediately.
  4. No Path:
    • If the queue is exhausted without reaching the target, return False.
  5. Data Structures:
    • We use a visited matrix to avoid revisiting cells (prevents cycles and redundant work).
    • All lookups (for moves and compatibility) are done using arrays or hash maps for constant-time access.

This approach ensures we only visit each cell at most once, and each move is checked efficiently.

Example Walkthrough

Consider the input grid: 

    [[2,4,3],
     [6,5,2]]
  1. Start at (0,0) with street type 2 (vertical). Allowed moves: up or down.
  2. Move down to (1,0), which is street type 6. Check if street 6 connects up (it does). Mark (1,0) as visited.
  3. From (1,0) (type 6), possible moves: right or up. Up leads back to (0,0) (already visited), so try right to (1,1) (type 5).
  4. Check if (1,1) (type 5) connects left (it does). Mark (1,1) as visited.
  5. From (1,1) (type 5), moves: left or up. Up to (0,1) (type 4).
  6. Check if (0,1) (type 4) connects down (it does). Mark (0,1) as visited.
  7. From (0,1) (type 4), moves: right or down. Right to (0,2) (type 3).
  8. Check if (0,2) (type 3) connects left (it does). Mark (0,2) as visited.
  9. From (0,2) (type 3), moves: left or down. Down to (1,2) (type 2).
  10. Check if (1,2) (type 2) connects up (it does). Mark (1,2) as visited.
  11. (1,2) is the bottom-right cell. Path found!

At each step, we only move to cells where the street types connect in both directions.

Time and Space Complexity

  • Brute-force:
    • Would try all possible paths, leading to exponential time: O(2^(m*n)) in the worst case.
  • Optimized (BFS/DFS):
    • Each cell is visited at most once: O(m*n) time.
    • Each move checks a constant number of directions (max 2 per cell).
    • Space complexity is O(m*n) for the visited matrix and queue.
  • Why:
    • Because we never revisit cells and only enqueue valid moves, the total number of operations is proportional to the number of cells.

Summary

The problem is solved efficiently by representing street connections and using BFS to explore the grid, always checking that each move is valid in both directions. By marking cells as visited, we avoid cycles and redundant work. The solution is elegant because it leverages the structure of the problem (street types and their connections) and standard graph traversal techniques, ensuring a linear time solution relative to the grid size.