โ† Paytm questions

Minimum number of days for rotten fruits

Filed under Paytm

Free read 2 of 3

Confirm 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

  1. Confirm grid dimensions, representation of rotten/fresh cells, and that propagation happens level-by-level (BFS).

Solution

O(M * N) time, O(M * N) space

Python
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.