Rotting Oranges - Practice Coding Problems

Rotting Oranges - Problem

You are given an m x n grid where each cell can have one of three values:

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

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

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

Input & Output

Example 1 — Standard Grid

$ Input: grid = [[2,1,1],[1,1,0],[0,1,1]]

› Output: 4

💡 Note: Initially one rotten orange at (0,0). After 1 minute: (0,1) and (1,0) rot. After 2 minutes: (0,2), (1,1) rot. After 3 minutes: (2,1) rots. After 4 minutes: (2,2) rots. All fresh oranges are now rotten.

Example 2 — Impossible Case

$ Input: grid = [[2,1,1],[0,1,1],[1,0,1]]

› Output: -1

💡 Note: The fresh orange at (2,0) is isolated by empty cells and cannot be reached by the spreading rot from (0,0). Some fresh oranges will remain forever fresh.

Example 3 — No Fresh Oranges

$ Input: grid = [[0,2]]

› Output: 0

💡 Note: There are no fresh oranges to rot, so 0 minutes are needed.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 10
grid[i][j] is 0, 1, or 2

Visualization

Tap to expand

Understanding the Visualization

Input Grid

3×3 grid with fresh (1), rotten (2), and empty (0) cells

Spreading Process

Rot spreads to 4-directionally adjacent fresh oranges each minute

Result

Return total minutes needed or -1 if impossible

Key Takeaway

🎯 Key Insight: Use multi-source BFS to simulate simultaneous spreading from all rotten oranges

Asked in

A Amazon 42 M Microsoft 28 G Google 24 B Bloomberg 18

The optimal solution uses multi-source BFS to simulate the simultaneous spreading of rot from all initially rotten oranges. The key insight is that all rotten oranges spread at the same time, so we process them level by level. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Multi-Source BFS	O(m×n)	O(m×n)	Use BFS starting from all initially rotten oranges simultaneously
Simulation Approach	O(m×n×k)	O(1)	Simulate each minute by checking all cells repeatedly

Multi-Source BFS — Algorithm Steps

Find all initially rotten oranges, add to queue
For each time unit, process all current rotten oranges
Add newly rotten oranges to queue for next time
Continue until queue is empty

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Add all initially rotten oranges to queue with time 0

Process Level

Process all oranges at current time, add neighbors to queue

Next Level

Continue with next time level until queue empty

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int row, col, time;
} QueueItem;

int solution(int** grid, int gridSize, int* gridColSize) {
    if (gridSize == 0 || gridColSize[0] == 0) return 0;
    
    int m = gridSize, n = gridColSize[0];
    QueueItem queue[m * n];
    int front = 0, rear = 0;
    int freshCount = 0;
    
    // Find all initially rotten oranges and count fresh ones
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) {
                queue[rear++] = (QueueItem){i, j, 0};
            } else if (grid[i][j] == 1) {
                freshCount++;
            }
        }
    }
    
    if (freshCount == 0) return 0;
    
    int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int maxTime = 0;
    
    while (front < rear) {
        QueueItem current = queue[front++];
        int row = current.row, col = current.col, time = current.time;
        
        for (int d = 0; d < 4; d++) {
            int newRow = row + directions[d][0];
            int newCol = col + directions[d][1];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && 
                grid[newRow][newCol] == 1) {
                
                grid[newRow][newCol] = 2;
                freshCount--;
                maxTime = (time + 1 > maxTime) ? time + 1 : maxTime;
                queue[rear++] = (QueueItem){newRow, newCol, time + 1};
            }
        }
    }
    
    return freshCount == 0 ? maxTime : -1;
}

int main() {
    // For simplicity, assume small grid size
    int grid[3][3] = {{2,1,1},{1,1,0},{0,1,1}};
    int* gridPtr[3] = {grid[0], grid[1], grid[2]};
    int gridColSize[3] = {3, 3, 3};
    
    int result = solution(gridPtr, 3, gridColSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Each cell is visited at most once during BFS traversal

✓ Linear Growth

Space Complexity

O(m×n)

Queue can store up to m×n cells in worst case

⚡ Linearithmic Space

286.2K Views

High Frequency

~15 min Avg. Time

8.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Multi-Source BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler