Coding questions · Snapchat

Compute shortest path in a 2D grid

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.

Shortest Path in a 2D Grid

Constraints

0 means open, 1 means blocked
start and target are grid coordinates

Examples

Example 1

Input: ([[0, 0, 0], [1, 1, 0], [0, 0, 0]], (0, 0), (2, 2))
Output: 4

Example 2

Input: ([[0, 1], [1, 0]], (0, 0), (1, 1))
Output: -1

Hints

Use BFS because every move has equal cost.