Compute shortest path in a 2D grid
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
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.
Quick Answer: 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 a 0/1 grid, start, and target, return the minimum number of 4-directional moves from start to target. Cells with 1 are blocked. Return -1 if unreachable.
Constraints
- 0 means open, 1 means blocked
- start and target are grid coordinates
Examples
Input: ([[0, 0, 0], [1, 1, 0], [0, 0, 0]], (0, 0), (2, 2))
Expected Output: 4
Input: ([[0, 1], [1, 0]], (0, 0), (1, 1))
Expected Output: -1
Input: ([[0]], (0, 0), (0, 0))
Expected Output: 0
Hints
- Use BFS because every move has equal cost.