Check if There is a Valid Path in a Grid: Pipe Connection BFS

You are given an m x n grid where each cell contains one of six street types. Each type connects exactly two directions:

• Type 1: left and right
• Type 2: up and down
• Type 3: left and down
• Type 4: right and down
• Type 5: left and up
• Type 6: right and up

You can walk from one cell to an adjacent cell only if both cells have streets that connect to each other at their shared edge. Return whether there is a valid path from (0, 0) to (m-1, n-1).

This is LeetCode 1391: Check if There is a Valid Path in a Grid.

Why this problem matters

Grid traversal is a classic BFS/DFS pattern, but this problem adds a twist: you cannot simply move to any adjacent cell. You need to verify that both cells agree on the connection. This "mutual handshake" constraint shows up in real-world scenarios like pipe-fitting puzzles, network topology validation, and circuit board routing. Solving it teaches you how to layer domain-specific constraints on top of standard graph traversal.

The key insight

Map each street type to the set of directions it connects. When you try to move from cell A to cell B, two conditions must hold: cell A must have an opening toward B, and cell B must have an opening back toward A. If either side is missing, the connection is invalid and you skip that neighbor.

For example, if you are at cell (0, 0) with street type 2 (connects up and down), you can attempt to move down to (1, 0). But (1, 0) must also connect upward for the move to be legal. If (1, 0) has type 6 (connects right and up), the "up" opening matches your "down," so the link is valid.

The solution

from collections import deque

def has_valid_path(grid: list[list[int]]) -> bool:
    rows, cols = len(grid), len(grid[0])
    if rows == 1 and cols == 1:
        return True

    directions = {
        1: ["left", "right"],
        2: ["up", "down"],
        3: ["left", "down"],
        4: ["right", "down"],
        5: ["left", "up"],
        6: ["right", "up"],
    }

    opposite = {
        "left": "right",
        "right": "left",
        "up": "down",
        "down": "up",
    }

    delta = {
        "left": (0, -1),
        "right": (0, 1),
        "up": (-1, 0),
        "down": (1, 0),
    }

    visited = set()
    visited.add((0, 0))
    queue = deque([(0, 0)])

    while queue:
        r, c = queue.popleft()
        for d in directions[grid[r][c]]:
            dr, dc = delta[d]
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                if opposite[d] in directions[grid[nr][nc]]:
                    if nr == rows - 1 and nc == cols - 1:
                        return True
                    visited.add((nr, nc))
                    queue.append((nr, nc))

    return (rows - 1, cols - 1) in visited

The code starts by mapping each of the six street types to the directions it opens. It also defines the opposite of each direction, because moving "down" from one cell requires the neighbor to open "up."

BFS begins at (0, 0). For each cell we dequeue, we iterate over the directions that cell's street type supports. For each direction, we compute the neighbor coordinates. If the neighbor is in bounds, unvisited, and its street type includes the opposite direction, the connection is mutual and we enqueue the neighbor.

The early return when we reach (rows - 1, cols - 1) is an optimization. If BFS finishes without hitting the goal, the final check on the visited set returns False.

Visual walkthrough

Notice how each step verifies that the current cell opens in a direction and the neighbor opens in the opposite direction. The BFS only follows edges where both sides connect. This is what makes a "valid path" in this problem: every pair of adjacent cells on the path must share a mutual opening.

Complexity analysis

Time is O(m * n). Each cell is visited at most once because we mark it in the visited set before enqueueing. For each cell, we check at most two directions (each street type connects exactly two), so the work per cell is constant.

Space is O(m * n) for the visited set and the BFS queue. In the worst case, every cell is reachable, so both structures grow to the size of the grid.

The building blocks

1. Direction mapping for each street type

directions = {
    1: ["left", "right"],
    2: ["up", "down"],
    3: ["left", "down"],
    4: ["right", "down"],
    5: ["left", "up"],
    6: ["right", "up"],
}

This mapping is the foundation. Every street type connects exactly two directions, and this dictionary encodes that knowledge. When you are at a cell, you look up its type to know which neighbors you can attempt to reach. This pattern of encoding graph connectivity as a lookup table shows up in many constraint-based traversal problems.

2. Mutual connection check

opposite = {"left": "right", "right": "left", "up": "down", "down": "up"}

for d in directions[grid[r][c]]:
    dr, dc = delta[d]
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        if opposite[d] in directions[grid[nr][nc]]:
            pass

This is the "handshake." You move in direction d from the current cell, then check if the neighbor's street type includes opposite[d]. Both cells must agree on the connection. This bidirectional validation pattern applies to any problem where edges have directional constraints, such as one-way streets, directed graphs encoded in grids, or tile-matching puzzles.

Edge cases

• Single cell grid: (0, 0) is already the goal. Return True immediately.
• Start cell points away from all reachable neighbors: if the street at (0, 0) does not open toward any in-bounds neighbor that connects back, BFS never enqueues anything. Return False.
• Large grid, all type 1: every cell connects left-right. Only the first row has a valid horizontal path. If the grid has more than one row, the goal at (m-1, n-1) is unreachable.
• Goal cell does not connect toward the path: even if BFS reaches a neighbor of the goal, the goal cell must open back toward that neighbor. A mismatch here means no valid path.
• Winding path through all six types: the BFS handles arbitrary combinations of street types. It does not assume any particular path shape.

From understanding to recall

You now understand how to layer directional constraints on top of BFS. The direction map and the mutual connection check are the two pieces that distinguish this problem from a vanilla grid traversal. But during a timed interview, it is easy to forget whether you need to check the current cell's direction, the neighbor's direction, or both. The answer is both, and the "opposite" dictionary is how you enforce it.

Spaced repetition locks this in. You practice writing the direction map, the opposite lookup, and the connection check from memory. After a few sessions, the bidirectional validation pattern becomes automatic. You see "cells must connect at shared edges" and the template writes itself.

Related posts

• Number of Islands - The foundational grid BFS/DFS traversal problem
• Rotting Oranges - Multi-source BFS on a grid with state propagation
• Pacific Atlantic Water Flow - Grid traversal with directional constraints

CodeBricks breaks this problem into its direction-mapping and mutual-connection building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a constrained grid traversal problem shows up in your interview, you do not hesitate. You just write it.