Solving Rotting Oranges in JavaScript: Step-by-Step Guide

Introduction to the Rotting Oranges Problem

The Rotting Oranges problem is one of the most popular algorithmic challenges on platforms like LeetCode (Problem 994). It is a classic graph traversal problem that tests your understanding of Breadth-First Search (BFS) and multi-source shortest path algorithms. In this tutorial, we will walk through the problem, understand the underlying concepts, and build a complete JavaScript solution from scratch.

What Is the Rotting Oranges Problem?

You are given an m x n grid where each cell represents one of three states:

0 — an empty cell
1 — a fresh orange
2 — a rotten orange

Every minute, any fresh orange that is adjacent (horizontally or vertically) to a rotten orange becomes rotten. Your task is to determine the minimum number of minutes that must pass until no fresh orange remains in the grid. If it is impossible to rot all the fresh oranges, return -1.

Example Scenario

Consider the following grid:

[[2, 1, 1],
 [1, 1, 0],
 [0, 1, 1]]

At minute 0, only the top-left orange is rotten. After each minute, the rot spreads to adjacent fresh oranges. After 4 minutes, all reachable fresh oranges will have become rotten, so the answer is 4.

Now consider this grid:

[[2, 1, 1],
 [0, 1, 1],
 [1, 0, 1]]

Here, the bottom-left orange can never be reached by the rot because it is isolated. Therefore, the answer is -1.

Why This Problem Matters

The Rotting Oranges problem is more than just an interview exercise. It models real-world scenarios where something spreads through a network or grid over time. Understanding how to solve it teaches you several fundamental concepts:

Multi-source BFS: Unlike standard BFS that starts from a single node, this problem requires starting from multiple rotten oranges simultaneously.
Level-order traversal: Each "minute" corresponds to one level of BFS, making it a perfect example of level-by-level processing.
State propagation: The problem demonstrates how state changes propagate through a system, which is applicable in simulations, infection modeling, and network routing.
Edge case handling: You must account for grids with no fresh oranges, no rotten oranges, or unreachable fresh oranges.

From an interview perspective, this problem is frequently asked because it cleanly tests whether a candidate can identify when to use BFS, implement it correctly, and handle edge cases gracefully.

Understanding the Approach

Why BFS and Not DFS?

The key insight is that the rot spreads uniformly in all directions, one cell per minute. This is exactly the behavior of BFS, which explores all nodes at the current depth before moving to nodes at the next depth level. DFS, on the other hand, would explore one path deeply before backtracking, which does not naturally model simultaneous spreading.

Another critical reason is that BFS guarantees the shortest path in an unweighted graph. Since each step (minute) has equal cost, BFS will find the minimum time for each fresh orange to become rotten.

Multi-Source BFS Strategy

In a standard BFS, you start with a single source node. In this problem, you may have multiple rotten oranges at minute 0. The solution is to enqueue all rotten oranges initially and process them level by level. This effectively simulates all rotten oranges spreading simultaneously.

The algorithm works as follows:

Scan the grid to find all initially rotten oranges and count all fresh oranges.
Enqueue all rotten oranges with their positions and a time value of 0.
Process the queue level by level. For each rotten orange, check its four neighbors.
If a neighbor is a fresh orange, rot it, decrement the fresh count, and enqueue it with time + 1.
After the queue is empty, if there are still fresh oranges remaining, return -1. Otherwise, return the maximum time reached.

Step-by-Step Implementation in JavaScript

Let us now build the solution step by step. We will start with the function signature and gradually add each piece of logic.

Step 1: Function Signature and Initial Setup

We begin by defining the function and handling the most basic edge cases.

function orangesRotting(grid) {
  if (!grid || grid.length === 0) return -1;

  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let freshCount = 0;

  // Directions for adjacent cells: up, down, left, right
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  return 0; // placeholder
}

Here we define the grid dimensions, initialize an empty queue for BFS, a counter for fresh oranges, and an array of direction vectors that represent the four possible adjacent moves.

Step 2: Scan the Grid

Next, we iterate through every cell in the grid. We enqueue all rotten oranges and count all fresh oranges.

function orangesRotting(grid) {
  if (!grid || grid.length === 0) return -1;

  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let freshCount = 0;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  // Scan the grid for rotten and fresh oranges
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) {
        queue.push([r, c, 0]); // [row, col, minute]
      } else if (grid[r][c] === 1) {
        freshCount++;
      }
    }
  }

  // If there are no fresh oranges, return 0 immediately
  if (freshCount === 0) return 0;

  return -1; // placeholder
}

Notice that each queue entry stores the row, column, and the minute at which that orange became rotten. The initial rotten oranges all start at minute 0. Also, if there are no fresh oranges at all, we can immediately return 0 since no time is needed.

Step 3: BFS Traversal

Now we implement the core BFS loop. We dequeue each rotten orange, check its four neighbors, rot any fresh neighbors, and enqueue them with an incremented time value.

function orangesRotting(grid) {
  if (!grid || grid.length === 0) return -1;

  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let freshCount = 0;
  let minutes = 0;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) {
        queue.push([r, c, 0]);
      } else if (grid[r][c] === 1) {
        freshCount++;
      }
    }
  }

  if (freshCount === 0) return 0;

  // BFS traversal
  while (queue.length > 0) {
    const [row, col, time] = queue.shift();

    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;

      // Check bounds and whether the cell has a fresh orange
      if (
        newRow >= 0 && newRow < rows &&
        newCol >= 0 && newCol < cols &&
        grid[newRow][newCol] === 1
      ) {
        grid[newRow][newCol] = 2; // Rot the fresh orange
        freshCount--;
        minutes = time + 1;
        queue.push([newRow, newCol, time + 1]);
      }
    }
  }

  return freshCount === 0 ? minutes : -1;
}

This is the complete solution. Let us break down the BFS loop in detail:

We use queue.shift() to dequeue the front element. This gives us the row, column, and the time at which this orange became rotten.
For each of the four directions, we compute the neighbor's coordinates.
We check whether the neighbor is within bounds and contains a fresh orange (value 1).
If so, we mark it as rotten by setting it to 2, decrement the fresh count, update the minutes, and enqueue the newly rotten orange with time + 1.
After the BFS completes, we check if all fresh oranges have been rotted. If freshCount is 0, we return the elapsed minutes. Otherwise, we return -1.

Step 4: Testing the Solution

Let us test our solution with several test cases to verify correctness.

// Test case 1: Normal case
const grid1 = [
  [2, 1, 1],
  [1, 1, 0],
  [0, 1, 1]
];
console.log(orangesRotting(grid1)); // Expected: 4

// Test case 2: Impossible case
const grid2 = [
  [2, 1, 1],
  [0, 1, 1],
  [1, 0, 1]
];
console.log(orangesRotting(grid2)); // Expected: -1

// Test case 3: No fresh oranges
const grid3 = [
  [0, 2]
];
console.log(orangesRotting(grid3)); // Expected: 0

// Test case 4: All fresh, no rotten
const grid4 = [
  [1, 1],
  [1, 1]
];
console.log(orangesRotting(grid4)); // Expected: -1

// Test case 5: Single rotten orange
const grid5 = [
  [2]
];
console.log(orangesRotting(grid5)); // Expected: 0

// Test case 6: Multiple rotten sources
const grid6 = [
  [2, 1, 1],
  [1, 1, 1],
  [1, 1, 2]
];
console.log(orangesRotting(grid6)); // Expected: 2

Test case 6 is particularly interesting because it has two rotten oranges at opposite corners. The multi-source BFS handles this naturally because both rotten oranges are enqueued at minute 0, and the rot spreads from both simultaneously.

Optimizing the Queue with a Head Pointer

One performance concern with the current implementation is the use of queue.shift(). In JavaScript, shift() on an array has O(n) time complexity because it requires re-indexing all remaining elements. For large grids, this can significantly slow down the solution.

A simple optimization is to use a head pointer instead of calling shift(). We track an index that points to the current front of the queue and simply increment it after each dequeue operation.

function orangesRottingOptimized(grid) {
  if (!grid || grid.length === 0) return -1;

  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let freshCount = 0;
  let minutes = 0;
  let head = 0; // Pointer to the front of the queue
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) {
        queue.push([r, c, 0]);
      } else if (grid[r][c] === 1) {
        freshCount++;
      }
    }
  }

  if (freshCount === 0) return 0;

  while (head < queue.length) {
    const [row, col, time] = queue[head];
    head++; // Move the head pointer forward

    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;

      if (
        newRow >= 0 && newRow < rows &&
        newCol >= 0 && newCol < cols &&
        grid[newRow][newCol] === 1
      ) {
        grid[newRow][newCol] = 2;
        freshCount--;
        minutes = time + 1;
        queue.push([newRow, newCol, time + 1]);
      }
    }
  }

  return freshCount === 0 ? minutes : -1;
}

This optimization reduces the dequeue operation from O(n) to O(1), making the overall BFS traversal more efficient. While the asymptotic time complexity remains the same, the constant factor improvement is significant for large inputs.

Alternative Approach: Level-by-Level BFS

Another common way to implement multi-source BFS is to process the queue level by level, where each level corresponds to one minute. Instead of storing the time in each queue entry, we process all nodes at the current level before moving to the next.

function orangesRottingLevelByLevel(grid) {
  if (!grid || grid.length === 0) return -1;

  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let freshCount = 0;
  let minutes = 0;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) {
        queue.push([r, c]);
      } else if (grid[r][c] === 1) {
        freshCount++;
      }
    }
  }

  if (freshCount === 0) return 0;

  while (queue.length > 0 && freshCount > 0) {
    const levelSize = queue.length;

    for (let i = 0; i < levelSize; i++) {
      const [row, col] = queue.shift();

      for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;

        if (
          newRow >= 0 && newRow < rows &&
          newCol >= 0 && newCol < cols &&
          grid[newRow][newCol] === 1
        ) {
          grid[newRow][newCol] = 2;
          freshCount--;
          queue.push([newRow, newCol]);
        }
      }
    }

    minutes++;
  }

  return freshCount === 0 ? minutes : -1;
}

In this version, we capture the queue size at the start of each level and process exactly that many nodes. After processing all nodes at the current level, we increment the minutes counter. This approach is arguably more intuitive because it directly mirrors the concept of "each level equals one minute."

Note that we also added freshCount > 0 to the while loop condition. This is a small optimization that allows us to exit early once all fresh oranges have been rotted, avoiding unnecessary iterations.

Complexity Analysis

Understanding the time and space complexity of your solution is essential, especially in interview settings.

Time Complexity

The time complexity is O(m * n) where m is the number of rows and n is the number of columns. This is because:

We scan the entire grid once to find rotten and fresh oranges, which takes O(m * n) time.
During BFS, each cell is visited at most once (since we mark it as rotten before enqueuing it), so the BFS traversal also takes O(m * n) time.
The total time complexity is O(m * n) + O(m * n) = O(m * n).

Space Complexity

The space complexity is also O(m * n) in the worst case. This is because:

In the worst case, all cells could be rotten initially, and all of them would be enqueued, requiring O(m * n) space for the queue.
The directions array uses constant space O(1).
We modify the grid in place, so no additional grid-sized data structure is needed.

Best Practices

1. Always Handle Edge Cases First

Before diving into the main algorithm, check for edge cases such as an empty grid, a grid with no fresh oranges, or a grid with no rotten oranges. Handling these upfront makes your code more robust and easier to reason about.

// Edge cases to consider:
// - Empty grid: return -1
// - No fresh oranges: return 0
// - No rotten oranges but fresh oranges exist: return -1
// - Single cell grid

2. Avoid Mutating Input When Possible

In our solution, we modify the input grid directly by changing fresh oranges to rotten. While this saves space, it can cause issues if the caller expects the grid to remain unchanged. If immutability is required, create a copy of the grid first.

function orangesRottingImmutable(grid) {
  if (!grid || grid.length === 0) return -1;

  const rows = grid.length;
  const cols = grid[0].length;

  // Create a deep copy of the grid
  const gridCopy = grid.map(row => [...row]);

  // ... rest of the algorithm using gridCopy instead of grid
}

3. Use Meaningful Variable Names

Variable names like r, c, dr, and dc are acceptable in short loops, but for production code, consider more descriptive names like row, col, deltaRow, and deltaCol. This improves readability and maintainability.

4. Validate Input Thoroughly

In a production environment, you should validate that the grid contains only valid values (0, 1, or 2) and that all rows have the same length. Here is a helper function for validation:

function validateGrid(grid) {
  if (!Array.isArray(grid) || grid.length === 0) return false;

  const cols = grid[0].length;
  for (const row of grid) {
    if (!Array.isArray(row) || row.length !== cols) return false;
    for (const cell of row) {
      if (cell !== 0 && cell !== 1 && cell !== 2) return false;
    }
  }

  return true;
}

5. Consider Using a Proper Queue Data Structure

For large-scale applications, consider using a dedicated queue implementation rather than relying on JavaScript arrays. Libraries or custom implementations can provide true O(1) enqueue and dequeue operations.

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }

  enqueue(item) {
    this.items[this.tail] = item;
    this.tail++;
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    const item = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return item;
  }

  isEmpty() {
    return this.head === this.tail;
  }

  size() {
    return this.tail - this.head;
  }
}

Using this queue class, both enqueue and dequeue are O(1) operations, making it ideal for BFS implementations.

Common Pitfalls and How to Avoid Them

Pitfall 1: Forgetting to Check Bounds

When checking neighbors, always verify that the computed row and column are within the grid boundaries. Failing to do so will result in accessing undefined values or throwing errors.

// Correct bounds checking
if (
  newRow >= 0 && newRow < rows &&
  newCol >= 0 && newCol < cols &&
  grid[newRow][newCol] === 1
) {
  // process neighbor
}

Pitfall 2: Not Marking Visited Cells Immediately

A common mistake is to mark a cell as rotten only when it is dequeued rather than when it is enqueued. This can lead to the same cell being enqueued multiple times, causing incorrect results and wasted computation. Always mark the cell as visited (rotten) at the time of enqueuing.

// Correct: mark as rotten when enqueuing
grid[newRow][newCol] = 2;
freshCount--;
queue.push([newRow, newCol, time + 1]);

Pitfall 3: Incorrect Minute Calculation

In the time-stamped approach, make sure you update minutes with time + 1 each time you rot a fresh orange. The final value of minutes will be the time of the last orange that was rotted, which is the correct answer.

In the level-by-level approach, be careful not to increment minutes after the last level. The condition freshCount > 0 in the while loop helps prevent this issue.

Pitfall 4: Using DFS Instead of BFS

DFS does not naturally find the shortest path in an unweighted graph. If you attempt to solve this problem with DFS, you would need to explore all possible paths and track the minimum time for each cell, which is far more complex and less efficient. Always recognize when BFS is the appropriate tool.

Visual Walkthrough

To solidify your understanding, let us walk through the BFS process visually for the following grid:

Initial grid (minute 0):
[[2, 1, 1],
 [1, 1, 0],
 [0, 1, 1]]

Queue: [(0,0,0)]
Fresh count: 6

At minute 0, we dequeue (0,0) and check its neighbors. Cells (0,1) and (1,0) are fresh, so we rot them and enqueue them with time 1.

After minute 1:
[[2, 2, 1],
 [2, 1, 0],
 [0, 1, 1]]

Queue: [(0,1,1), (1,0,1)]
Fresh count: 4

At minute 1, we dequeue (0,1) and (1,0). From (0,1), we rot (0,2). From (1,0), we rot (1,1). Both are enqueued with time 2.

After minute 2:
[[2, 2, 2],
 [2, 2, 0],
 [0, 1, 1]]

Queue: [(0,2,2), (1,1,2)]
Fresh count: 2

At minute 2, we dequeue (0,2) and (1,1). From (1,1), we rot (2,1). Cell (0,2) has no fresh neighbors. (2,1) is enqueued with time 3.

After minute 3:
[[2, 2, 2],
 [2, 2, 0],
 [0, 2, 1]]

Queue: [(2,1,3)]
Fresh count: 1

At minute 3, we dequeue (2,1) and rot (2,2), enqueuing it with time 4.

After minute 4:
[[2, 2, 2],
 [2, 2, 0],
 [0, 2, 2]]

Queue: [(2,2,4)]
Fresh count: 0

At minute 4, we dequeue (2,2), but it has no fresh neighbors. The queue is now empty, and freshCount is 0, so we return 4.

Extending the Problem

Once you are comfortable with the basic solution, consider these variations to deepen your understanding:

Variation 1: Diagonal Spread

What if the rot could also spread diagonally? Simply add four more direction vectors to the directions array:

const directions = [
  [-1, 0], [1, 0], [0, -1], [0, 1],   // cardinal directions
  [-1, -1], [-1, 1], [1, -1], [1, 1]   // diagonal directions
];

Variation 2: Return the Rotted Grid

Instead of returning just the number of minutes, return both the minutes and the final state of the grid. This is useful for visualization and debugging.

function orangesRottingWithGrid(grid) {
  // ... same BFS logic ...

  if (freshCount === 0) {
    return { minutes, grid };
  }
  return { minutes: -1, grid };
}

Variation 3: Multiple Orange Types

Consider a scenario where there are different types of rot that spread at different rates or compete with each other. This would require tracking which type of rot reaches each cell first, adding a layer of complexity to the BFS.

Conclusion

The Rotting Oranges problem is an excellent example of how Breadth-First Search can be applied to grid-based spreading problems. By understanding the multi-source BFS pattern, you gain a powerful tool that applies to a wide range of problems, from infection modeling to network propagation. The key takeaways are to identify when BFS is appropriate, enqueue all sources simultaneously, mark cells as visited at enqueue time, and handle edge cases diligently. With the step-by-step implementation, optimization techniques, and best practices covered in this tutorial, you are now well-equipped to solve this problem confidently in JavaScript and adapt the approach to similar challenges you may encounter.