Katkat
Back

Return a Shortest Path Through a Binary Grid

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Implement breadth-first search on an 8-directional binary grid to find and reconstruct a deterministic shortest path from the top-left to the bottom-right cell.

Description

Given an n x n binary grid grid, find the shortest clear path from the top-left corner (0, 0) to the bottom-right corner (n - 1, n - 1).

A clear path is a sequence of cells (r0, c0), (r1, c1), ..., (rk, ck) such that:

  • All visited cells grid[r][c] are 0 (clear).
  • All adjacent cells in the path are 8-directionally connected (horizontally, vertically, or diagonally).
  • (r0, c0) = (0, 0) and (rk, ck) = (n - 1, n - 1).

To ensure your result is deterministic when multiple shortest paths exist, visit neighbor offsets in this exact order: (-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)

Return the path as a list of coordinate pairs [(r0, c0), ..., (rk, ck)]. If no clear path exists, return an empty list [].

Function Signature

def shortest_path_binary_matrix(grid: list[list[int]]) -> list[tuple[int, int]]:
    pass

Examples

Example 1

Input: grid = [
  [0, 0, 0],
  [1, 1, 0],
  [1, 1, 0]
]
Output: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
Explanation: The shortest path takes 5 steps through clear cells along the top and right edges.

Example 2

Input: grid = [
  [0, 1],
  [1, 0]
]
Output: [(0, 0), (1, 1)]
Explanation: A diagonal step reaches the destination immediately.

Example 3

Input: grid = [
  [1, 0],
  [0, 0]
]
Output: []
Explanation: The starting cell is blocked, so no path exists.

Constraints

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

Hints

Hint 1

Because all steps have equal weight, Breadth-First Search (BFS) guarantees that the first time you reach the destination, it is via a shortest path.

Hint 2

Maintain a parent dictionary mapping `child_cell -> parent_cell` during traversal to backtrack and reconstruct the path once the destination is reached.

Hint 3

Handle the edge cases upfront: if `grid[0][0] == 1` or `grid[n - 1][n - 1] == 1`, return an empty list immediately; for `n == 1`, return `[(0, 0)]` if the cell is `0`.

Follow-up questions

  • How would your algorithm change if cardinal moves cost 1 unit and diagonal moves cost sqrt(2) units?
  • How can you apply bidirectional BFS to reduce the number of explored states on large grids?
  • If the grid does not fit in memory but can be queried via an API, how would you optimize memory usage during path reconstruction?