This problem requires identifying separate land regions in a 2D binary grid efficiently. Start from each unvisited land cell and perform a depth-first search (DFS) or breadth-first search (BFS) to mark all connected lands. Each DFS/BFS initiation represents a distinct island, ensuring that overlapping or adjacent land clusters are not double-counted, which is key for accurate results in large grids.
Problem Statement
Given an m x n 2D grid representing a map of '1's (land) and '0's (water), determine the total number of separate islands. An island consists of horizontally or vertically adjacent '1's and is entirely surrounded by water.
Each cell can only belong to one island. You must process the grid efficiently, applying depth-first search, breadth-first search, or union-find strategies to identify all islands without revisiting previously counted land cells. Examples illustrate typical island configurations.
Examples
Example 1
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]
Output: 1
Example details omitted.
Example 2
Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]
Output: 3
Example details omitted.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] is '0' or '1'.
Solution Approach
Depth-First Search (DFS) Traversal
Iterate over each cell in the grid. When a '1' is found, initiate a DFS to mark all connected lands as visited. Each DFS call counts as a single island. This approach leverages recursion or an explicit stack to traverse neighbors efficiently.
Breadth-First Search (BFS) Traversal
For each unvisited land cell, use a queue to explore all neighboring land cells level by level. Mark cells as visited to prevent double-counting. BFS ensures systematic traversal and can handle larger grids iteratively without deep recursion stack issues.
Union-Find Approach
Represent each land cell as a node in a disjoint set. Merge connected land nodes using union operations. After processing the grid, the number of unique sets corresponds to the total islands. This method is effective for dynamic connectivity but requires careful initialization.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity varies: DFS/BFS is O(mn) as each cell is visited once. Union-Find is O(mn * α(mn)) where α is the inverse Ackermann function. Space complexity is O(mn) for visited markers or recursion/queue storage depending on the approach.
What Interviewers Usually Probe
- Expect array traversal plus DFS/BFS as a primary approach.
- Check if candidate handles edge cases like all water or single-cell islands.
- Look for marking strategies to prevent revisiting cells and miscounting islands.
Common Pitfalls or Variants
Common pitfalls
- Failing to mark visited cells, causing infinite loops or double-counting.
- Confusing diagonal adjacency with vertical/horizontal adjacency.
- Using recursion without stack limits, which may cause stack overflow on large grids.
Follow-up variants
- Count islands considering diagonal adjacency as connected.
- Return the size of the largest island instead of the count.
- Allow dynamic addition of land cells and update the island count incrementally.
How GhostInterview Helps
- Identifies when DFS or BFS is most efficient for island counting.
- Highlights common pitfalls like revisiting cells or miscounting islands.
- Provides step-by-step guidance to implement array-based island traversal correctly.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the best approach to solve Number of Islands?
DFS or BFS is typically optimal; DFS is simple recursively, BFS uses a queue to avoid deep recursion issues.
Can diagonal cells count as connected islands?
By default, only horizontal and vertical connections count; diagonal connections create a different variant of the problem.
How do I prevent revisiting cells during DFS/BFS?
Mark each visited land cell by changing its value or using a separate visited matrix to avoid double-counting islands.
What is the time complexity for Number of Islands?
DFS and BFS both run in O(m*n) time, visiting each cell exactly once; Union-Find has slightly higher overhead.
Does GhostInterview handle large grids efficiently?
Yes, it guides the implementation to manage visited markers and traversal order to prevent stack overflow or excessive memory usage.
Need direct help with Number of Islands instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Number of Islands from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Transform the matrix in-place by marking regions surrounded by 'X' as 'X', while keeping border-adjacent 'O's intact.
Open problem page#695 Max Area of IslandFind the largest connected land area in a binary grid using array traversal and depth-first search efficiently.
Open problem page#778 Swim in Rising WaterSolve the problem of swimming through a grid of rising water with a binary search on the valid answer space.
Open problem page