Check if There is a Valid Path in a Grid

Medium
1527.

Check if There is a Valid Path in a Grid

Check if There is a Valid Path in a Grid is a medium coding problem on depth-first search, matrix and breadth-first search, asked in Amazon and Google interviews.

Every cell of an m x n grid holds one street piece, given as a number from 1 to 6:

  • 1 joins the left and right neighbours.
  • 2 joins the upper and lower neighbours.
  • 3 joins the left and lower neighbours.
  • 4 joins the right and lower neighbours.
  • 5 joins the left and upper neighbours.
  • 6 joins the right and upper neighbours.

You may step from a cell to an adjacent one only if the street in your cell opens toward that neighbour and the neighbour's street opens back toward you. Streets cannot be rotated.

Starting at the top-left cell (0, 0), return true if the streets lead you to the bottom-right cell (m - 1, n - 1).

Example 1

Input
grid = [[4,1,3],[6,1,5]]
Output
true
Explanation
(0,0) opens right into the straight piece at (0,1), then (0,2) turns down into (1,2), which opens upward.

Example 2

Input
grid = [[1,2],[2,1]]
Output
false
Explanation
(0,0) opens only left and right, but (0,1) is a vertical piece that does not open to the left.

Example 3

Input
grid = [[5]]
Output
true
Explanation
The start is already the destination.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • 1 <= grid[i][j] <= 6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {boolean}
 */
var hasValidPath = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check if There is a Valid Path in a Grid — Solution

Check if There is a Valid Path in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Check if There is a Valid Path in a Grid is a medium coding problem on depth-first search, matrix and breadth-first search, asked in Amazon and Google interviews.

Problem statement

Every cell of an m x n grid holds one street piece, given as a number from 1 to 6:

  • 1 joins the left and right neighbours.
  • 2 joins the upper and lower neighbours.
  • 3 joins the left and lower neighbours.
  • 4 joins the right and lower neighbours.
  • 5 joins the left and upper neighbours.
  • 6 joins the right and upper neighbours.

You may step from a cell to an adjacent one only if the street in your cell opens toward that neighbour and the neighbour's street opens back toward you. Streets cannot be rotated.

Starting at the top-left cell (0, 0), return true if the streets lead you to the bottom-right cell (m - 1, n - 1).

Example 1

Input: grid = [[4,1,3],[6,1,5]]
Output: true
Explanation: (0,0) opens right into the straight piece at (0,1), then (0,2) turns down into (1,2), which opens upward.

Example 2

Input: grid = [[1,2],[2,1]]
Output: false
Explanation: (0,0) opens only left and right, but (0,1) is a vertical piece that does not open to the left.

Example 3

Input: grid = [[5]]
Output: true
Explanation: The start is already the destination.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • 1 <= grid[i][j] <= 6

Hints for Check if There is a Valid Path in a Grid

  1. Hint 1

    Model each street type as the set of directions it opens toward.

  2. Hint 2

    A move between neighbours is allowed only when both cells open toward each other — check the neighbour for the opposite direction.

  3. Hint 3

    Run a BFS or DFS from (0, 0) using that rule and report whether (m − 1, n − 1) is visited.

How to solve Check if There is a Valid Path in a Grid

The grid is a graph whose edges exist only between neighbouring cells that open toward each other; the question is plain reachability from the top-left to the bottom-right.

Approach

  1. Encode each street type as a 4-bit mask of openings (up, right, down, left).
  2. BFS from (0, 0). From cell (r, c) try every direction d its mask contains.
  3. Move to the neighbour if it is inside the grid, unvisited, and its mask contains the opposite direction (d + 2) mod 4.
  4. Return true as soon as (m − 1, n − 1) is reached; false when the queue empties.

Why it works

Two cells are connected by a usable street exactly when both openings face each other, so the mutual-opening test reproduces the street graph precisely. BFS visits every cell reachable in that graph, so the destination is reached if and only if a valid path exists.

Complexity

  • Time — O(m · n)
  • Space — O(m · n)

Pitfalls

  • Checking only the current cell's opening lets you walk into a piece that does not connect back.
  • A 1 × 1 grid is trivially true.
  • Paths may wind up and left as well as down and right — do not restrict the search to monotone moves.

Reference solution

Python

from typing import List
from collections import deque

def hasValidPath(grid: List[List[int]]) -> bool:
    m, n = len(grid), len(grid[0])
    masks = [0, 10, 5, 12, 6, 9, 3]
    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]
    seen = [[False] * n for _ in range(m)]
    seen[0][0] = True
    q = deque([(0, 0)])
    while q:
        r, c = q.popleft()
        if r == m - 1 and c == n - 1:
            return True
        mk = masks[grid[r][c]]
        for d in range(4):
            if not (mk >> d) & 1:
                continue
            nr, nc = r + dr[d], c + dc[d]
            if nr < 0 or nr >= m or nc < 0 or nc >= n or seen[nr][nc]:
                continue
            if not (masks[grid[nr][nc]] >> ((d + 2) % 4)) & 1:
                continue
            seen[nr][nc] = True
            q.append((nr, nc))
    return False

Java

public static boolean hasValidPath(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] masks = {0, 10, 5, 12, 6, 9, 3};
    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    boolean[] seen = new boolean[m * n];
    int[] queue = new int[m * n];
    int head = 0, tail = 0;
    queue[tail++] = 0;
    seen[0] = true;
    while (head < tail) {
        int id = queue[head++];
        int r = id / n, c = id % n;
        if (r == m - 1 && c == n - 1) return true;
        int mk = masks[grid[r][c]];
        for (int d = 0; d < 4; d++) {
            if ((mk & (1 << d)) == 0) continue;
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if ((masks[grid[nr][nc]] & (1 << ((d + 2) % 4))) == 0) continue;
            int nid = nr * n + nc;
            if (!seen[nid]) { seen[nid] = true; queue[tail++] = nid; }
        }
    }
    return false;
}

C++

bool hasValidPath(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int masks[7] = {0, 10, 5, 12, 6, 9, 3};
    int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
    vector<char> seen(m * n, 0);
    vector<int> queue;
    queue.push_back(0);
    seen[0] = 1;
    for (size_t h = 0; h < queue.size(); h++) {
        int r = queue[h] / n, c = queue[h] % n;
        if (r == m - 1 && c == n - 1) return true;
        int mk = masks[grid[r][c]];
        for (int d = 0; d < 4; d++) {
            if ((mk & (1 << d)) == 0) continue;
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if ((masks[grid[nr][nc]] & (1 << ((d + 2) % 4))) == 0) continue;
            int nid = nr * n + nc;
            if (!seen[nid]) { seen[nid] = 1; queue.push_back(nid); }
        }
    }
    return false;
}

JavaScript

var hasValidPath = function(grid) {
    var m = grid.length, n = grid[0].length;
    var masks = [0, 10, 5, 12, 6, 9, 3];
    var dr = [-1, 0, 1, 0], dc = [0, 1, 0, -1];
    var seen = [];
    for (var i = 0; i < m * n; i++) seen.push(false);
    var queue = [0];
    seen[0] = true;
    for (var h = 0; h < queue.length; h++) {
        var r = Math.floor(queue[h] / n), c = queue[h] % n;
        if (r === m - 1 && c === n - 1) return true;
        var mk = masks[grid[r][c]];
        for (var d = 0; d < 4; d++) {
            if ((mk & (1 << d)) === 0) continue;
            var nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if ((masks[grid[nr][nc]] & (1 << ((d + 2) % 4))) === 0) continue;
            var id = nr * n + nc;
            if (!seen[id]) { seen[id] = true; queue.push(id); }
        }
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Matrix and Grid Traversal