Number of Islands

Concept

LeetCode #200. This is arguably the most famous Graph interview question in existence.
Problem: 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.

Input:
[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

The Implicit Graph

This problem doesn’t hand you an Adjacency List. It hands you a 2D Array.
However, a 2D Array is just a highly structured Graph.

• Every single cell [row][col] is a Node.
• The Edges are the mathematical neighbors: Up, Down, Left, Right.
• You do NOT need to build an Adjacency List! You can run DFS directly on the Matrix.

The Strategy

We must traverse the 2D grid like reading a book (top-left to bottom-right).

1. When we find a "1" (Land), we have discovered a brand new Island! We increment our islandCount.
2. But wait! If we keep looping, we will count the next piece of land on the exact same island as a “new” island.
3. We must launch a massive DFS infection starting from the "1". The DFS will plunge in all 4 directions, physically destroying the island by converting every "1" it touches into a "0" (or marking it visited).
4. By the time the DFS finishes, the entire physical island has been “sunk”.
5. We resume our outer loop. The next "1" we encounter is guaranteed to be a completely different island!

Implementation

// Time Complexity: O(M * N) (We visit every cell)
// Space Complexity: O(M * N) (Worst case Call Stack if the entire grid is one massive island)

function numIslands(grid: string[][]): number {
    if (!grid || grid.length === 0) return 0;
    
    const rows = grid.length;
    const cols = grid[0].length;
    let numIslands = 0;
    
    function sinkIslandDFS(r: number, c: number) {
        // 1. Boundary Checks: Did we fall off the edge of the map?
        if (r < 0 || c < 0 || r >= rows || c >= cols) return;
        
        // 2. Value Check: Is this water? Or is this land we already sank?
        if (grid[r][c] === "0") return;
        
        // 3. We are standing on Land ("1")! SINK IT to mark it as visited.
        grid[r][c] = "0";
        
        // 4. Launch DFS in all 4 directions to sink the rest of the island
        sinkIslandDFS(r - 1, c); // UP
        sinkIslandDFS(r + 1, c); // DOWN
        sinkIslandDFS(r, c - 1); // LEFT
        sinkIslandDFS(r, c + 1); // RIGHT
    }
    
    // The Outer Loop: Scan the entire map
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === "1") {
                // We found an unvisited piece of land!
                numIslands++;
                
                // Launch the DFS payload to sink the entire connected landmass
                sinkIslandDFS(r, c);
            }
        }
    }
    
    return numIslands;
}

The “Visited Matrix” Alternative

In the code above, we permanently mutated the input grid by turning "1"s into "0"s.
In a real-world software engineering job, mutating the input parameters of a function is often a terrible anti-pattern (you just destroyed the map that another function might need!).

If the interviewer says “Do not mutate the original grid”, you must allocate extra memory. You create a parallel 2D array of the exact same dimensions: const visited = new Array(rows).fill(false).... Instead of changing the grid to "0", you check if (visited[r][c]) return; and update visited[r][c] = true;.

Interview Questions

Q: A problem asks you to find the “Shortest Path in a Maze” from the top-left to the bottom-right. The maze is a 2D matrix of 0s (paths) and 1s (walls). Can you use DFS like Number of Islands?
A: No. You are looking for the shortest path. DFS will blindly plunge down the maze, potentially finding a valid path that takes 5,000 winding steps, entirely missing the 10-step straight line path right next to it. For shortest path on an unweighted 2D grid, you MUST use BFS with a Queue. You enqueue the starting coordinate [0,0], and ripple outwards level by level.