Tomato Timer

Moderate
0/80
1 upvote

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
3 3
2 1 1
1 1 0
0 1 1
Sample Output 1 :
4
Explanation of sample input 1 :
Initially, the rotten tomato is at (0, 0).
The matrix is:
2 1 1
1 1 0
0 1 1

At time 1, tomatoes at (0, 1) and (1, 0) become rotten.
The matrix becomes:
2 2 1
2 1 0
0 1 1

At time 2, the tomato at (1, 1) becomes rotten.
The matrix becomes:
2 2 1
2 2 0
0 1 1

At time 3, tomatoes at (0, 2) and (2, 1) become rotten.
The matrix becomes:
2 2 2
2 2 0
0 2 1

At time 4, the tomato at (2, 2) becomes rotten.
The matrix becomes:
2 2 2
2 2 0
0 2 2

All fresh tomatoes are rotten. The minimum time is 4.
Sample Input 2 :
3 3
2 1 2
1 0 1
1 1 1
Sample Output 2 :
-1
Hint

Consider this problem as finding the shortest path in a grid, where rotten tomatoes spread outwards level by level.

Approaches (1)
BFS

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'.
Time Complexity

O(M * N), where 'M' is the number of rows and 'N' is the number of columns in the matrix 'A'.

In the worst case, we visit each cell of the matrix at most a constant number of times (when adding to the queue and processing). Thus, the overall time complexity is of the order O(M * N).

Space Complexity

O(M * N), where 'M' is the number of rows and 'N' is the number of columns in the matrix 'A'.

In the worst case, the queue can hold the positions of all cells in the matrix. Thus, the overall space complexity is of the order O(M * N).

Code Solution
(100% EXP penalty)
Tomato Timer
Full screen
Console