Shortest Path in Binary Matrix

HardGraphsbfs 8-direction

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an n x n square grid named grid whose cells contain only 0 or 1. A 0 marks an open cell you may step on; a 1 marks a wall you cannot enter. A **clear path** runs from the top-left cell grid[0][0] to the bottom-right cell grid[n-1][n-1] such that: - Every cell visited on the path is an open cell (value 0), including the start and end cells. - Consecutive cells on the path are connected **8-directionally** — that is, they differ by at most 1 in both the row and the column index (the four orthogonal neighbors plus the four diagonal neighbors). The **length** of a clear path is the total number of visited cells, counting both the start and the end. Return the length of the shortest clear path from the top-left corner to the bottom-right corner. If no such path exists, return -1.

Examples

Input: grid = [[0,1],[1,0]]
Output: 2
Start at (0,0) and move diagonally to (1,1). Both cells are open and are 8-directionally adjacent, so the path visits 2 cells.
Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
One shortest route is (0,0) -> (0,1) -> (1,2) -> (2,2), visiting 4 cells. The diagonal step from (0,1) to (1,2) is allowed.
Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1
The top-left cell is a wall, so no clear path can begin. The answer is -1.

Constraints

  • `n == grid.length == grid[i].length`
  • `1 <= n <= 100`
  • `grid[i][j]` is either `0` or `1`.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.