Rotten Oranges Problem - BFS in Matrix

You are given an m x n grid representing a box of oranges. Each cell of the grid can have one of the following values:

• 0: an empty cell
• 1: a fresh orange
• 2: a rotten orange

Each minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Your task is to return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Understanding the Problem

We are given a 2D grid (matrix) that represents a box of oranges. Each cell in the grid can have one of the following values:

• 0 — an empty cell (no orange)
• 1 — a fresh orange
• 2 — a rotten orange

Every minute, a rotten orange will cause all directly adjacent fresh oranges (up, down, left, right) to become rotten. Our task is to calculate the minimum number of minutes that must pass until no cell has a fresh orange. If it's not possible for all the fresh oranges to rot, we should return -1.

Step-by-Step Solution with Example

Step 1: Understand the input

Let’s consider the following input grid:

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

Here, we have one rotten orange at the top-left corner (0,0), and the rest are fresh (1s), except a few empty cells (0s).

Step 2: Choose the right strategy

To simulate the spread of rot over time, we use Breadth-First Search (BFS). We treat all initially rotten oranges as the starting points of BFS and process them level by level (minute by minute).

Step 3: Initialize the BFS queue

We enqueue all the rotten oranges along with their time = 0. We also count how many fresh oranges are initially present. This helps us track when all fresh ones have been rotted.

Step 4: BFS traversal

For each rotten orange in the queue, we visit its four neighbors (up, down, left, right). If any neighbor is a fresh orange, we turn it rotten, decrement the fresh count, and enqueue it with time +1.

Step 5: Track the time

We maintain a variable time to track the number of minutes taken to rot all reachable fresh oranges. It is updated as we process new levels in the BFS queue.

Step 6: Check if all fresh oranges are rotted

Once the BFS is done, we check if any fresh oranges are left. If so, return -1 because they were unreachable. Otherwise, return the maximum time it took to rot all oranges.

Step 7: Apply to our example

Initially rotten orange at (0,0) rots its neighbors one by one:

• Minute 1: (0,1), (1,0) become rotten
• Minute 2: (0,2), (1,1)
• Minute 3: (2,1)
• Minute 4: (2,2)

All fresh oranges are now rotten. Total time taken: 4 minutes.

Edge Cases

Case 1: All oranges already rotten or no fresh oranges

If there are no fresh oranges, return 0 since no rotting is needed.

Case 2: Fresh oranges exist but no rotten oranges

There is no way to rot the fresh oranges. Return -1.

Case 3: Some fresh oranges are isolated

If a fresh orange is completely surrounded by empty cells or other fresh ones and cannot be reached by a rotten one, it will remain fresh. Again, return -1.

Finally

This problem helps us understand how to simulate processes over time using BFS in a grid. Always begin by identifying the sources (in this case, initially rotten oranges) and process outward in waves. By tracking time and counting fresh oranges, we can determine the exact moment all fresh oranges have been infected—or if it's impossible.

1. Initialize a queue and count of fresh oranges.
2. Add all initially rotten oranges to the queue with timestamp 0.
3. While the queue is not empty:
1. Pop an orange from the queue.
2. For each of the 4 directions:
1. If the adjacent cell has a fresh orange, rot it, decrement fresh count, and add to queue with incremented time.
4. If fresh count becomes 0, return the last recorded time. Else return -1.

#include <stdio.h>
#define MAX 100

int queue[MAX][3], front = 0, rear = 0;

void enqueue(int r, int c, int t) {
    queue[rear][0] = r;
    queue[rear][1] = c;
    queue[rear][2] = t;
    rear++;
}

void dequeue(int *r, int *c, int *t) {
    *r = queue[front][0];
    *c = queue[front][1];
    *t = queue[front][2];
    front++;
}

int orangesRotting(int grid[3][3], int rows, int cols) {
    int fresh = 0, time = 0;
    int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) enqueue(r, c, 0);
            if (grid[r][c] == 1) fresh++;
        }
    }

    while (front < rear) {
        int r, c, t;
        dequeue(&r, &c, &t);
        if (t > time) time = t;

        for (int i = 0; i < 4; i++) {
            int nr = r + directions[i][0];
            int nc = c + directions[i][1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                grid[nr][nc] = 2;
                fresh--;
                enqueue(nr, nc, t + 1);
            }
        }
    }
    return fresh == 0 ? time : -1;
}

int main() {
    int grid[3][3] = {{2,1,1},{1,1,0},{0,1,1}};
    printf("Minutes to rot all oranges: %d\n", orangesRotting(grid, 3, 3));
    return 0;
}

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int orangesRotting(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    queue<tuple<int, int, int>> q;
    int fresh = 0, time = 0;

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) q.emplace(r, c, 0);
            if (grid[r][c] == 1) fresh++;
        }
    }

    int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

    while (!q.empty()) {
        auto [r, c, t] = q.front(); q.pop();
        time = max(time, t);

        for (auto& dir : directions) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                grid[nr][nc] = 2;
                fresh--;
                q.emplace(nr, nc, t + 1);
            }
        }
    }
    return fresh == 0 ? time : -1;
}

int main() {
    vector<vector<int>> grid = {{2,1,1},{1,1,0},{0,1,1}};
    cout << "Minutes to rot all oranges: " << orangesRotting(grid) << endl;
    return 0;
}

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh += 1

    directions = [(0,1), (1,0), (0,-1), (-1,0)]
    time = 0

    while queue:
        r, c, t = queue.popleft()
        time = max(time, t)
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                queue.append((nr, nc, t + 1))

    return time if fresh == 0 else -1

print("Minutes to rot all oranges:", oranges_rotting([[2,1,1],[1,1,0],[0,1,1]]))

import java.util.*;

public class RottingOranges {
    public static int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int fresh = 0, time = 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, 0});
                if (grid[r][c] == 1) fresh++;
            }
        }

        int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], t = curr[2];
            time = Math.max(time, t);

            for (int[] dir : directions) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.offer(new int[]{nr, nc, t + 1});
                }
            }
        }
        return fresh == 0 ? time : -1;
    }

    public static void main(String[] args) {
        int[][] grid = {{2,1,1},{1,1,0},{0,1,1}};
        System.out.println("Minutes to rot all oranges: " + orangesRotting(grid));
    }
}

function orangesRotting(grid) {
  const rows = grid.length, cols = grid[0].length;
  const queue = [];
  let fresh = 0, time = 0;

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

  const directions = [[0,1],[1,0],[0,-1],[-1,0]];

  while (queue.length > 0) {
    const [r, c, t] = queue.shift();
    time = Math.max(time, t);
    for (const [dr, dc] of directions) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
        grid[nr][nc] = 2;
        fresh--;
        queue.push([nr, nc, t + 1]);
      }
    }
  }

  return fresh === 0 ? time : -1;
}

console.log("Minutes to rot all oranges:", orangesRotting([[2,1,1],[1,1,0],[0,1,1]]));

package main

import (
	"fmt"
)

type Point struct {
	r, c, t int
}

func orangesRotting(grid [][]int) int {
	rows, cols := len(grid), len(grid[0])
	queue := []Point{}
	fresh := 0
	directions := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == 2 {
				queue = append(queue, Point{r, c, 0})
			} else if grid[r][c] == 1 {
				fresh++
			}
		}
	}
	time := 0
	for len(queue) > 0 {
		curr := queue[0]
		queue = queue[1:]
		time = max(time, curr.t)
		for _, d := range directions {
			nr, nc := curr.r + d[0], curr.c + d[1]
			if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 {
				grid[nr][nc] = 2
				fresh--
				queue = append(queue, Point{nr, nc, curr.t + 1})
			}
		}
	}
	if fresh == 0 {
		return time
	}
	return -1
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	grid := [][]int{{2,1,1},{1,1,0},{0,1,1}}
	fmt.Println("Minutes to rot all oranges:", orangesRotting(grid))
}

use std::collections::VecDeque;

fn oranges_rotting(grid: &mut Vec<Vec<i32>>) -> i32 {
    let rows = grid.len();
    let cols = grid[0].len();
    let mut queue = VecDeque::new();
    let mut fresh = 0;
    let directions = [(0,1),(1,0),(0,-1),(-1,0)];

    for r in 0..rows {
        for c in 0..cols {
            if grid[r][c] == 2 {
                queue.push_back((r, c, 0));
            } else if grid[r][c] == 1 {
                fresh += 1;
            }
        }
    }

    let mut time = 0;
    while let Some((r, c, t)) = queue.pop_front() {
        time = time.max(t);
        for (dr, dc) in &directions {
            let nr = r as isize + dr;
            let nc = c as isize + dc;
            if nr >= 0 && nr < rows as isize && nc >= 0 && nc < cols as isize &&
               grid[nr as usize][nc as usize] == 1 {
                grid[nr as usize][nc as usize] = 2;
                fresh -= 1;
                queue.push_back((nr as usize, nc as usize, t + 1));
            }
        }
    }
    if fresh == 0 { time } else { -1 }
}

fn main() {
    let mut grid = vec![vec![2,1,1], vec![1,1,0], vec![0,1,1]];
    println!("Minutes to rot all oranges: {}", oranges_rotting(&mut grid));
}

fun orangesRotting(grid: Array<IntArray>): Int {
    val rows = grid.size
    val cols = grid[0].size
    val queue = ArrayDeque<Triple<Int, Int, Int>>()
    var fresh = 0
    val directions = arrayOf(
        intArrayOf(0, 1), intArrayOf(1, 0),
        intArrayOf(0, -1), intArrayOf(-1, 0)
    )

    for (r in 0 until rows) {
        for (c in 0 until cols) {
            if (grid[r][c] == 2) queue.add(Triple(r, c, 0))
            if (grid[r][c] == 1) fresh++
        }
    }

    var time = 0
    while (queue.isNotEmpty()) {
        val (r, c, t) = queue.removeFirst()
        time = maxOf(time, t)
        for ((dr, dc) in directions) {
            val nr = r + dr
            val nc = c + dc
            if (nr in 0 until rows && nc in 0 until cols && grid[nr][nc] == 1) {
                grid[nr][nc] = 2
                fresh--
                queue.add(Triple(nr, nc, t + 1))
            }
        }
    }

    return if (fresh == 0) time else -1
}

fun main() {
    val grid = arrayOf(intArrayOf(2,1,1), intArrayOf(1,1,0), intArrayOf(0,1,1))
    println("Minutes to rot all oranges: ${orangesRotting(grid)}")
}

import Foundation

func orangesRotting(_ grid: inout [[Int]]) -> Int {
    let rows = grid.count, cols = grid[0].count
    var queue: [(Int, Int, Int)] = []
    var fresh = 0, time = 0
    let directions = [(0,1),(1,0),(0,-1),(-1,0)]

    for r in 0..<rows {
        for c in 0..<cols {
            if grid[r][c] == 2 {
                queue.append((r, c, 0))
            } else if grid[r][c] == 1 {
                fresh += 1
            }
        }
    }

    while !queue.isEmpty {
        let (r, c, t) = queue.removeFirst()
        time = max(time, t)
        for (dr, dc) in directions {
            let nr = r + dr, nc = c + dc
            if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 {
                grid[nr][nc] = 2
                fresh -= 1
                queue.append((nr, nc, t + 1))
            }
        }
    }
    return fresh == 0 ? time : -1
}

var grid = [[2,1,1],[1,1,0],[0,1,1]]
print("Minutes to rot all oranges:", orangesRotting(&grid))

function orangesRotting(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  let queue: [number, number, number][] = [];
  let fresh = 0, time = 0;

  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) fresh++;
    }
  }

  const directions = [[0,1],[1,0],[0,-1],[-1,0]];

  while (queue.length) {
    const [r, c, t] = queue.shift()!;
    time = Math.max(time, t);
    for (const [dr, dc] of directions) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
        grid[nr][nc] = 2;
        fresh--;
        queue.push([nr, nc, t + 1]);
      }
    }
  }

  return fresh === 0 ? time : -1;
}

console.log("Minutes to rot all oranges:", orangesRotting([[2,1,1],[1,1,0],[0,1,1]]));

Time complexity

Space complexity

O(m * n)

In the worst case, the queue may hold all the oranges in the grid, especially if they're all rotten or become rotten one after another.