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 '1' that hasn't been visited yet, I know I've found a new island, so I increment my counter and immediately initiate a Depth-First Search from that position. The DFS function will explore all four adjacent directions—up, down, left, and right. Before recursing, I must check boundary conditions to ensure coordinates remain within the grid limits. Crucially, I will mark each visited cell as '0' or add it to a visited set to avoid counting the same island multiple times. For example, if the grid has a cluster of three connected '1's, the initial trigger finds the first one, and the DFS recursively visits the other two, marking them all as processed before returning control to the main loop. This ensures we count exactly one island per connected component. Regarding complexity, since we visit each cell at most once during the outer loop and the recursive calls, the time complexity is strictly O(m*n). Space complexity depends on the recursion stack depth, which could be O(min(m,n)) for balanced islands or O(m*n) for a snake-like path filling the entire grid. This approach aligns with Amazon's expectation for robust, scalable solutions that handle edge cases gracefully.
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
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.