Crack the Backend

Problem Statement

Given an n×n binary matrix grid, return the length of the shortest clear path from (0,0) to (n-1,n-1). A clear path goes only through cells with value 0. You can move in 8 directions (up, down, left, right, and the 4 diagonals). If no such path exists, return -1. The path length is the number of visited cells (so (0,0) counts as 1).

This is an unweighted grid shortest path: BFS guarantees we first reach the bottom-right with the minimum number of steps. Start from (0,0); if (0,0) or (n-1,n-1) is 1, return -1.

Key Observations

BFS: Queue entries (r, c, dist). Start with (0, 0, 1). Mark cells as visited when we enqueue them (or when we process them). For each cell, try all 8 neighbors: if in bounds, grid[nr][nc] == 0, and not visited, enqueue (nr, nc, dist+1). When we dequeue (n-1, n-1, d), return d. If the queue is exhausted without reaching the end, return -1.
Each cell is enqueued at most once; O(n²) time and space.

Approach

High-level: If grid[0][0] == 1 || grid[n-1][n-1] == 1 return -1. BFS from (0,0) with distance 1. Queue (r, c, dist). When we pop (n-1, n-1), return dist. Neighbors: 8 directions, in bounds, grid[nr][nc]==0, not visited. Return -1 if queue empties.

Steps: Queue, enqueue (0,0,1), mark visited. While queue not empty: pop (r,c,d); if (r,c)==(n-1,n-1) return d; for each of 8 neighbors if valid and 0 and not visited, enqueue (nr,nc,d+1), mark visited. Return -1.

Implementation

Java

public int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;

    if (grid[0][0]==1 || grid[n-1][n-1]==1) {
        return -1;
    }

    int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    Queue<int[]> q = new ArrayDeque<>();
    boolean[][] vis = new boolean[n][n];
    vis[0][0]=true; q.offer(new int[]{0,0,1});

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r=cur[0], c=cur[1], d=cur[2];

        if (r==n-1 && c==n-1) {
            return d;
        }

        for (int[] dir : dirs) {
            int nr=r+dir[0], nc=c+dir[1];

            if (nr>=0&&nr<n&&nc>=0&&nc<n&&!vis[nr][nc]&&grid[nr][nc]==0) {
                vis[nr][nc]=true; q.offer(new int[]{nr,nc,d+1});
            }
        }
    }

    return -1;
}

Test Cases

Example 1

Input

grid = [[0,1],[1,0]]

Expected

2

Explanation

Path (0,0)->(1,1).

Complexity Analysis

Time: O(n^2).
Space: O(n^2).

Follow-ups

4-direction only; obstacles.