Check if There is a Valid Path in a Grid - Practice Coding Problems

Check if There is a Valid Path in a Grid - Problem

You are given an m x n grid. Each cell of grid represents a street. The street of grid[i][j] can be:

1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Input & Output

Example 1 — Valid Path Exists

$ Input: grid = [[2,4,3],[6,5,2]]

› Output: true

💡 Note: Path exists: (0,0) → (1,0) → (1,1) → (1,2). Street 2 at (0,0) connects down to street 6 at (1,0), which connects up. Then street 6 connects right to street 5 at (1,1), and so on.

Example 2 — No Valid Path

$ Input: grid = [[1,2,1],[1,2,1]]

› Output: false

💡 Note: Street 1 at (0,0) only connects left-right, but there's no valid connection downward. Street 2 at (0,1) connects up-down but (0,0) doesn't connect right.

Example 3 — Single Cell

$ Input: grid = [[6]]

› Output: true

💡 Note: Start and end are the same cell (0,0), so the path is valid by default.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Each number represents a street type with specific connections

Validate Connections

Check if adjacent cells can connect to each other

Find Path

Use DFS/BFS to find valid route from (0,0) to bottom-right

Key Takeaway

🎯 Key Insight: Street connections must be bidirectional - both cells must connect to each other for valid movement

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is that each street type has specific connection rules - you must validate that both the current cell connects in a direction AND the adjacent cell connects back. Best approach is DFS or BFS with proper connection validation. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ BFS Shortest Path Search	O(m×n)	O(m×n)	Use breadth-first search to find the shortest valid path from start to destination
DFS with Connection Validation	O(m×n)	O(m×n)	Use depth-first search to explore all possible paths while validating street connections

BFS Shortest Path Search — Algorithm Steps

Initialize queue with starting position (0,0)
For each cell, check all valid adjacent connections
Add valid neighbors to queue if not visited
Continue until destination is reached or queue is empty

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Queue

Start with (0,0) in queue, mark as visited

Process Level

Check all valid connections from current level

Expand Search

Add valid neighbors to queue for next level

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int row, col;
} Point;

typedef struct {
    Point* data;
    int front, rear, size, capacity;
} Queue;

Queue* createQueue(int capacity) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->data = (Point*)malloc(capacity * sizeof(Point));
    q->front = 0;
    q->rear = 0;
    q->size = 0;
    q->capacity = capacity;
    return q;
}

void enqueue(Queue* q, Point p) {
    q->data[q->rear] = p;
    q->rear = (q->rear + 1) % q->capacity;
    q->size++;
}

Point dequeue(Queue* q) {
    Point p = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return p;
}

bool connections[7][4] = {
    {},
    {false, true, false, true},   // 1: left-right
    {true, false, true, false},   // 2: up-down
    {false, false, true, true},   // 3: left-down
    {false, true, true, false},   // 4: right-down
    {true, false, false, true},   // 5: left-up
    {true, true, false, false}    // 6: right-up
};

int directions[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

bool solution(int** grid, int m, int n) {
    if (m == 0 || n == 0) return false;
    
    bool** visited = (bool**)malloc(m * sizeof(bool*));
    for (int i = 0; i < m; i++) {
        visited[i] = (bool*)calloc(n, sizeof(bool));
    }
    
    Queue* queue = createQueue(m * n);
    Point start = {0, 0};
    enqueue(queue, start);
    visited[0][0] = true;
    
    while (queue->size > 0) {
        Point curr = dequeue(queue);
        
        if (curr.row == m - 1 && curr.col == n - 1) {
            // Cleanup
            for (int i = 0; i < m; i++) free(visited[i]);
            free(visited);
            free(queue->data);
            free(queue);
            return true;
        }
        
        int currentStreet = grid[curr.row][curr.col];
        
        for (int i = 0; i < 4; i++) {
            int newRow = curr.row + directions[i][0];
            int newCol = curr.col + directions[i][1];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
                if (connections[currentStreet][i]) {
                    int adjacentStreet = grid[newRow][newCol];
                    int oppositeDirection = (i + 2) % 4;
                    
                    if (connections[adjacentStreet][oppositeDirection]) {
                        visited[newRow][newCol] = true;
                        Point next = {newRow, newCol};
                        enqueue(queue, next);
                    }
                }
            }
        }
    }
    
    // Cleanup
    for (int i = 0; i < m; i++) free(visited[i]);
    free(visited);
    free(queue->data);
    free(queue);
    
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for demo
    int m = 3, n = 4;
    int** grid = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    int example[3][4] = {{2,4,3},{6,5,2},{1,2,1}};
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            grid[i][j] = example[i][j];
        }
    }
    
    bool result = solution(grid, m, n);
    printf(result ? "true\n" : "false\n");
    
    for (int i = 0; i < m; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Each cell is visited at most once during BFS traversal

✓ Linear Growth

Space Complexity

O(m×n)

Queue can contain up to all grid cells, plus visited array

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS Shortest Path Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler