The O(n) Club: Rotting Oranges – How Fast Can You Spoil Lunch?

The O(n) Club: Rotting Oranges – How Fast Can You Spoil Lunch?

⚡ TL;DR

Staring at a grid of oranges where some are gross (rotten) and some are still clinging to hope (fresh)? As every minute ticks by, adjacent (up/down/left/right—not diagonal, this isn’t chess) fresh oranges catch the funk. For each minute, all rotten oranges rot their neighbors. Want to do this fast? Use BFS. If you can’t rot ‘em all, you’re out: return -1.

// Java starter pack
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
// Traverse grid: add rotten coords to queue and count fresh.
// Then, BFS the grid like it’s a pandemic simulator.

🧠 How Devs Usually Mess This Up

If you’re hand-writing a for-loop and updating each orange one-by-one, congratulations: you’re halfway to an O(n³) timesink. Common fails?

• Rotting one at a time: Thinking rot works one orange per minute. It’s a wave: all rotten oranges infect at once every round. BFS, people!
• Diagonal Hopes: Sorry, rot doesn’t travel diagonally. Stop making it harder for yourself.
• Minute Mishandling: Counting minutes when nothing actually rots. Only increment when something changes—otherwise it’s just you watching oranges.

🔍 What’s Actually Going On

BFS shines here like a janitor with a power washer. Each “minute” is a round—every rotten orange sends their “magic” to up/down/left/right fresh oranges. Those turn rotten and join the party (the queue) for the next minute. Eventually, either everything is gross, or some lone hipster oranges are walled off, forever pure.

Imagine a dance floor: rotten oranges with bad moves infect adjacent dancers each song (“minute”). When the music’s over, check for anyone dancing alone. If yes, party fail (-1). Otherwise, minutes = how many songs were played.

🛠️ PseudoCode

• Prep the Grid:

  Queue<int[]> queue = new LinkedList<>();
  int fresh = 0;
  // Loop through grid: if orange is rotten, queue its pos; if fresh, count up.

  Line everyone up, know who’s sick and who’s at risk.

• BFS (Rotting Party):

  int minutes = 0;
  while(!queue.isEmpty() && fresh > 0) {
    int size = queue.size();
    for(int i=0; i<size; i++) {
      int[] pos = queue.poll();
      // Infect each neighbor; if fresh, mark rotten, queue it, fresh--
    }
    minutes++;
  }

  Each minute, process only those who just joined the rot club. Only count the minute if something actually happened.

• Victory Lap:

  return (fresh == 0) ? minutes : -1;

  If someone’s left fresh, you lose—return -1 HQ style.

💻 The Code

public int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) queue.offer(new int[]{r, c});
            if (grid[r][c] == 1) fresh++;
        }
    }
    if (fresh == 0) return 0;
    int minutes = 0;
    int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
    while (!queue.isEmpty() && fresh > 0) {
        int sz = queue.size();
        for (int i = 0; i < sz; i++) {
            int[] pos = queue.poll();
            for (int[] d : dirs) {
                int x = pos[0] + d[0];
                int y = pos[1] + d[1];
                if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 1) {
                    grid[x][y] = 2;
                    queue.offer(new int[]{x, y});
                    fresh--;
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Isolated Oranges: Fresh oranges trapped by zeros—permanently healthy. Watch for them, or your code loops forever.
• Grid Out-of-Bounds: Don’t let your BFS wander off the edge—ArrayIndexOutOfBounds is one Stacktrace you don’t want.
• Time/Space Reality: Time: O(mn), Space: O(mn)—unless you invent teleporting rot, this is as good as it gets for a grid.
• Minute Counting: Increment minutes only when new rot spreads. If you find yourself adding time for no reason, take a coffee break.

🧠 Interviewer Brain-Tattoo

“When in doubt, remember: rot doesn’t travel alone. If your solution is rotting one orange at a time, so will your interview.”