The O(n) Club: Island Perimeter — Don’t Forget to Subtract the Neighbors

The O(n) Club: Island Perimeter — Don’t Forget to Subtract the Neighbors

⚡ TL;DR

Calculate the perimeter of a single “island” (group of 1s) in a grid of 0s and 1s. Every land cell brings 4 edges to the party, but if it’s got a land buddy above or to the left, subtract 2 from the total. Java makes this as easy as undercooking instant ramen.

// Java — iterate and count
int perimeter = 0;
for (int i = 0; i < grid.length; i++) {
  for (int j = 0; j < grid[0].length; j++) {
    if (grid[i][j] == 1) {
      perimeter += 4;
      if (i > 0 && grid[i-1][j] == 1) perimeter -= 2;
      if (j > 0 && grid[i][j-1] == 1) perimeter -= 2;
    }
  }
}

🧠 How Devs Usually Mess This Up

Classic mistakes, coming right up:

• They sum 4 sides for every cell but forget to subtract for neighbors, accidentally creating a perimeter longer than every Amazon package delivery route combined.
• They boldly search for multiple islands when there’s only one, like checking ten times if you left the stove on (it’s off, relax).
• They include diagonals like the island is building bridges — diagonals don’t count. Island law.

🔍 What’s Actually Going On

Picture each land cell as a shy apartment tenant enclosing themselves with four cozy walls. If they have a neighbor above or to their left, they both lose one wall — not out of generosity, just physics. This ensures every shared wall is only counted once, guaranteed. Water is emotionally distant and offers no walls.

Still tempted to use DFS? That’s fine for weirdly-shaped islands or if you’re hoping for a stack overflow (the error, not the website). Iteration is just simpler and faster for this one.

🛠️ PseudoCode

• For every cell in the grid:
• If cell == 0: move on, nothing to see here.
• If cell == 1:
• Add 4 to perimeter.
• If cell above is 1: subtract 2 (shared wall).
• If cell left is 1: subtract 2 (shared wall again — we’re fair like that).
• End of loop: return perimeter. Boom, nailed it.

// Java-esque pseudocode
for (int row = 0; row < grid.length; row++) {
  for (int col = 0; col < grid[0].length; col++) {
    if (grid[row][col] == 1) {
      perimeter += 4;
      if (row > 0 && grid[row-1][col] == 1) perimeter -= 2;
      if (col > 0 && grid[row][col-1] == 1) perimeter -= 2;
    }
  }
}
return perimeter;

💻 The Code

public int islandPerimeter(int[][] grid) {
    int perimeter = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1) {
                perimeter += 4;
                if (i > 0 && grid[i - 1][j] == 1) perimeter -= 2;
                if (j > 0 && grid[i][j - 1] == 1) perimeter -= 2;
            }
        }
    }
    return perimeter;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Diagonal drama: Don’t count diagonal neighbors unless you’re building avant-garde beaches.
• DFS black hole: DFS can be epic, but only if you want to accidentally drown the JVM on a huge grid.
• One-island guarantee: No need to track “visited” cells or search for the lost city of Atlantis. You’ve got one island and that’s it.
• Complexity: Iterative: O(rows × cols). Your computer won’t even break a sweat.

🧠 Interviewer Brain-Tattoo

“Perimeters aren’t made by lonely cells — they’re made when neighboring cells forget to share walls. Subtract the neighbors, save the perimeter.”