Katkat
Back

Compute shortest path in a 2D grid

SnapchatSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of graph traversal and pathfinding concepts, including modeling a 2D grid as a graph and reasoning about shortest-path computations and obstacle handling.

Given an m x n grid where:

  • 0 represents an empty cell you can move through
  • 1 represents a blocked cell you cannot enter
  • movement is allowed in 4 directions (up, down, left, right)

You are also given coordinates start = (sr, sc) and target = (tr, tc) (both are inside the grid).

Return the length of the shortest path (number of moves) from start to target. If target is unreachable, return -1.

Explain the algorithm you would use and its time/space complexity.