Your Dashboard
Interview Coaching
Learn
System Design
ML System Design
Code
Behavioral
Salary Negotiation
Interview Guides
Leetcode 200. Number of Islands
Count the number of islands (4-directionally connected components of '1's) in an m×n binary grid. This is a connected-components/flood-fill problem typically solved with DFS/BFS or Union-Find in O(mn) time (m,n ≤ 300).
Asked at:
Snapchat
Meta
Smartsheet
DESCRIPTION
Count the number of islands (4-directionally connected components of '1's) in an m×n binary grid. This is a connected-components/flood-fill problem typically solved with DFS/BFS or Union-Find in O(mn) time (m,n ≤ 300).
Input:
Output:
Explanation: There are 3 islands: the 2×2 block in top-left, the single cell in the middle, and the 1×2 block in bottom-right
Constraints:
- m == grid.length (number of rows)
- n == grid[i].length (number of columns)
- 1 <= m, n <= 300
- grid[i][j] is '0' or '1'
- Islands are connected 4-directionally (not diagonally)
Understanding the Problem
Let's understand what we're being asked to do. We have a 2D grid (matrix) filled with '0's and '1's, like:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
We need to count how many islands exist. An island is a group of '1's connected horizontally or vertically (not diagonally). In the example above, there are 3 islands: the top-left 2×2 block, the single '1' in the middle, and the bottom-right 1×2 block.
Important constraint: Connections are only 4-directional (up, down, left, right). Diagonal connections don't count!
Edge cases to consider: What if the grid is empty? What if the entire grid is water ('0's)? What if the entire grid is one giant island? What if islands touch at corners but aren't connected?
Building Intuition
When we find a '1' that hasn't been visited yet, we've discovered a new island. But that '1' might be part of a larger connected group.
The key insight: once we find an unvisited '1', we need to explore all connected '1's to mark the entire island as visited. This prevents counting the same island multiple times.
By exploring all connected cells when we discover a new island, we ensure each island is counted exactly once.
This transforms the problem from 'count all '1's' (which would be wrong) to 'count connected components' (which is correct). The difference is between counting individual cells vs. counting groups of connected cells.
Imagine you're looking at a map of actual islands from an airplane. When you spot land, you don't just mark that one spot - you trace the entire coastline to understand the full extent of that island.
Similarly, when we find a '1', we need to 'flood fill' outward in all 4 directions, marking every connected '1' as part of the same island. Only after fully exploring one island do we continue searching for the next one.
Common Mistakes
Optimal Solution
The optimal approach uses Depth-First Search (DFS) to explore connected components. Iterate through each cell in the grid. When we find an unvisited '1', increment the island count and launch a DFS to mark all connected '1's as visited (by changing them to '0' or using a separate visited set). The DFS explores all 4 directions recursively, ensuring the entire island is marked before continuing the search. This guarantees each island is counted exactly once.
Start: 4x5 grid, count islands (4-directionally connected '1's)
0 / 39
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(m × n) We visit each cell in the grid exactly once. Even though DFS is called multiple times, each cell is processed only once across all DFS calls, resulting in linear time relative to grid size
Space Complexity: O(m × n) In the worst case (entire grid is one island), the DFS recursion stack can go as deep as m × n cells. Additionally, if using a separate visited set instead of modifying the grid, that requires O(m × n) space
What We've Learned
- DFS/BFS for connected components: When you need to find groups of connected cells in a matrix (islands, regions, clusters), Depth-First Search or Breadth-First Search is the go-to pattern - it systematically explores all reachable cells from a starting point, naturally identifying one complete component per search.
- In-place marking technique: Instead of maintaining a separate visited set (which costs O(mn) space), modify the grid directly by changing '1' to '0' (or another marker) as you visit cells - this achieves O(1) auxiliary space while preventing revisits and double-counting islands.
- Four-directional traversal pattern: Implement neighbor exploration using direction arrays like `[(0,1), (1,0), (0,-1), (-1,0)]` or explicit checks - this makes the code cleaner and easier to extend to 8-directional or other connectivity patterns in similar problems.
- Boundary validation before recursion: Always check bounds (row/col within grid) AND cell value ('1' for land) before making recursive DFS calls or adding to BFS queue - failing to validate boundaries first leads to index-out-of-bounds errors, while checking cell value prevents infinite loops.
- Linear time complexity insight: The O(mn) time complexity works because each cell is visited at most once - once marked as visited (turned to '0'), it's never processed again, making this approach optimal since you must examine every cell at least once to count all islands.
- Flood-fill pattern recognition: This problem is fundamentally a flood-fill algorithm (like paint bucket in image editors) - recognize this pattern in problems involving region detection, image segmentation, maze solving, or any scenario where you need to identify contiguous groups in a 2D space.
Related Concepts and Problems to Practice
medium
This is the exact same problem as the one being analyzed. It teaches connected-components/flood-fill on a matrix using DFS, which is the core pattern needed for counting islands in a binary grid.
easy
This is a foundational flood-fill problem on a matrix that teaches the same 4-directional traversal pattern used in Number of Islands. It's an easier introduction to the connected-components concept before tackling island counting.
medium
This problem uses similar matrix DFS traversal to identify connected regions, but adds complexity by requiring boundary-aware logic. It reinforces the same connected-components pattern while introducing edge-case handling in matrix traversal.
Test Your Understanding
Why is matrix the right data structure for this problem?
matrix provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early November, 2025
Snapchat
Mid-level
A variant of this question for the technical phone screen round.
Late October, 2025
Senior
Asked in the first technical screening round
Late October, 2025
Snapchat
Senior
It was slightly differently phrased with int[][] sky as a grid with Heat radiation Index as values and cloud is anything which has value <=4. Find how many clouds are in the grid. There were also some follow-ups regarding 1.if value <= 1 then its a thurderstom. Verify if there is a thunderstorm in the grid. 2. Count of thunderstorms?
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.