Problem: Number of Islands (DFS/BFS)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Input:

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Output: 3

2. The Mental Model: "Sinking the Land"

This problem is about finding Connected Components in a Graph.

Every '1' is a node.
Every adjacent '1' is an edge.
An island is a group of nodes where you can reach any node from any other node.

The most efficient way to count them is to:

Scan the grid.
When you hit a '1', increment your counter.
Immediately "Sink" (visit) the entire island so you don't count its other parts later.

3. Visual Execution (The Sink logic)

graph TD
    subgraph "Before Sink"
        A[1,1] --- B[1,2]
        A --- C[2,1]
    end
    
    subgraph "After DFS"
        A1[#, #] --- B1[#, #]
        A1 --- C1[#, #]
    end
    
    DFS[DFS starts from 1,1 and paints everything to #]

4. Java Implementation (Optimal O(M*N))

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    
    int count = 0;
    int rows = grid.length;
    int cols = grid[0].length;
    
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            // 1. Found new land
            if (grid[r][c] == '1') {
                count++;
                // 2. Explore and sink the entire island
                sink(grid, r, c);
            }
        }
    }
    
    return count;
}

private void sink(char[][] grid, int r, int c) {
    // 3. Base Case: Out of bounds or water/visited
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == '0') {
        return;
    }
    
    // 4. Mark as visited (sink it)
    grid[r][c] = '0';
    
    // 5. Recurse in 4 directions
    sink(grid, r + 1, c);
    sink(grid, r - 1, c);
    sink(grid, r, c + 1);
    sink(grid, r, c - 1);
}

5. Verbal Interview Script (Staff Tier)

Interviewer: "How would you solve this if you weren't allowed to modify the input grid?"

You: "If the input grid is immutable, I would use a separate boolean[][] visited array of the same dimensions ($M \times N$). During the DFS, I would check the visited array instead of overwriting the grid characters. While this increases the space complexity from $O(1)$ extra space (excluding the recursion stack) to $O(M \times N)$, it is the proper engineering choice for production systems where data integrity and thread safety are paramount."

6. Staff-Level Follow-Ups

Follow-up 1: "Could we use BFS for this?"

The Answer: "Yes. Instead of recursion, I would use a Queue<int[]> to store coordinates. BFS would find islands in 'ripples' instead of going deep. BFS is often safer for massive grids because it avoids the JVM stack limit, but it uses slightly more memory on the heap to store the queue of frontiers."

Follow-up 2: "What if the grid is massive and spread across multiple machines?"

The Answer: "For distributed grids, I would use the Union-Find (Disjoint Set) algorithm. I would process the grid in chunks and then 'Union' the components that touch at the boundaries. This is the foundation of parallelized connected-component algorithms in systems like Apache Spark."

7. Performance Nuances (The Java Perspective)

Recursion Depth: The worst-case stack depth is $O(M \times N)$ for a grid that is entirely land. In Java, with a standard 1MB stack size, a $500 \times 500$ grid could easily trigger a StackOverflowError. For large production grids, always use an iterative BFS or a Stack-based DFS.
Primitive Chars: Using char[][] is memory-efficient because a char in Java is 2 bytes, unlike an int which is 4. However, since the problem only uses '0' and '1', a byte[][] or BitSet could reduce memory usage even further.

6. Staff-Level Verbal Masterclass (Communication)

Interviewer: "How would you defend this specific implementation in a production review?"

You: "In a mission-critical environment, I prioritize the Big-O efficiency of the primary data path, but I also focus on the Predictability of the system. In this implementation, I chose a recursive approach with memoization. While a recursive solution is more readable, I would strictly monitor the stack depth. If this were to handle skewed inputs, I would immediately transition to an explicit stack on the heap to avoid a StackOverflowError. From a memory perspective, I leverage primitive arrays to ensure that we minimize the garbage collection pauses (Stop-the-world) that typically plague high-throughput Java applications."

7. Global Scale & Distributed Pivot

When a problem like this is moved from a single machine to a global distributed architecture, the constraints change fundamentally.

Data Partitioning: We would shard the input space using Consistent Hashing. This ensures that even if our dataset grows to petabytes, any single query only hits a small subset of our cluster, maintaining logarithmic lookup times.
State Consistency: For problems involving state updates (like DP or Caching), we would use a Distributed Consensus protocol like Raft or Paxos to ensure that all replicas agree on the final state, even in the event of a network partition (The P in CAP theorem).

8. Performance Nuances (The Staff Perspective)

Cache Locality: Accessing a 2D matrix in row-major order (reading [i][j] then [i][j+1]) is significantly faster than column-major order in modern CPUs due to L1/L2 cache pre-fetching. I always structure my loops to align with how the memory is physically laid out.
Autoboxing and Generics: In Java, using List<Integer> instead of int[] can be 3x slower due to the overhead of object headers and constant wrapping. For the most performance-sensitive sections of this algorithm, I advocate for primitive specialized structures.

Key Takeaways

Every '1' is a node.
Every adjacent '1' is an edge.
An island is a group of nodes where you can reach any node from any other node.