Day 95 | Rotten Oranges

Today I solved a problem that was practically the same as yesterdays problem with a little variation. You are given an m x n grid where each cell can have one of these 3 values: 0 (representing an empty cell), 1 (representing a fresh orange), or 2 (representing a rotton orange). Every minute, an adjacent orange to a rotten orange becomes rotten. The task is to return the minimum number of minutes until all oranges are rotten. You return -1 if this is not possible.

This problem is practically the same as yesterdays problem, islands and treasure. Instead of distance, we are keeping track of time. Instead of islands and treasure, we have fresh oranges and rotten oranges. The same general idea is the same. What makes this problem a little more difficult is the fact that we have to validate that no fresh oranges exist in the end of the problem. What I mean by this is a rotten orange might end up never reaching a fresh orange. In this case, we'd have to return -1. So the question is, how can we keep track of this?

The Approach

The approach we are going to take is the exact same as yesterday. We are going to perform a bfs from multiple starting points (the rotten oranges). I'm not going to go too deeply into this part since I did yesterday, but lets focus on how we can validate the grid in the end. While initially searching for the rotten oranges to add to our queue, we are also going to be searching for fresh oranges. We can initialize a variable called freshCount. For every fresh orange that we find, we increment this counter. Now when we perform our BFS, for every fresh fruit that turns rotten, we can decrement the counter. Finally, we return -1 if this counter is not 0 and the minutes otherwise.

The Code

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        q = deque()
        freshCount = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 2:
                    q.append((r,c))
                if grid[r][c] == 1:
                    freshCount += 1
        minutes = 0
        directions = [[1,0], [0,1], [-1,0], [0,-1]]
        while(q and freshCount):
            for _ in range(len(q)):
                r,c = q.popleft()
                for rowAdd, colAdd in directions:
                    new_r, new_c = r + rowAdd, c + colAdd
                    if new_r >= 0 and new_c >= 0 and new_r < ROWS and new_c < COLS and grid[new_r][new_c] == 1:
                        q.append((new_r,new_c))
                        grid[new_r][new_c] = 2
                        freshCount -= 1
            minutes += 1
        return minutes if freshCount == 0 else -1        

Again, I'm not going to go into the BFS algorithm since I did yesterday, however as you can see, we initialize a freshCount to count the oranges in the grid. For every fresh orange we find, we increment it. Now within the bfs algorithm, every time we move to a cell that contains a fresh orange that turns rotten, we decrement the freshCount to maintain our counter. In the very end, we can return the minutes variable if freshCount is 0, otherwise we return -1 since we can never achieve a board with no fresh oranges.

Complexity Analysis

The time complexity of this solution is going to be O(m x n). This is because we process each cell on the board at most once. The space complexity is also going to be O(m x n) since this is going to be the max size of the queue.