Shortest Path in Binary Matrix
Given an $n \times n$ binary matrix `grid`, return the length of the shortest clear path from the top-left to the bottom-right corner. A clear path uses only cells with 0. Use BFS.
Why Interviewers Ask This
Amazon asks this question to evaluate a candidate's mastery of Breadth-First Search (BFS) for unweighted shortest path problems. They specifically look for the ability to handle edge cases like blocked start/end points and to implement queue-based traversal efficiently without recursion depth issues, reflecting their emphasis on operational excellence and clean, scalable code.
How to Answer This Question
1. Clarify requirements: Confirm if diagonal moves are allowed (yes here), define return value (-1 vs length), and check constraints. 2. Validate inputs: Immediately check if grid[0][0] or grid[n-1][n-1] is 1; return -1 instantly if blocked. 3. Initialize BFS: Create a queue storing coordinates and distance, add start node with distance 1, and maintain a visited set or modify grid in-place to avoid cycles. 4. Execute traversal: Loop while queue is not empty, dequeue current cell, check all 8 neighbors, and enqueue valid 0s with incremented distance. 5. Optimize and verify: Stop immediately upon reaching the bottom-right corner to ensure shortest path, then return the distance or -1 if queue empties. This structured approach demonstrates Amazon's 'Deliver Results' principle by prioritizing early exits and efficient resource usage.
Key Points to Cover
- Explicitly handling the edge case where start or end nodes are blocked
- Correctly implementing 8-directional movement logic including diagonals
- Using BFS to guarantee the shortest path in an unweighted grid
- Optimizing space by modifying the input grid or using a visited set effectively
- Implementing an early exit condition once the destination is reached
Sample Answer
To solve the Shortest Path in Binary Matrix problem efficiently, I would first validate the input matrix. If the starting cell at [0,0] or the destination at [n-1,n-1] contains a 1, we cannot form a path, so I would retu…
Common Mistakes to Avoid
- Forgetting to check if the starting or ending cell is blocked before running BFS
- Only checking 4 cardinal directions instead of the required 8 directions
- Failing to mark cells as visited, leading to infinite loops and Time Limit Exceeded errors
- Returning the number of edges instead of the number of nodes (path length)
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.