We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if There is a Valid Path in a Grid

Number: 1507

Difficulty: Medium

Paid? No

Companies: Robinhood

Problem Description

Given an m x n grid where each cell is one of six types representing streets that connect two directions, determine if there is a valid path from the upper-left cell (0, 0) to the bottom-right cell (m - 1, n - 1). The path must follow the directions allowed by the type of each street, and movement between cells is only possible if both cells provide a road connection between them.

Key Insights

  • Each cell type (from 1 to 6) defines specific allowed directions where a move is possible.
  • The movement is only valid if the neighbor cell supports a connection back to the current cell.
  • A mapping from cell type to allowed move directions simplifies determining reachable neighbors.
  • Both Depth-First Search (DFS) and Breadth-First Search (BFS) can be used to explore the grid.
  • Use a visited set (or equivalent) to avoid cycles and redundant work.

Space and Time Complexity

Time Complexity: O(m * n) - In the worst case, every cell is visited once. Space Complexity: O(m * n) - For the queue/stack and visited set used during traversal.

Solution

We can solve the problem using a BFS (or DFS) approach. First, define a mapping from each cell type to its allowed 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

Also, define the opposites of these directions to ensure that when moving from cell A to B, cell B’s type must have the corresponding reverse direction to connect back to A.

Start from cell (0, 0) and explore allowed directions. For each move:

  1. Validate that the new cell is within bounds.
  2. Check if the neighbor cell's type allows a connection back in the opposite direction.
  3. If a valid connection exists, add the cell to the queue (or stack) for further exploration.
  4. Continue until reaching (m - 1, n - 1) or exhausting all possibilities.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with detailed comments.

from collections import deque

def hasValidPath(grid):
    m, n = len(grid), len(grid[0])
    
    # Mapping from cell type to allowed directions (dx, dy)
    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
    }
    
    # Mapping for each direction to its opposite direction for connectivity check
    opposite = {
        (0, -1): (0, 1),
        (0, 1): (0, -1),
        (-1, 0): (1, 0),
        (1, 0): (-1, 0)
    }
    
    # BFS using deque
    queue = deque([(0, 0)])
    visited = set([(0, 0)])
    
    while queue:
        x, y = queue.popleft()
        # Check if reached destination
        if x == m - 1 and y == n - 1:
            return True
        
        # Explore allowed directions from current cell based on its type
        for dx, dy in directions[grid[x][y]]:
            nx, ny = x + dx, y + dy
            # Check bounds and if already visited
            if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited:
                # Check if neighbor cell has a connection back
                if opposite[(dx, dy)] in directions[grid[nx][ny]]:
                    visited.add((nx, ny))
                    queue.append((nx, ny))
    
    return False

# Example usage:
# print(hasValidPath([[2,4,3],[6,5,2]]))  # Expected output: True
← Back to All Questions