Crack the Backend

Problem Statement

You are given a grid where each cell is: 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, any rotten orange rotts 4-directionally adjacent fresh oranges. Return the minimum number of minutes until no cell has a fresh orange. If it is impossible (some fresh cannot be reached by rotten), return -1.

Multi-source BFS: All initially rotten oranges are at "distance 0". We BFS from all of them at once; each level of the BFS corresponds to one minute. When we process a cell, we turn its fresh neighbors to rotten and enqueue them. We need to track how many fresh oranges remain; if after the BFS there is still fresh, return -1.

Key Observations

Enqueue all (r, c) where grid[r][c] == 2 with distance 0. Maintain a fresh count (number of 1's initially). In BFS: for each dequeued cell, check 4 neighbors; if a neighbor is fresh (1), set it to 2, decrement fresh, enqueue with dist+1. The answer is the maximum distance we assigned (or 0 if no fresh initially). After BFS, if fresh > 0 return -1.

Approach

High-level: Count fresh oranges. Queue all (r,c) with grid[r][c]==2, dist=0. BFS: for each (r,c,d), for each 4-neighbor with value 1, set to 2, fresh--, enqueue (nr,nc,d+1). Minutes = max d. If fresh>0 return -1 else return minutes (or 0).

Implementation

Java

public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length, fresh = 0;
    Queue<int[]> q = new ArrayDeque<>();

    for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++) {
        if (grid[i][j] == 1) {
            fresh++;
        }

        if (grid[i][j] == 2) {
            q.offer(new int[]{i, j, 0});
        }
    }

    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    int mins = 0;

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r=cur[0], c=cur[1], d=cur[2];
        mins = d;

        for (int[] dir : dirs) {
            int nr=r+dir[0], nc=c+dir[1];

            if (nr>=0&&nr<m&&nc>=0&&nc<n&&grid[nr][nc]==1) {
                grid[nr][nc]=2; fresh--; q.offer(new int[]{nr,nc,d+1});
            }
        }
    }

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

Test Cases

Example 1

Input

grid = [[2,1,1],[1,1,0],[0,1,1]]

Expected

4

Explanation

4 minutes to rot all.

Complexity Analysis

Time: O(m*n).
Space: O(m*n).

Follow-ups

Multiple rotten sources; different decay rates.