Prerequisites: Matrix, BFS.
Problem: Given an N x M matrix where each cell can have one of three values:
0representing an empty cell,1representing a fresh apple, or2representing a rotten apple.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten apple becomes rotten.
Find the minimum number of minutes that must elapse until no cell has a fresh apple. If this is impossible, return -1.
Solution Approach:
The core idea of the solution is to simulate the process of rotting apples in a grid. We start by initializing a queue to store the positions of rotten apples and counting the number of fresh apples in the grid. Then, in each iteration, we process all currently rotten apples by checking their adjacent cells. If a fresh apple is found adjacent to a rotten apple, it becomes rotten in the next minute, and we enqueue its position for further processing. This process continues until no fresh apples are left or until all reachable fresh apples have become rotten. Throughout the simulation, we track the number of minutes elapsed. If all fresh apples have been rotten after the simulation, we return the total number of minutes. Otherwise, if there are still fresh apples remaining but no more reachable rotten apples, it indicates that some fresh apples are unreachable and will never rot, so we return -1 to indicate that it’s impossible for all fresh apples to become rotten.
Time Complexity: O(N * M), where N is the number of rows and M is the number of columns in the grid. This is because we traverse each cell in the grid once during the initialization and the simulation process.
Space Complexity: O(N * M). This is primarily due to the usage of the queue to store the positions of rotten apples, which can potentially hold up to all the cells in the grid