DSA Intermediate

Number of Islands — DFS StackOverflow on 10,000×10,000 Grid

Q: 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.

Q: 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.

Q: 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.

Q: What is the time complexity of the number of islands algorithm?

O(rows * cols) because each cell is visited at most twice: once by the outer scan and once by DFS. The DFS for each island visits each cell exactly once. The total work across all DFS calls is bounded by the total number of cells.

Q: Can this be solved with BFS instead of DFS?

Yes. Replace the recursive DFS with a BFS queue. Start with the unvisited '1' cell, add it to the queue, mark as visited, then repeatedly dequeue and enqueue unvisited '1' neighbors. BFS and DFS both give O(rows*cols) time. BFS avoids recursion depth issues for large grids.

Q: How do you solve the 'number of distinct islands' problem?

Record the shape of each island as the DFS traversal path (e.g., 'RRDD' for right-right-down-down). Normalize the path (subtract the starting cell coordinates). Use a set of shapes to count distinct island shapes. Two islands with identical DFS traversal patterns are the same shape.

📅 March 05, 2026 ⏱ 6 min read 🎯 Intermediate

Where developers are forged. · Structured learning · Free forever.

📍 Part of: Graphs → Topic 12 of 17

Java's default 1MB stack overflows at ~2,500 recursion depth on 10,000×10,000 grid.

⚙️ Intermediate — basic DSA knowledge assumed

In this tutorial, you'll learn

Java's default 1MB stack overflows at ~2,500 recursion depth on 10,000×10,000 grid.

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.

✦ Plain-English analogy ✦ Real code with output ✦ Interview questions

⚡Quick Answer

Number of Islands counts connected '1's in a 2D grid using graph traversal.
Three approaches: DFS (recursive flood-fill), BFS (queue-based wave), Union-Find (disjoint sets).
All run O(m×n) time but differ in space and stack safety.
DFS is simplest but risks StackOverflow on large grids; BFS is stack-safe.
Union-Find handles dynamic grid updates and is the go-to for distributed or incremental problems.
Biggest mistake: ignoring grid bounds or marking visited at dequeue time in BFS (causes double processing).

🚨 START HERE

Grid Island Debug Cheat Sheet

Quick commands and checks for common grid traversal bugs

🟡

StackOverflow with DFS

Immediate ActionAdd explicit stack or use BFS

Commands

java -Xss2m -cp . YourClass

Check max recursion depth with -XX:+PrintFlagsFinal -XX:StackSize

Fix NowRewrite to BFS using java.util.LinkedList queue

🟡

Wrong island count in BFS

Immediate ActionCheck visited marking logic

Commands

Add debug output: System.out.println('Enqueuing ('+row+','+col+')');

Verify grid marking: ensure grid[row][col]='0' at enqueue, not dequeue

Fix NowMove visited=true to enqueue block

🟡

ArrayIndexOutOfBounds

Immediate ActionCheck neighbor bounds checking

Commands

Print grid dimensions: System.out.println(rows+'x'+cols);

Verify all neighbor condition checks include row>=0 && row<rows

Fix NowRefactor to a helper method inBounds()

Production Incident

DFS StackOverflow on a 10,000 × 10,000 Satellite Image Grid

A geospatial analytics platform crashed when processing a massive raster grid because the recursive DFS used for island counting exceeded the call stack limit.

SymptomThe application threw a StackOverflowError on grid sizes exceeding 2,000 × 2,000. The island count was never returned; the process died silently.

AssumptionThe team assumed DFS's simplicity would scale because 'it's just recursion.' They tested only on small grids during development.

Root causeJava's default thread stack size is ~1MB. A fully connected island of 10,000 cells -> recursion depth of 10,000 frames, each storing local variables -> stack overflow around 2,000–3,000 frames.

FixReplaced recursive DFS with iterative BFS (queue-based). Stack usage moved to heap, eliminating the overflow.

Key Lesson

Always test edge-case grid sizes (e.g., single island covering entire grid).For large grids, prefer BFS or iterative DFS with explicit stack over recursion.If you must use recursion, increase stack size via -Xss flag, but that only buys you space, not reliability.

Production Debug Guide

Island counting and flood fill patterns

StackOverflowError during island traversal→Switch from DFS recursion to BFS or iterative DFS. Use -Xss to temporarily increase stack, but fix the root cause.

Wrong island count (under or over counting)→Check visited marking: In BFS, mark visited at enqueue time, not dequeue. In DFS, mark before recursive calls. Ensure you're not counting water cells.

Island count too high, especially for diagonal-only land cells→Verify you're only checking 4 directions (up/down/left/right). Diagonal adjacency is not counted in this problem.

Performance degradation on sparse grids→Use Union-Find for sparse or dynamically updated grids. DFS/BFS still O(m×n) but Union-Find can skip large empty areas if combined with sparse representation.

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.

How Number of Islands Works — Step by Step

The algorithm uses DFS or BFS to explore connected land cells, treating each unexplored '1' as a new island.

Scan the grid cell by cell from top-left to bottom-right.
When an unvisited '1' is found, increment the island counter and start DFS/BFS to mark the entire connected island.
DFS: mark current cell as visited ('0' or a visited marker). Recursively visit all 4 neighbors (up, down, left, right) that are '1' and unvisited.
After DFS returns, all cells of that island are marked. Continue scanning for the next unvisited '1'.
Return the island counter.

For grid: 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1

(0,0)=1: island++→1. DFS marks (0,0),(0,1),(1,0),(1,1) as visited.
(0,2..4)=0: skip. (1,2..4)=0: skip.
(2,2)=1: island++→2. DFS marks (2,2).
(3,3)=1: island++→3. DFS marks (3,3),(3,4).
Return 3.

📊 Production Insight

The naive approach of scanning and DFS works for grids up to a few thousand cells.

Beyond that, the recursion depth of DFS becomes a problem — you'll hit StackOverflow on a single large island.

Rule: Always ask about grid size before choosing the algorithm in production.

🎯 Key Takeaway

Treat each unvisited '1' as a new island and sink it completely.

The 'sink and scan' pattern is the core of all three solutions.

Without this pattern, you either double-count or miss islands.

Worked Example — Grid Traversal Trace

Grid (3x3): 1 1 0 0 1 0 0 0 1

Scan

(0,0)=1: islands=1. DFS: visit (0,0), go right→(0,1)=1: visit. Go right→(0,2)=0: stop. Go down from (0,1)→(1,1)=1: visit. Go down from (1,1)→(2,1)=0: stop. Go left from (1,1)→(1,0)=0: stop. All neighbors of island 1 explored.
(0,1) already visited. (0,2)=0: skip.
(1,0)=0: skip. (1,1) already visited. (1,2)=0: skip.
(2,0)=0: skip. (2,1)=0: skip. (2,2)=1: islands=2. DFS: visit (2,2). No unvisited '1' neighbors.
Total: 2 islands.

Time: O(rowscols). Space: O(rowscols) for recursion stack in worst case (all land).

📊 Production Insight

Worked examples expose off-by-one errors and boundary conditions.

In real debugging, trace a small grid by hand to verify your algorithm before trusting it on large data.

Rule: A pencil trace catches more bugs than a debugger on the first try.

🎯 Key Takeaway

Trace at least one full example to validate your logic.

The grid scanning order (top-left to bottom-right) ensures you see every cell exactly once.

This manual step prevents the classic 'why did I count 4 islands instead of 3?' interview crisis.

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.

IslandGridVisualizer.java · JAVA

12345678910111213141516171819202122232425262728293031

package io.thecodeforge.algorithm;

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.");
    }
}

▶ Output

Grid layout (L=land, ~=water):
L L ~ ~ ~
L L ~ ~ ~
~ ~ L ~ ~
~ ~ ~ L L

Expected island count: 3
Each cluster of connected L's = one island.

🔥Mental Model:

Diagonal cells do NOT count as connected. (1,1) and (2,2) are neighbors on a chessboard but NOT in this problem. Only up, down, left, right — four directions only. This trips up a surprising number of candidates.

📊 Production Insight

Once you see the grid as a graph, you unlock decades of graph algorithm research.

In production, this means you can reuse existing graph libraries (like JGraphT or Neo4j) rather than writing custom traversal.

Rule: The hardest part of any problem is reframing it — spend time on that, not on coding.

🎯 Key Takeaway

A grid cell is a node; adjacency is an edge.

This reframing turns island counting into connected components counting.

Mastering this mental model is more valuable than any single implementation.

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.

NumberOfIslandsDFS.java · JAVA

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778

package io.thecodeforge.algorithm;

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
    }
}

▶ Output

Grid 1 island count: 3
Grid 2 island count: 1
Grid 3 island count: 4

⚠ Watch Out:

The in-place mutation (overwriting '1' with '0') modifies the caller's grid permanently. If the original grid must be preserved, clone it before passing it in, or use a separate boolean[][] visited array. In interviews, always ask: 'Can I modify the input?' before mutating it.

📊 Production Insight

DFS is the fastest to write but the most dangerous in production on large grids.

We've seen production outages caused by StackOverflow from unexpectedly large connected components.

Rule: In code reviews, flag recursive grid traversals unless the grid size is bounded.

🎯 Key Takeaway

DFS is the simplest but riskiest approach.

Always assess grid dimensions before choosing recursion.

If you can't bound the depth, use BFS instead.

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.

NumberOfIslandsBFS.java · JAVA

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687

package io.thecodeforge.algorithm;

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
    }
}

▶ Output

Grid 1 (BFS) island count: 3
Large grid (BFS) island count: 1

💡Pro Tip:

In production systems processing enormous satellite image grids (think: 10,000 x 10,000 cells), BFS is almost always the right call. Java's default thread stack is ~512KB to 1MB. A 10,000-cell-deep DFS recursion will blow that stack. BFS moves the frontier onto the heap (the queue), where memory is orders of magnitude larger.

📊 Production Insight

BFS trades recursion depth for heap memory. The queue grows as O(min(rows,cols)) in the worst case, which is far safer than DFS's O(rows*cols) stack.

In practice, BFS is the default for any grid with unknown size.

Rule: If the grid dimensions aren't under your control, use BFS.

🎯 Key Takeaway

BFS avoids stack overflow by using a heap-allocated queue.

Space complexity is O(min(m,n)) — queue width — not O(m*n) like DFS stack.

When in doubt, pick BFS over DFS for production safety.

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.

NumberOfIslandsUnionFind.java · JAVA

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125

package io.thecodeforge.algorithm;

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
    }
}

▶ Output

Grid 1 (Union-Find) island count: 3
Grid 2 (Union-Find) island count: 8

🔥Interview Gold:

If an interviewer asks 'What if cells are added to the grid one at a time and you need the island count after each insertion?', Union-Find is the only efficient answer. DFS/BFS would be O(m*n) per insertion. Union-Find handles each new cell in near O(1) — you initialize the new cell as its own island, then try to union it with its existing land neighbors.

📊 Production Insight

Union-Find excels in dynamic environments where cells are added incrementally.

In production systems handling streaming satellite data, BFS/DFS require full recomputation, but Union-Find processes each addition in near-constant time.

Rule: For any problem with incremental updates, Union-Find is your only realistic option.

🎯 Key Takeaway

Union-Find is overkill for a static grid but invaluable for dynamic updates.

Its near-O(1) union and find operations make it the only choice when cells appear over time.

Master its 1D index encoding: index = row * cols + col.

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

✕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.

✕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.

✕Counting water cells or double-counting merged islands in Union-Find

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?Mid-levelReveal
Modify DFS/BFS to return the size of the explored island by counting cells during traversal. For DFS, increment a counter each time you call sinkIsland on a cell and return the total. For BFS, count cells as you dequeue. Track the maximum using a variable. Union-Find requires storing component sizes in the rank array or a separate size array; during union, update the size of the new root.
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?SeniorReveal
BFS/DFS can't cross machines because they require shared state. Union-Find can be adapted: each server processes its slice and tracks boundary rows. When two adjacent land cells are on different machines (boundary), you need a distributed union. This is typically done by sending boundary cell coordinates to a coordinator that performs the union. The final island count is the sum of local islands minus the number of boundary unions that merged separate groups.
QWhat changes to your algorithm if diagonal connections also count as part of the same island? Walk me through the exact code change needed.Mid-levelReveal
Change the direction arrays to include diagonals: rowDirections = {-1,-1,-1,0,0,1,1,1} and colDirections = {-1,0,1,-1,1,-1,0,1}. Then update the DFS/BFS neighbor loop to iterate over 8 directions. Union-Find also needs to check all 8 directions when iterating the grid (or at least right, down, and down-right, down-left). The rest of the algorithm remains the same. Complexity stays O(m×n) but constant factor increases.

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.

What is the time complexity of the number of islands algorithm?

O(rows * cols) because each cell is visited at most twice: once by the outer scan and once by DFS. The DFS for each island visits each cell exactly once. The total work across all DFS calls is bounded by the total number of cells.

Can this be solved with BFS instead of DFS?

Yes. Replace the recursive DFS with a BFS queue. Start with the unvisited '1' cell, add it to the queue, mark as visited, then repeatedly dequeue and enqueue unvisited '1' neighbors. BFS and DFS both give O(rows*cols) time. BFS avoids recursion depth issues for large grids.

How do you solve the 'number of distinct islands' problem?

Record the shape of each island as the DFS traversal path (e.g., 'RRDD' for right-right-down-down). Normalize the path (subtract the starting cell coordinates). Use a set of shapes to count distinct island shapes. Two islands with identical DFS traversal patterns are the same shape.

🔥

Naren Founder & Author

Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.

About Naren Get in touch

Forged with 🔥 at TheCodeForge.io — Where Developers Are Forged