Master the Rotten Oranges BFS Problem: Java Solution Explained

I often notice that the more technically proficient a person is, the simpler their explanations become—sometimes a single sentence is enough to convey the core issue.

Conversely, less experienced individuals tend to overwhelm listeners with jargon and lengthy background, which can obscure the real problem.

Interview Question: Rotten Oranges

The "Rotten Oranges" problem (LeetCode #994) describes a 2D grid where 0 represents empty cells, 1 fresh oranges, and 2 rotten oranges. Each minute, a rotten orange turns its adjacent fresh oranges (up, down, left, right) rotten. The task is to determine the minimum minutes required for all oranges to rot, or return -1 if impossible.

import java.util.*;

public class RottenOranges {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;
        // Initialize: add all rotten oranges to the queue and count fresh oranges
        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});
                } else if (grid[r][c] == 1) {
                    freshCount++;
                }
            }
        }
        if (freshCount == 0) return 0; // No fresh oranges
        int minutes = 0;
        int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!queue.isEmpty()) {
            int size = queue.size();
            boolean hasRotten = false;
            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                int r = cell[0], c = cell[1];
                for (int[] d : directions) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        freshCount--;
                        hasRotten = true;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
            if (hasRotten) minutes++;
        }
        return freshCount == 0 ? minutes : -1;
    }
    // Simple test
    public static void main(String[] args) {
        RottenOranges solver = new RottenOranges();
        int[][] grid = {
            {2,1,1},
            {1,1,0},
            {0,1,1}
        };
        System.out.println(solver.orangesRotting(grid)); // Output 4
    }
}

Key points analysis:

Initial state: all rotten oranges serve as BFS starting points.

Each BFS layer corresponds to one minute of spread.

After each layer, check if fresh oranges remain to decide the final minute count or return -1.

This problem is an excellent exercise for mastering BFS templates and queue operations, representing a fundamental graph traversal scenario frequently encountered in technical interviews.