Number of Islands Problem: BFS, DFS & Union-Find Explained
Every major mapping service — Google Maps, Apple Maps, OpenStreetMap — needs to understand geography as data. When a system asks 'how many distinct landmasses exist in this region?' or 'are these two cities on the same continent?', it's solving a problem structurally identical to Number of Islands. It's not an academic puzzle. It's the foundational pattern behind flood-fill tools in Photoshop, network segmentation in cybersecurity, and even blob detection in medical imaging software.
The core challenge is this: given a 2D grid of '1's (land) and '0's (water), you need to count the number of islands, where an island is a group of '1's connected horizontally or vertically. The tricky part isn't the counting itself — it's the traversal. You need a systematic way to explore every cell belonging to an island exactly once, without revisiting or double-counting. This is where graph traversal algorithms — specifically BFS and DFS — become your most powerful tools.
By the end of this article, you'll be able to implement three distinct solutions (DFS, BFS, and Union-Find) and — more importantly — explain why each one exists, when to choose one over another, and what to watch out for in an interview setting. You'll walk away with battle-tested code, a clear mental model, and the confidence to handle follow-up questions interviewers love to throw at candidates who think they're done after the first solution.
Thinking in Graphs: Why a Grid IS a Graph
Before writing a single line of code, you need to make a mental shift. A 2D grid isn't just a matrix of numbers — it's an implicit graph. Every cell is a node. Every horizontal or vertical adjacency between two land cells ('1') is an edge.
Once you see it that way, the problem transforms from 'count groups in a matrix' into 'count the number of connected components in an undirected graph.' That reframing is everything, because now you have decades of well-understood graph algorithms at your disposal.
The approach: iterate through every cell. When you find a '1' that you haven't visited yet, you've discovered a new island. Increment your counter, then immediately explore the entire island — marking every cell you touch as visited — so you never count it again. Repeat until every cell has been seen.
This 'explore and mark' pattern is the heartbeat of every solution to this problem, whether you use DFS, BFS, or Union-Find. Get this mental model locked in before you touch the code.
public class IslandGridVisualizer { public static void main(String[] args) { // This grid has 3 islands — let's visualize it before we solve it // '1' = land, '0' = water char[][] grid = { {'1', '1', '0', '0', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '1', '0', '0'}, {'0', '0', '0', '1', '1'} }; System.out.println("Grid layout (L=land, ~=water):"); for (char[] row : grid) { for (char cell : row) { // Replace '1' and '0' with readable symbols System.out.print(cell == '1' ? " L " : " ~ "); } System.out.println(); } // Manually trace the 3 islands: // Island 1: top-left 2x2 block of L's // Island 2: single L at row 2, col 2 // Island 3: two L's at row 3, cols 3-4 System.out.println("\nExpected island count: 3"); System.out.println("Each cluster of connected L's = one island."); } }
L L ~ ~ ~
L L ~ ~ ~
~ ~ L ~ ~
~ ~ ~ L L
Expected island count: 3
Each cluster of connected L's = one island.
DFS Solution: The Recursive Flood-Fill Approach
Depth-First Search is the most intuitive solution here. The moment you land on an unvisited land cell, you sink as deep as possible into that island — going north, south, east, west — before backtracking. It mirrors how you'd physically explore an island: keep walking until you hit water, then turn around.
The trick that makes this elegant: instead of maintaining a separate 'visited' boolean grid, you mutate the original grid. When you visit a land cell, you overwrite it with '0'. You're effectively sinking the island as you explore it, so it can never be counted twice. This is called 'in-place marking' and it cuts your space complexity from O(mn) for a visited array down to O(1) extra space (though the call stack still uses O(mn) in the worst case for recursion depth).
The recursion naturally handles the 'explore the whole island' requirement — each recursive call handles one cell, and it fans out in all four directions. The base cases stop the recursion when you go out of bounds or hit water.
Time complexity is O(m n) because every cell is visited at most once. Space complexity is O(m n) in the worst case due to the recursive call stack on a fully land-filled grid.
public class NumberOfIslandsDFS { // Direction arrays for moving up, down, left, right // These two arrays work in tandem: rowDirections[0] with colDirections[0] = move UP, etc. private static final int[] rowDirections = {-1, 1, 0, 0}; private static final int[] colDirections = {0, 0, -1, 1}; public static int countIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; // Guard clause: handle edge case of empty grid } int totalRows = grid.length; int totalCols = grid[0].length; int islandCount = 0; for (int row = 0; row < totalRows; row++) { for (int col = 0; col < totalCols; col++) { // Only start a DFS when we find unvisited land if (grid[row][col] == '1') { islandCount++; // Found a new island — now sink it entirely sinkIsland(grid, row, col, totalRows, totalCols); } } } return islandCount; } private static void sinkIsland(char[][] grid, int row, int col, int totalRows, int totalCols) { // Base case: stop if out of bounds OR if this cell is already water if (row < 0 || row >= totalRows || col < 0 || col >= totalCols || grid[row][col] != '1') { return; } // Mark this land cell as visited by turning it into water // This prevents us from counting it again in future iterations grid[row][col] = '0'; // Recursively sink all 4 neighbors that are also land for (int direction = 0; direction < 4; direction++) { int neighborRow = row + rowDirections[direction]; int neighborCol = col + colDirections[direction]; sinkIsland(grid, neighborRow, neighborCol, totalRows, totalCols); } } public static void main(String[] args) { char[][] gridOne = { {'1', '1', '0', '0', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '1', '0', '0'}, {'0', '0', '0', '1', '1'} }; char[][] gridTwo = { {'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'} }; char[][] gridThree = { {'1', '0', '0', '0', '0'}, {'0', '1', '0', '0', '0'}, {'0', '0', '1', '0', '0'}, {'0', '0', '0', '1', '0'} }; System.out.println("Grid 1 island count: " + countIslands(gridOne)); // Expect 3 System.out.println("Grid 2 island count: " + countIslands(gridTwo)); // Expect 1 System.out.println("Grid 3 island count: " + countIslands(gridThree)); // Expect 4 } }
Grid 2 island count: 1
Grid 3 island count: 4
BFS Solution: The Level-by-Level Wave Expansion
BFS solves the same problem but explores the island differently — like a wave rippling outward from a stone thrown into water. Instead of diving deep first, it visits all immediate neighbors before moving further out. This matters in practice because BFS avoids deep call stacks, making it safer for very large grids where DFS would cause a StackOverflowError.
The implementation uses a queue. When you find an unvisited land cell, enqueue it, mark it visited immediately (to avoid adding it multiple times), then process cells from the queue one by one — adding their unvisited land neighbors each time. When the queue empties, the entire island has been explored.
A critical BFS gotcha: mark the cell as visited when you ENQUEUE it, not when you DEQUEUE it. If you wait until dequeue, the same cell can be added to the queue multiple times by different neighbors, leading to redundant processing and potentially wrong counts in modified versions of this problem.
BFS and DFS produce identical island counts — the choice between them is about constraints. Large grid with deep islands? BFS wins. Simple implementation needed fast? DFS is cleaner. Both run in O(m * n) time.
import java.util.LinkedList; import java.util.Queue; public class NumberOfIslandsBFS { private static final int[] rowDirections = {-1, 1, 0, 0}; private static final int[] colDirections = {0, 0, -1, 1}; public static int countIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int totalRows = grid.length; int totalCols = grid[0].length; int islandCount = 0; for (int row = 0; row < totalRows; row++) { for (int col = 0; col < totalCols; col++) { if (grid[row][col] == '1') { islandCount++; // BFS: explore the entire island using a queue exploreIslandBFS(grid, row, col, totalRows, totalCols); } } } return islandCount; } private static void exploreIslandBFS(char[][] grid, int startRow, int startCol, int totalRows, int totalCols) { Queue<int[]> cellQueue = new LinkedList<>(); // Encode the cell position as a 2-element int array [row, col] cellQueue.offer(new int[]{startRow, startCol}); // Mark the starting cell visited NOW, before we even process it. // This prevents other neighbors from re-adding it to the queue. grid[startRow][startCol] = '0'; while (!cellQueue.isEmpty()) { int[] currentCell = cellQueue.poll(); int currentRow = currentCell[0]; int currentCol = currentCell[1]; // Explore all 4 neighbors of the current cell for (int direction = 0; direction < 4; direction++) { int neighborRow = currentRow + rowDirections[direction]; int neighborCol = currentCol + colDirections[direction]; // Check bounds and whether neighbor is unvisited land boolean inBounds = neighborRow >= 0 && neighborRow < totalRows && neighborCol >= 0 && neighborCol < totalCols; if (inBounds && grid[neighborRow][neighborCol] == '1') { cellQueue.offer(new int[]{neighborRow, neighborCol}); // Mark visited at enqueue time — crucial for correctness! grid[neighborRow][neighborCol] = '0'; } } } } public static void main(String[] args) { char[][] gridOne = { {'1', '1', '0', '0', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '1', '0', '0'}, {'0', '0', '0', '1', '1'} }; // A large single island that would create deep recursion with DFS char[][] largeIslandGrid = { {'1', '1', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '1', '1', '1', '1'} }; System.out.println("Grid 1 (BFS) island count: " + countIslands(gridOne)); // Expect 3 System.out.println("Large grid (BFS) island count: " + countIslands(largeIslandGrid)); // Expect 1 } }
Large grid (BFS) island count: 1
Union-Find Solution: The Most Powerful (and Interview-Impressive) Approach
Union-Find (also called Disjoint Set Union, or DSU) is the most sophisticated solution and the one that unlocks the most powerful follow-up variants of this problem. While DFS and BFS work by exploration, Union-Find works by connection: for every land cell, merge it with its land neighbors. At the end, count how many distinct groups remain.
This approach shines in two real-world scenarios. First: dynamic grids. If land cells are added one at a time and you need the island count after each addition, BFS/DFS would force you to recompute from scratch every time. Union-Find handles incremental updates in near O(1) per operation. Second: distributed systems. Union-Find can be parallelized in ways that recursive DFS cannot.
The implementation needs three core pieces: a parent array (who is each cell's group representative?), a rank array (used to keep the tree flat for efficiency), and an island count that decrements each time two separate groups merge into one.
Both find() and union() operations run in effectively O(1) amortized time with path compression and union by rank. Overall complexity: O(m n α(m*n)) where α is the inverse Ackermann function — practically constant.
public class NumberOfIslandsUnionFind { // Union-Find data structure encapsulated cleanly static class UnionFind { private int[] parent; // parent[i] = representative of i's group private int[] rank; // rank[i] = tree depth, used to keep trees flat private int islandCount; // tracks how many distinct islands exist public UnionFind(char[][] grid) { int totalRows = grid.length; int totalCols = grid[0].length; int totalCells = totalRows * totalCols; parent = new int[totalCells]; rank = new int[totalCells]; islandCount = 0; // Initialize: each land cell is its own island (its own parent) for (int row = 0; row < totalRows; row++) { for (int col = 0; col < totalCols; col++) { if (grid[row][col] == '1') { // Encode 2D position (row, col) as a 1D index int cellIndex = row * totalCols + col; parent[cellIndex] = cellIndex; // cell is its own root islandCount++; // every land cell starts as its own island } } } } // Find with path compression: points nodes directly to their root // This flattens the tree over time, making future finds faster public int find(int cellIndex) { if (parent[cellIndex] != cellIndex) { // Path compression: make every node on the path point to root parent[cellIndex] = find(parent[cellIndex]); } return parent[cellIndex]; } // Union by rank: always attach smaller tree under larger tree's root public void union(int cellA, int cellB) { int rootA = find(cellA); int rootB = find(cellB); if (rootA == rootB) { return; // Already in the same island — nothing to merge } // Merge the smaller-ranked tree into the larger-ranked tree if (rank[rootA] < rank[rootB]) { parent[rootA] = rootB; } else if (rank[rootA] > rank[rootB]) { parent[rootB] = rootA; } else { // Equal rank: arbitrarily choose rootB as new root, increase its rank parent[rootA] = rootB; rank[rootB]++; } // Two separate islands just merged into one — decrement count islandCount--; } public int getIslandCount() { return islandCount; } } public static int countIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int totalRows = grid.length; int totalCols = grid[0].length; UnionFind uf = new UnionFind(grid); // Only need to check RIGHT and DOWN neighbors to avoid double-processing // (each edge is undirected, so checking 2 directions covers all connections) for (int row = 0; row < totalRows; row++) { for (int col = 0; col < totalCols; col++) { if (grid[row][col] == '1') { int currentCellIndex = row * totalCols + col; // Check right neighbor if (col + 1 < totalCols && grid[row][col + 1] == '1') { int rightNeighborIndex = row * totalCols + (col + 1); uf.union(currentCellIndex, rightNeighborIndex); } // Check down neighbor if (row + 1 < totalRows && grid[row + 1][col] == '1') { int downNeighborIndex = (row + 1) * totalCols + col; uf.union(currentCellIndex, downNeighborIndex); } } } } return uf.getIslandCount(); } public static void main(String[] args) { char[][] gridOne = { {'1', '1', '0', '0', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '1', '0', '0'}, {'0', '0', '0', '1', '1'} }; char[][] gridTwo = { {'1', '0', '1', '0', '1'}, {'0', '1', '0', '1', '0'}, {'1', '0', '1', '0', '1'} }; System.out.println("Grid 1 (Union-Find) island count: " + countIslands(gridOne)); // Expect 3 System.out.println("Grid 2 (Union-Find) island count: " + countIslands(gridTwo)); // Expect 8 } }
Grid 2 (Union-Find) island count: 8
| Aspect | DFS (Recursive) | BFS (Iterative) | Union-Find |
|---|---|---|---|
| Time Complexity | O(m × n) | O(m × n) | O(m × n × α) |
| Space Complexity | O(m × n) call stack | O(min(m,n)) queue | O(m × n) parent array |
| Stack Overflow Risk | Yes — large grids | No — uses heap queue | No — fully iterative |
| Mutates Input Grid | Yes (unless cloned) | Yes (unless cloned) | No — reads grid only |
| Handles Dynamic Updates | No — full recompute | No — full recompute | Yes — near O(1) per update |
| Code Simplicity | Highest — fewest lines | Medium | Most complex — most code |
| Best Use Case | Small/medium grids, quick implementation | Large grids, stack safety matters | Dynamic grids, distributed systems |
| Interview Impressiveness | Expected — baseline | Good — shows awareness | Excellent — shows depth |
🎯 Key Takeaways
- A 2D grid is an implicit graph — reframing it that way unlocks BFS, DFS, and Union-Find as valid solution strategies, not just nested loop tricks.
- Always mark cells visited at ENQUEUE time in BFS, not dequeue time — this single rule prevents duplicate processing and is a classic interview-killer when forgotten.
- DFS is the most readable but risks StackOverflow on large grids; BFS is stack-safe; Union-Find is the only approach that handles dynamic cell insertions efficiently.
- The 1D encoding trick (index = row * totalCols + col) is what makes Union-Find work on a 2D grid — it flattens the grid into a single array without losing positional information.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Marking cells visited at DEQUEUE time instead of ENQUEUE time in BFS — Symptom: the same cell gets added to the queue multiple times by multiple neighbors, causing redundant processing; in modified problems that track island sizes this gives wrong counts — Fix: always set grid[row][col] = '0' (or visited[row][col] = true) immediately when you call queue.offer(), before the cell is even processed.
- ✕Mistake 2: Forgetting bounds checking before accessing grid cells — Symptom: ArrayIndexOutOfBoundsException when a land cell is on the edge of the grid and the algorithm tries to check a neighbor outside the array — Fix: always validate row >= 0 && row < totalRows && col >= 0 && col < totalCols BEFORE accessing grid[row][col]. Combine both checks in a single compound condition so Java short-circuits and never accesses the out-of-bounds index.
- ✕Mistake 3: Counting water cells or double-counting merged islands in the Union-Find approach — Symptom: island count is too high because water cells were initialized with parent entries — Fix: only initialize parent[cellIndex] and increment islandCount for cells where grid[row][col] == '1'. Water cells ('0') should never enter the Union-Find structure, and islandCount should only decrement inside union() when rootA != rootB — confirming a genuine merge of two previously separate islands.
Interview Questions on This Topic
- QHow would you modify your solution to return the SIZE of the largest island, not just the count of islands?
- QImagine the grid is so large it can't fit in memory on one machine — it's split across multiple servers, each holding a horizontal slice of rows. How would you count islands across the whole grid? (This tests whether you understand that BFS/DFS can't cross machines but Union-Find can be adapted with boundary merging.)
- QWhat changes to your algorithm if diagonal connections also count as part of the same island? Walk me through the exact code change needed.
Frequently Asked Questions
What is the time complexity of the Number of Islands problem?
All three main approaches — DFS, BFS, and Union-Find — run in O(m × n) time where m is the number of rows and n is the number of columns. Every cell is visited at most once. Union-Find is technically O(m × n × α(m×n)) where α is the inverse Ackermann function, but α grows so slowly it's effectively O(1) in practice, making Union-Find essentially O(m × n) as well.
Can you solve the Number of Islands problem without recursion?
Yes — BFS uses an iterative queue-based approach with no recursion at all. Union-Find is also fully iterative. Only the DFS solution typically uses recursion. If you want DFS without recursion, you can implement it with an explicit Stack instead of relying on the call stack, giving you the depth-first traversal order without StackOverflow risk.
Why do we only check RIGHT and DOWN neighbors in the Union-Find solution, but all 4 directions in DFS and BFS?
In Union-Find, we're scanning the grid top-to-bottom, left-to-right. For any given cell, its UP and LEFT neighbors have already been processed in previous iterations — meaning any union that needed to happen with them was already performed. Checking only RIGHT and DOWN avoids redundant union() calls without missing any connections. In DFS/BFS, we check all 4 directions because we're doing a radial exploration from a source cell outward, not a linear left-to-right scan.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.