The O(n) Club: Max Area of Island — Because DFS Is Land Lord

The O(n) Club: Max Area of Island — Because DFS Is Land Lord

⚡ TL;DR

You get a grid of 0s (water) and 1s (land). Your mission, should you choose to accept it: find the size of the biggest island of connected land, only counting up/down/left/right neighbors — diagonals are forbidden by law and common sense.

// Java quick and dirty
int max = 0;
for (int i = 0; i < rows; i++) {
  for (int j = 0; j < cols; j++) {
    if (grid[i][j] == 1) {
      max = Math.max(max, dfs(grid, i, j));
    }
  }
}

🧠 How Devs Usually Mess This Up

Oh, where to begin? Here’s how even the best get beached:

• Diagonal Delusions: Accidentally treat diagonal connections as valid. Sorry, your island does not have WiFi corners. Stick to four cardinal moves.
• Endless Loops of Doom: If you don’t mark cells as visited (change that 1 to 0 ASAP), you’ll count the same patch forever and Java’s call stack will file for bankruptcy.
• Off-the-Map Panic: Neglecting boundary checks? Congratulations: ArrayIndexOutOfBoundsException. Real islands have edges. Your array does, too.
• Monogamous Mindset: Stopping after the first island? Buddy, there’s a whole archipelago out there. Keep looking.

🔍 What’s Actually Going On

Picture a robot (or you, pre-coffee) wandering a digital archipelago. Every time it lands on an undiscovered piece of land (cell == 1), it launches a caffeinated DFS expedition in all four cardinal directions. It marks every visited land cell as 0 (burn the bridge!) so it never counts the same patch twice. The biggest chunk it finds? That’s the answer. No diagonal shortcuts, no counting the same square twice, and if it wanders off the map, we bring it back quickly before the null pointer monsters get it.

🛠️ PseudoCode

• For each cell in the grid:
  • If it’s land (1), run DFS. Count the full area and update your max. Dive in, but never look back.
• DFS (Depth-First Search):
  • If we’re out of bounds or water (0), return 0. You’ve hit a wall or the sea.
  • Mark the land cell as visited (turn 1 into 0 before you do anything else).
  • Recursively DFS all four directions: up, down, left, right. Sum their areas into yours. Ignore diagonals like your last spam email.
  • Return the total patch size.

// Java-ish DFS
int dfs(int[][] grid, int i, int j) {
  if (i<0 || j<0 || i>=grid.length || j>=grid[0].length || grid[i][j]==0) return 0;
  grid[i][j]=0;
  int area=1;
  area += dfs(grid,i+1,j);
  area += dfs(grid,i-1,j);
  area += dfs(grid,i,j+1);
  area += dfs(grid,i,j-1);
  return area;
}

💻 The Code

public class MaxAreaOfIsland {
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    max = Math.max(max, dfs(grid, i, j));
                }
            }
        }
        return max;
    }
    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0)
            return 0;
        grid[i][j] = 0;
        int area = 1;
        area += dfs(grid, i + 1, j);
        area += dfs(grid, i - 1, j);
        area += dfs(grid, i, j + 1);
        area += dfs(grid, i, j - 1);
        return area;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Recursion Stack Meltdown: Too big an island? Java throws a tantrum (StackOverflow). For planet-sized inputs, try BFS or iterative DFS, or brag to your interviewer about it.
• Losing Track of Visited: If you don’t mark visited right away, you’ll count land like it’s a government census — badly and repeatedly. May the odds be in your favor.
• Time & Space: Each cell checked once — time and worst-case stack space are O(mn).
• Diagonal Temptation: Trust us, resist. Your interviewer definitely is.

🧠 Interviewer Brain-Tattoo

“There are only four directions on this map. If you stray, so does your code.” — The ghost of interviewers past