Last Updated: 2 May, 2025

Tomato Timer

Moderate

Solve now

Problem statement

Given a 2D matrix 'A' of size 'M' x 'N' containing only integers 0, 1, and 2.

Each 2 represents a rotten tomato, each 1 represents a fresh tomato, and each 0 represents an empty cell. A rotten tomato at position (i, j) can rot any adjacent fresh tomato at (i-1, j), (i+1, j), (i, j-1), or (i, j+1) in one unit of time.

Find the minimum time required for all fresh tomatoes to become rotten. If it's impossible for all fresh tomatoes to rot, return -1.

For Example :

Let 'M' = 3, 'N' = 3, and 'A' =
2 1 1
1 1 0
0 1 1

Initially, the rotten tomato is at (0, 0).
After 1 minute, the fresh tomatoes at (0, 1) and (1, 0) become rotten.
The matrix becomes:
2 2 1
2 1 0
0 1 1

After 2 minutes, the tomato at (1, 1) becomes rotten (from (0,1) or (1,0)).
The matrix becomes:
2 2 1
2 2 0
0 1 1

After 3 minutes, the tomatoes at (0, 2) and (2, 1) become rotten.
The matrix becomes:
2 2 2
2 2 0
0 2 1

After 4 minutes, the tomato at (2, 2) becomes rotten.
The matrix becomes:
2 2 2
2 2 0
0 2 2
All fresh tomatoes have become rotten. The minimum time taken is 4.

Input Format :

The first line contains two integers, 'M' and 'N'.
The next 'M' lines contain 'N' integers each, representing the matrix 'A'.

Output Format :

Return the minimum time required for all fresh tomatoes to become rotten. Return -1 if this is not possible.

Note :

You don’t need to print anything. Just implement the given function.

Constraints :

1 <= 'M', 'N' <= 100
0 <= 'A[i][j]' <= 2

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

Use a Breadth-First Search (BFS) approach to simulate the rotting process.
Initialize a queue with the positions of all initially rotten tomatoes.
Count the total number of fresh tomatoes in the matrix.
Process the queue level by level, where each level represents one unit of time.
For each rotten tomato dequeued, check its adjacent cells.
If an adjacent cell contains a fresh tomato, mark it as rotten, add its position to the queue, and decrement the count of fresh tomatoes.
Keep track of the time taken (number of levels processed).
If the queue becomes empty and there are still fresh tomatoes left, it's impossible to rot all of them.

Algorithm:

Initialize a queue 'Q'.
Initialize a variable 'fresh_tomatoes' to count the number of 1s in the matrix 'A'.
Iterate through the matrix 'A' using row index 'i' from 0 to 'M - 1' and column index 'j' from 0 to 'N - 1' :
- If ( A[ i ][ j ] == 2 ) :
  - Enqueue the position ( i, j ) into 'Q'.
- If ( A[ i ][ j ] == 1 ) :
  - Increment 'fresh_tomatoes' by 1.
Initialize a variable 'minutes' to 0.
While ( 'Q' is not empty ) :
- Get the size of the current level, 'level_size', from 'Q'.
- If ( 'fresh_tomatoes' is 0 ) :
  - Break the loop.
- Iterate 'level_size' times :
  - Dequeue a position ( current_row, current_col ) from 'Q'.
  - Define possible adjacent directions: ( -1, 0 ), ( 1, 0 ), ( 0, -1 ), ( 0, 1 ).
  - For each direction ( dr, dc ) :
    - Calculate neighbor position: neighbor_row = current_row + dr, neighbor_col = current_col + dc.
      - If ( neighbor_row is within [0, M-1] and neighbor_col is within [0, N-1] and A[ neighbor_row ][ neighbor_col ] == 1 ) :
        Set A[ neighbor_row ][ neighbor_col ] to 2.
        Enqueue ( neighbor_row, neighbor_col ) into 'Q'.
        Decrement 'fresh_tomatoes' by 1.
- Increment 'minutes' by 1.
If ( 'fresh_tomatoes' > 0 ) :
- Return -1.
Else :
- Return 'minutes'.

Solve now