Shortest Path in Binary Matrix - Practice Coding Problems

Shortest Path in Binary Matrix - Problem

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Input & Output

Example 1 — Basic Path Found

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

› Output: 4

💡 Note: The shortest clear path is (0,0) → (0,1) → (0,2) → (1,2) → (2,2). Path length is 4.

Example 2 — No Path Possible

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

› Output: -1

💡 Note: No clear path exists from top-left to bottom-right due to blocking 1s.

Example 3 — Single Cell

$ Input: grid = [[0]]

› Output: 1

💡 Note: Start and end are the same cell (0,0). Path length is 1.

Constraints

n == grid.length
n == grid[i].length
1 ≤ n ≤ 100
grid[i][j] is 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with 0s (clear) and 1s (blocked)

BFS Exploration

Level-by-level search with 8-directional movement

Shortest Path

First path found gives minimum length

Key Takeaway

🎯 Key Insight: BFS naturally finds shortest paths by exploring level-by-level

Asked in

a Amazon 45 M Microsoft 32 G Google 28 f Facebook 25

The key insight is that BFS naturally finds the shortest path in unweighted grids by exploring level-by-level. The optimal approach uses Breadth-First Search starting from (0,0) and exploring all 8 directions until reaching (n-1,n-1). Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Backtracking	O(4ⁿ)	O(n²)	Try all possible paths using depth-first search
Breadth-First Search (Optimal)	O(n²)	O(n²)	Find shortest path using level-by-level exploration

DFS with Backtracking — Algorithm Steps

Start DFS from (0,0) if it's 0
For each cell, try all 8 directions
Backtrack and try other paths
Return minimum path length

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin at (0,0) and explore 8 directions

Backtrack

When stuck, backtrack and try other paths

Find Minimum

Track shortest path across all explorations

Code -

solution.c — C

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

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

void dfs(int** grid, int x, int y, int pathLength, int n, int** visited) {
    if (x == n-1 && y == n-1) {
        if (pathLength < minPath) {
            minPath = pathLength;
        }
        return;
    }
    
    for (int i = 0; i < 8; i++) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && 
            grid[nx][ny] == 0 && !visited[nx][ny]) {
            visited[nx][ny] = 1;
            dfs(grid, nx, ny, pathLength + 1, n, visited);
            visited[nx][ny] = 0;
        }
    }
}

int solution(int** grid, int n) {
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
    
    minPath = INT_MAX;
    int** visited = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        visited[i] = (int*)calloc(n, sizeof(int));
    }
    
    visited[0][0] = 1;
    dfs(grid, 0, 0, 1, n, visited);
    
    for (int i = 0; i < n; i++) {
        free(visited[i]);
    }
    free(visited);
    
    return minPath == INT_MAX ? -1 : minPath;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int n = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] == '[' && i > 0) n++;
    }
    
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    char* ptr = line + 1;
    for (int i = 0; i < n; i++) {
        ptr = strchr(ptr, '[') + 1;
        for (int j = 0; j < n; j++) {
            grid[i][j] = strtol(ptr, &ptr, 10);
            if (*ptr == ',') ptr++;
        }
        ptr = strchr(ptr, ']') + 1;
    }
    
    printf("%d\n", solution(grid, n));
    
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4ⁿ)

In worst case, explores exponential number of paths

✓ Linear Growth

Space Complexity

O(n²)

Recursion stack depth and visited array

⚠ Quadratic Space

87.0K Views

High Frequency

~25 min Avg. Time

1.9K 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

DFS with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler