Compute grid shortest path with obstacles
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an m x n grid of integers where cells with value -1 represent obstacles and all other cells are traversable. Starting at (0,
0) and targeting (m-1, n-
1), compute the length of the shortest path using only four-directional moves (up, down, left, right). Return -1 if the target is unreachable. Describe your algorithm, prove its correctness at a high level, analyze time and space complexities, cover edge cases (e.g., blocked start/goal, single-cell grid), and provide pseudocode.
Quick Answer: This question evaluates understanding of grid-based graph traversal, shortest-path reasoning, and obstacle handling, testing competence in algorithmic problem-solving and complexity analysis within the Coding & Algorithms domain.
You are given an `m x n` grid of integers where cells with value `-1` represent obstacles and all other cells are traversable. Starting at the top-left cell `(0, 0)` and targeting the bottom-right cell `(m-1, n-1)`, compute the length of the shortest path using only four-directional moves (up, down, left, right). The path length is the number of moves (edges) taken. Return `-1` if the target is unreachable.
Edge cases to handle: a blocked start or goal cell returns `-1`; a single-cell grid `[[0]]` returns `0` (already at the target); an empty grid returns `-1`.
Use breadth-first search (BFS) from the start. Because every move has unit cost, the first time BFS reaches the goal it does so via a shortest path. Track visited cells to avoid revisiting. Time complexity is `O(m * n)` since each cell is enqueued at most once; space complexity is `O(m * n)` for the visited grid and queue.
Constraints
- 1 <= m, n <= 1000
- Each cell is either -1 (obstacle) or a non-negative integer (traversable)
- Only up/down/left/right moves are allowed
- Path length is counted as the number of moves (edges), so a single-cell start==goal grid has length 0
Examples
Input: [[0,0,0],[0,-1,0],[0,0,0]]
Expected Output: 4
Explanation: The center is blocked; the shortest path goes around it in 4 moves, e.g. (0,0)->(0,1)->(0,2)->(1,2)->(2,2).
Input: [[0,-1],[-1,0]]
Expected Output: -1
Explanation: Both neighbors of the start are obstacles, so the goal at (1,1) is unreachable.
Hints
- Every move costs the same (unit weight), so BFS from the start yields shortest paths — Dijkstra is unnecessary.
- Mark a cell visited the moment you enqueue it, not when you dequeue it, to avoid adding the same cell multiple times.
- Handle the special cases first: empty grid, blocked start, blocked goal, and a 1x1 grid (answer 0).