Katkat
Back

Find Shortest Clear Grid Path

SnapchatMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

Solve the shortest clear path in an n by n binary grid using BFS in 8 directions. Covers blocked endpoints, visited marking, path length, correctness, complexity, and weighted-move follow-ups.

Given an n x n binary grid, where 0 means open and 1 means blocked, return the length of the shortest clear path from the top-left cell to the bottom-right cell.

You may move in all 8 directions to neighboring cells: horizontal, vertical, and diagonal. A valid path may only pass through open cells.

Return -1 if either endpoint is blocked or no path exists.

Constraints & Assumptions

  • The path length counts the number of cells visited, including the start and end cells.
  • The grid is square: n x n.
  • Diagonal moves are allowed.
  • Mutating the grid for visited marking is acceptable if stated, but a separate visited set is also fine.
  • Use breadth-first search because all moves have equal cost.

Clarifying Questions to Ask

  • Does path length count edges or cells?
  • Are diagonal moves allowed through corners if adjacent orthogonal cells are blocked?
  • Can I mutate the input grid?
  • What should be returned for an empty grid?

Follow-up questions

  • How would the solution change if moves had different costs?
  • How would you return the actual path, not only length?
  • How would you handle a rectangular grid?
  • How would you solve it if diagonal corner-cutting were disallowed?