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

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

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

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

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

// io.thecodeforge — dsa tutorial
// In-place flood fill – no visited matrix, no extra allocation

public class IslandCounter {
    private char[][] grid;
    private int rows, cols;

    public int countIslands(char[][] map) {
        grid = map;
        rows = grid.length;
        cols = grid[0].length;
        int islandCount = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 'L') {
                    islandCount++;
                    sinkIsland(r, c);
                }
            }
        }
        return islandCount;
    }

    private void sinkIsland(int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != 'L')
            return;
        grid[r][c] = 'W';  // mark as visited by turning into water
        sinkIsland(r - 1, c);
        sinkIsland(r + 1, c);
        sinkIsland(r, c - 1);
        sinkIsland(r, c + 1);
    }
}

// io.thecodeforge — dsa tutorial
// BFS with encoded int queue – heap-friendly flood fill

import java.util.ArrayDeque;
import java.util.Deque;

public class BFSIslandCounter {
    public int countIslands(char[][] grid) {
        int rows = grid.length, cols = grid[0].length, count = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != 'L') continue;
                count++;
                queue.addLast((r << 16) | c);

                while (!queue.isEmpty()) {
                    int cell = queue.removeFirst();
                    int cr = cell >> 16, cc = cell & 0xFFFF;
                    if (grid[cr][cc] != 'L') continue;
                    grid[cr][cc] = 'W';

                    for (int[] d : dirs) {
                        int nr = cr + d[0], nc = cc + d[1];
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 'L')
                            queue.addLast((nr << 16) | nc);
                    }
                }
            }
        }
        return count;
    }
}

// io.thecodeforge — dsa tutorial
// Union-Find for dynamic island counting – game territory tracker

public class DynamicIslandGrid {
    private int[] parent, rank;
    private int cols, count;
    private boolean[][] land;

    public DynamicIslandGrid(int rows, int cols) {
        this.cols = cols;
        int n = rows * cols;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        land = new boolean[rows][cols];
        count = 0;
    }

    public void addLand(int r, int c) {
        if (land[r][c]) return;
        land[r][c] = true;
        count++;
        int id = r * cols + c;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < land.length && nc >= 0 && nc < cols && land[nr][nc]) {
                union(id, nr * cols + nc);
            }
        }
    }

    private void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        count--;
    }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];  // path compression
            x = parent[x];
        }
        return x;
    }

    public int getIslandCount() { return count; }
}

// io.thecodeforge — dsa tutorial

public class VisualizeIslands {
    public static void printGrid(char[][] grid) {
        for (char[] row : grid) {
            for (char c : row) System.out.print(c + " ");
            System.out.println();
        }
        System.out.println("---");
    }

    public static void dfs(char[][] grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return;
        if (grid[r][c] != '1') return;
        grid[r][c] = 'X'; // mark visited
        printGrid(grid);
        dfs(grid, r-1, c); dfs(grid, r+1, c);
        dfs(grid, r, c-1); dfs(grid, r, c+1);
    }

    public static void main(String[] args) {
        char[][] grid = {
            {'1','1','0'},
            {'1','0','0'},
            {'0','0','1'}
        };
        printGrid(grid);
        int count = 0;
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++)
                if (grid[i][j] == '1') { count++; dfs(grid, i, j); }
        System.out.println("Islands: " + count);
    }
}

// io.thecodeforge — dsa tutorial

public class VisualizeUnionFind {
    static int[] parent;
    static void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra != rb) parent[rb] = ra;
    }
    static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    static void printState() {
        for (int i = 0; i < parent.length; i++)
            System.out.print(parent[i] + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        // 3x3 grid: 0 1 2 / 3 4 5 / 6 7 8
        char[][] grid = {{'1','1','0'},{'0','1','0'},{'0','0','1'}};
        parent = new int[9];
        for (int i = 0; i < 9; i++) parent[i] = i;

        for (int r = 0; r < 3; r++) {
            for (int c = 0; c < 3; c++) {
                if (grid[r][c] == '0') continue;
                int idx = r * 3 + c;
                if (c > 0 && grid[r][c-1] == '1') union(idx, idx-1);
                if (r > 0 && grid[r-1][c] == '1') union(idx, idx-3);
            }
        }
        printState();
        int islands = 0;
        for (int i = 0; i < 9; i++)
            if (grid[i/3][i%3] == '1' && parent[i] == i) islands++;
        System.out.println("Islands: " + islands);
    }
}