DSA interview question

Shortest Path in a Binary Matrix

Hard · Data structures · Topics: graph, bfs, matrix

The problem

A warehouse robot moves on an n × n floor grid where 0 is free and 1 is blocked. It starts at the top-left cell and must reach the bottom-right cell, moving to any of the 8 neighbouring cells (diagonals included). What's the shortest path length, counted as the number of cells visited including both ends, or −1 if there's no path? Every move costs the same, so BFS from the start gives the answer the first time it reaches the goal.

Example: [[0,0,0], [1,1,0], [1,1,0]] → 4.

Function signature

int shortestPathBinaryMatrix(const vector<vector<int>>& grid);  // n x n

Test cases

Input	Output	Explanation
`[[0,1],[1,0]]`	`2`	One diagonal step
`[[0,0,0],[1,1,0],[1,1,0]]`	`4`	Right, diagonal, down
`[[1,0,0],[1,1,0],[1,1,0]]`	`-1`	The start is blocked
`[[0,1],[1,1]]`	`-1`	The goal is blocked
`[[0]]`	`1`	Start = goal

(Confirm: 8-directional moves; the path length counts cells, not moves; blocked start or goal gives −1.)

How interviewers phrase it

"Given an n x n binary matrix, return the length of the shortest clear path from top-left to bottom-right, moving in 8 directions" (LeetCode 1091).

Clarifying questions to ask

4 or 8 directions? (8.)
Is the length counted in cells or moves? (Cells.)
What if the start or end is blocked? (−1.)

Follow-ups to expect

"Why BFS and not Dijkstra?"
"How are the 8 neighbours generated?"
"Can you speed it up?"
"What if moves had different costs?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview