The O(n) Club: Old Man and the Sea of Zeros

The O(n) Club: Old Man and the Sea of Zeros

⚡ TL;DR

Given a city grid of land (1) and water (0), you get one chance to turn water into land. Your goal? Connect as many parks (islands) as possible in one dramatic flip. Brute forcing every flip is so O(n⁴) it hurts. Smarter? DFS-label your islands, map their sizes, and only then try clever flips—like this:

// Core Java approach
for (each cell) {
  if (cell == 1 and not yet labeled) {
    dfs to label this island
    map islandId -> area
  }
}
for (each 0 cell) {
  use a Set to gather unique adjacent islandIds
  sum their areas plus one (for your flip)
  keep the max
}

🧠 How Devs Usually Mess This Up

Ever finish a feature and realize you just double-billed the same client? It happens here too:

• Counting the Same Island Twice: If you don’t use a Set when gathering neighbor islands, you might count your biggest park two or more times. That’s both illegal and embarrassing.
• All Land, No Water: The grid is already an island? Don’t return zero—return n * n! Don’t punish yourself for perfection.
• Union-Find Envy: Drool over Union-Find if you must, but really: plain DFS works here and your brain will thank you.

🔍 What’s Actually Going On

Imagine you’re city planner for a chaotic town: each park is an island separated by roads. You only have enough concrete grass for one empty lot. Drop it in the right spot, and—BOOM—you just built Central Park. Label every patch first (so you know what connects to what), then look for the “one flip to rule them all.”

🛠️ PseudoCode

• Step 1: Label and Size
  • Loop through the grid. If you find a 1 that hasn’t been labeled, DFS-label the whole island starting there.
  • Record the size of each island with its unique label in a map.

  // DFS to label and count
  int islandId = 2;
  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
      if (grid[i][j]==1)
        sizeMap.put(islandId, dfsCount(grid, i, j, islandId++));

• Step 2: Best-Flip Computation
  • For every 0 in the grid, gather all unique neighboring island IDs with a set.
  • Sum those islands’ sizes, add 1 for the flip itself, and keep track of the max.

  for (each 0 cell):
    Set<Integer> neighbors = new HashSet<>();
    int tmp = 1;
    for (each neighbor direction)
      if (island id > 1) neighbors.add(id);
    for (int id : neighbors) tmp += sizeMap.get(id);
    max = Math.max(max, tmp);

• Edge Case: No 0s? Return n * n.

💻 The Code

public int largestIsland(int[][] grid) {
    int n = grid.length;
    Map<Integer, Integer> sizeMap = new HashMap<>();
    int label = 2;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (grid[i][j]==1) {
                sizeMap.put(label, labelIsland(grid, i, j, label));
                label++;
            }
        }
    }
    int max = 0;
    boolean seenZero = false;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (grid[i][j]==0) {
                seenZero = true;
                Set<Integer> neighbors = new HashSet<>();
                for (int[] d : DIRS) {
                    int ni = i+d[0], nj = j+d[1];
                    if (ni>=0 && ni<n && nj>=0 && nj<n && grid[ni][nj]>1) {
                        neighbors.add(grid[ni][nj]);
                    }
                }
                int sum = 1;
                for (int id : neighbors) sum += sizeMap.get(id);
                max = Math.max(max, sum);
            }
        }
    }
    return seenZero ? max : n*n;
}
private final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
private int labelIsland(int[][] grid, int i, int j, int label) {
    if (i<0||j<0||i>=grid.length||j>=grid.length||grid[i][j]!=1) return 0;
    grid[i][j]=label;
    int res = 1;
    for (int[] d : DIRS) res += labelIsland(grid, i+d[0], j+d[1], label);
    return res;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Double-counting adjacent islands? Don’t. That’s set abuse, my friend.
• Grid mutation: DFS labeling scribbles all over your input. Need the original? Clone before chaos.
• All 1’s? Return the full grid. No creative penalty for paradise.
• Runtime: O(n²) time and space. Not beach-body fast, but good enough for any interview island hop.

🧠 Interviewer Brain-Tattoo

“Real grid hustlers label before they flip. Don’t merge everything twice—unless you like debugging existential crises instead of code.”