The O(n) Club: Number of Islands — Why Diagonal Swimming Doesn’t Count

The O(n) Club: Number of Islands — Why Diagonal Swimming Doesn’t Count

⚡ TL;DR

Given a grid of ‘1’s (land) and ‘0’s (water), count how many separate islands exist. Only up, down, left, and right are valid treks—not diagonals, because apparently, islands are social distancing. Mark your visited ‘1’s so you don’t double-count. Here’s the caffeine-overdosed version in Java:

int numIslands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.length; ++r)
        for (int c = 0; c < grid[0].length; ++c)
            if (grid[r][c] == '1') {
                sink(grid, r, c);
                count++;
            }
    return count;
}
void sink(char[][] grid, int r, int c) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != '1')
        return;
    grid[r][c] = '0';
    sink(grid, r+1, c); sink(grid, r-1, c); sink(grid, r, c+1); sink(grid, r, c-1);
}

🧠 How Devs Usually Mess This Up

Let’s face it, most of us jump in thinking diagonal lands are BFFs, marking ‘1’s as fast as we can click, and then forget to actually mark them at all. The usual mistakes?

• Counting diagonally-adjacent ‘1’s as connected. Sorry, your island isn’t that inclusive.
• Not marking ‘1’s as visited. Welcome to Infinite Island: population, way too many.
• Ignoring the all-water, all-land, or empty-grid “exotic” edge cases. Yes, zero islands is a valid answer (and not a bug!).

🔍 What’s Actually Going On

Picture a chef wandering a kitchen with only four types of movement—no diagonal jazz hands. Every time they bump into a new potato (‘1’), they brown it (mark as visited), and follow it across the grid, orthogonally, until they’ve seasoned every bit of that particular mash. Then they go looking for the next. That’s your paint bucket tool in Photoshop, but with land and water instead of rainbow gradients.

🛠️ PseudoCode

• Loop over every grid cell.
  for each (r, c) in grid:
• If you find a ‘1’: start a “flood” (DFS/BFS) from there.
  if grid[r][c] == '1':
• During the flood, change every ‘1’ you touch to a ‘0’ (or whatever nonsense value you want) so you don’t revisit.
• When the flood ends: you’ve found an entire island, so increment the counter.
• Repeat until the grid’s as dry as your sense of humor.

• Marking as visited is the anti-cheat code for this problem. If you skip it, welcome to Groundhog Island.
• Diagonal pixels? The rules committee says, “Denied.” Stick to up, down, left, right.

💻 The Code

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int islands = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') {
                bfs(grid, r, c);
                islands++;
            }
        }
    }
    return islands;
}
 private void bfs(char[][] grid, int sr, int sc) {
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    Queue<int> q = new LinkedList<>();
    q.add(new int[] {sr, sc});
    grid[sr][sc] = '0';
    while (!q.isEmpty()) {
        int[] pos = q.poll();
        for (int d = 0; d < 4; d++) {
            int r = pos[0] + dr[d];
            int c = pos[1] + dc[d];
            if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] == '1') {
                grid[r][c] = '0';
                q.add(new int[] {r, c});
            }
        }
    }
}
</int>

⚠️ Pitfalls, Traps & Runtime Smacks

• All 0’s? Your code should return zero. No one vacations here.
• All 1’s? Just one island, unless you’re being extra and splitting it up yourself.
• Empty grid or null input? Beware the NullPointer Kraken.
• Recursive DFS on a warehouse-sized grid? You’ll stack overflow so hard you’ll invent a new runtime exception. BFS is less melodramatic.
• Modifying the input grid is fast—unless the interviewer is allergic. Then you’ll need an extra boolean[][] visited and a little more RAM.
• O(mn) time and (maybe) O(mn) space for worst-case piles of land.

🧠 Interviewer Brain-Tattoo

Every time you forget to mark a visited ‘1’, an interviewer gets a new reason to say, “Thanks, but we’ll keep looking.” Diagonal moves? That’s how legends are lost to the sea.