How Long Until Every Fresh Fruit Spoils

Medium25–30 min

Topics

GraphBFSMulti-Source BFSGrid

Companies

AmazonMicrosoftGoogleFlipkartAdobe

A crate is laid out as a grid. Each cell is empty (0), holds a fresh fruit (1) or holds a spoiled fruit (2). Every minute, every fresh fruit that touches a spoiled fruit on one of its four sides becomes spoiled. Return the minimum number of minutes after which no fresh fruit is left, or -1 if that never happens.

Think of each cell as a node, connected to its four neighbours: the spoilage spreads exactly like a breadth-first search that begins at all the spoiled fruits simultaneously.

Test Case 1:

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

Output:5

Explanation:The single spoiled fruit at the top-left infects its two neighbours in minute 1, and the spoilage spreads like a wave: cells at distance d from it are reached in minute d. The farthest fresh fruits, the top-right and bottom-right ones, are 5 steps away through the middle row.

Test Case 2:

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

Output:-1

Explanation:The empty slots cut the grid into two parts: the fresh fruits in the bottom row can never be reached.

Test Case 3:

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

Output:0

Explanation:There is no fresh fruit, so no time is needed.

Constraints

◆1 ≤ rows, cols ≤ 12; grid[r][c] is 0 (empty crate slot), 1 (fresh fruit) or 2 (spoiled fruit)
◆Every minute, each fresh fruit that is directly above, below, left or right of a spoiled fruit becomes spoiled (spoilage does not pass through empty slots or diagonally)
◆Return the minimum number of minutes until no fresh fruit remains. If some fresh fruit can never be reached, return -1. If there is no fresh fruit to begin with, return 0
◆The grid is a graph in which every cell is a node and cells that share a side are connected

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Simulate Minute by Minute, Rescanning the Whole Grid

Brute

Simulate the spoilage literally. In each round scan every cell; for every spoiled fruit, note the fresh neighbours that would spoil this minute. If nobody would spoil, stop. Otherwise turn all those neighbours to spoiled at once (deciding first and applying afterwards makes the round a single minute) and count one minute. At the end, any remaining fresh fruit means -1. Every round re-scans the whole grid, including the old spoiled cells that can no longer spread anything new, so a long winding path costs O(R·C) rounds of O(R·C) work.

TimeO((R·C)²)

SpaceO(R·C)

Java

Try it out

class Solution {
    public int minutesToSpoil(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};
        int minutes = 0;
        while (true) {
            List<int[]> spoiled = new ArrayList<>();
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] != 2) continue;
                    for (int d = 0; d < 4; d++) {
                        int nr = r + dr[d], nc = c + dc[d];
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                            spoiled.add(new int[]{nr, nc});
                        }
                    }
                }
            }
            if (spoiled.isEmpty()) break;
            for (int[] cell : spoiled) grid[cell[0]][cell[1]] = 2;
            minutes++;
        }
        for (int[] row : grid) {
            for (int v : row) {
                if (v == 1) return -1;
            }
        }
        return minutes;
    }
}

Optimal — Multi-Source Breadth-First Search, One Level per Minute

Optimal

Spoilage moves outward one step per minute from ALL spoiled fruits at the same time — exactly a breadth-first search that starts from many sources. Put every initially spoiled cell in a queue and count the fresh fruits. Then process the queue level by level: all cells currently in the queue are the ones that became spoiled in the previous minute; each spoils its fresh neighbours (mark them spoiled at once, decrease the fresh count, and queue them for the next minute). One level = one minute. Stop when the queue is empty or no fresh fruit is left; if fresh fruit remains, it was unreachable: -1. Each cell enters the queue at most once: O(R·C).

TimeO(R·C)