Shortest Path in a Binary Matrix
Google● MediumFULLTIMEOAProblem statement
You are given an n × n binary matrix grid. A cell containing 0 is open, and a cell containing 1 is blocked.
Find a shortest path from the top-left cell (0, 0) to the bottom-right cell (n - 1, n - 1). Every visited cell must be open. In one move you may go to any of the eight neighboring cells: horizontally, vertically or diagonally. A diagonal move is allowed even when either neighboring horizontal or vertical cell is blocked.
Examples
Example 1
grid = [[0,1],[1,0]]return = 2The path (0, 0) → (1, 1) uses two open cells. The diagonal move is allowed even though the other two cells are blocked. Any path between these distinct endpoints uses at least two cells, so the answer is 2.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 1 more worked example, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.