Minimum number of days for rotten fruits
Filed under Paytm
Free read 2 of 3Confirm grid dimensions, representation of rotten/fresh cells, and that propagation happens level-by-level (BFS).
The question
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 fruit, or 2 representing a rotten fruit. Every minute, any fresh fruit that is 4-directionally adjacent to a rotten fruit becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh fruit. If this is impossible, return -1.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- grid[i][j] is 0, 1, or 2.
Examples
- Input
- grid = [[2,1,1],[1,1,0],[0,1,1]]
- Output
- 4
- Why
- Minutes pass and rotten fruits spread to adjacent fresh fruits until all are rotten after 4 steps.
Approach
Confirm grid dimensions, representation of rotten/fresh cells, and that propagation happens level-by-level (BFS).
Simulate minute-by-minute infection by scanning the grid repeatedly until no changes occur. Inefficient and complex to track.
Multi-source BFS. Initialize a queue with all initially rotten cells (2s) and count fresh fruits (1s). Pop from queue, infect neighbors, decrement fresh count, and push new rotten cells with incremented time.
Grid has zero fresh fruits to begin with (return 0), or fresh fruits remain uninfected at the end (return -1).
Solution
O(M * N) time, O(M * N) space
from collections import deque
def orangesRotting(grid):
m, n = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
queue.append((r, c, 0))
elif grid[r][c] == 1:
fresh += 1
time = 0
while queue:
r, c, time = queue.popleft()
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc, time + 1))
return time if fresh == 0 else -1
Tips
- What they are testing: Test grids with no fresh fruits initially, grids where some fresh fruits are completely isolated (unreachable), and a 1x1 grid.
- Common mistake: Using DFS instead of BFS; rotten fruits spread simultaneously in all directions, requiring a multi-source breadth-first search.
Related Paytm questions
Collected from public candidate posts and coding forums. Updated Nov 2026.