Number of Islands
Given an $m \times n$ 2D binary grid, return the number of islands. An island is formed by connecting adjacent '1's. Use DFS or BFS.
Why Interviewers Ask This
Amazon asks this problem to evaluate a candidate's ability to traverse graph structures efficiently using standard algorithms like DFS or BFS. It tests core competency in handling 2D grids, managing visited states to prevent cycles, and optimizing for time complexity O(m*n). Interviewers specifically look for clean code implementation and the ability to discuss trade-offs between recursion depth and iterative approaches under pressure.
How to Answer This Question
1. Clarify Requirements: Confirm grid dimensions, boundary conditions, and what constitutes an island (horizontal/vertical adjacency only). 2. Propose Algorithm: State your choice of DFS or BFS immediately, explaining why one might be preferred over the other for deep grids versus wide ones. 3. Define Data Structures: Explicitly mention how you will track visited cells, such as modifying the input grid directly or using a separate boolean matrix. 4. Walk Through Logic: Describe the nested loop iteration over every cell, triggering a traversal only when an unvisited '1' is found. 5. Analyze Complexity: Conclude by calculating time complexity as O(m*n) since each cell is visited once, and space complexity based on your chosen recursion stack or queue size. This structured approach demonstrates Amazon's leadership principle of Dive Deep while ensuring clarity.
Key Points to Cover
- Explicitly state the time complexity is O(m*n) because every cell is processed once
- Demonstrate clear boundary checks before accessing array indices to prevent runtime errors
- Explain the mechanism for tracking visited nodes, whether by mutating the grid or using a hash set
- Discuss the trade-off between DFS and BFS regarding memory usage for very large grids
- Show awareness of edge cases like empty grids or grids containing no islands
Sample Answer
To solve the Number of Islands problem efficiently, I would start by validating the input grid. If it is empty, the answer is zero. Otherwise, I will iterate through every cell in the m x n grid. Whenever I encounter a '…
Common Mistakes to Avoid
- Forgetting to check boundary conditions, leading to index out-of-bounds exceptions during traversal
- Neglecting to mark visited cells, causing infinite loops or double-counting the same island
- Ignoring the distinction between horizontal and vertical connections, mistakenly including diagonals
- Failing to modify the input grid or create a visited structure, resulting in incorrect counts for repeated traversals
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.