Jobs

Interviews

Discussions

Rotting Oranges

Medium

Apple

5 views

Topics:

ArraysGraphs

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 orange, or
2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

For example, consider the following grid:

[[2,1,1],[1,1,0],[0,1,1]]

In this case, the function should return 4 because it takes 4 minutes for all fresh oranges to rot.

Another example:

[[2,1,1],[0,1,1],[1,0,1]]

Here, the function should return -1 because the orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Lastly, if we have:

[[0,2]]

The function should return 0 since there are no fresh oranges at minute 0.

Write a function to solve this problem efficiently.

Rotting Oranges

Medium

Apple

5 views

Topics:

ArraysGraphs

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 orange, or
2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

For example, consider the following grid:

[[2,1,1],[1,1,0],[0,1,1]]

In this case, the function should return 4 because it takes 4 minutes for all fresh oranges to rot.

Another example:

[[2,1,1],[0,1,1],[1,0,1]]

Here, the function should return -1 because the orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Lastly, if we have:

[[0,2]]

The function should return 0 since there are no fresh oranges at minute 0.

Write a function to solve this problem efficiently.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for the grid elements? Are they limited to 0, 1, and 2?
What should I return if there are no fresh oranges initially?
Can the grid be empty or null? What about rows or columns with zero length?
If no oranges rot, or all are already rotten, should I return 0?
Are the dimensions of the grid (rows and columns) guaranteed to be within certain bounds?

Brute Force Solution

Approach

The brute force approach is like watching the oranges rot in real-time and meticulously tracking what happens. We repeatedly simulate the rotting process, checking every orange in every round, until no more oranges can rot. This continues until we either rot all the fresh oranges or reach a point where no more rotting can occur.

Here's how the algorithm would work step-by-step:

Examine every orange in the grid to see if it's rotten.
If an orange is rotten, check its immediate neighbors (up, down, left, and right).
If any of those neighbors are fresh, mark them as 'will rot' in the next time step.
Repeat this process for all rotten oranges.
Once you've checked all oranges and marked those that will rot, update the grid to make those marked oranges rotten.
Count one time step or minute of rotting.
Repeat the whole process (steps 1-6) again and again until no more fresh oranges are turning rotten during a time step.
Finally, check if any fresh oranges still remain in the grid. If so, it's impossible to rot all oranges, and we return -1; otherwise, return the number of time steps it took.

Code Implementation

def rotting_oranges_brute_force(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    minutes_elapsed = 0

    while True:
        oranges_to_rot = []

        # Iterate through the grid to find rotten oranges
        for row in range(number_of_rows):
            for column in range(number_of_columns):
                if grid[row][column] == 2:
                    #Check adjacent cells for fresh oranges to rot.
                    if row > 0 and grid[row-1][column] == 1:
                        oranges_to_rot.append((row-1, column))
                    if row < number_of_rows - 1 and grid[row+1][column] == 1:
                        oranges_to_rot.append((row+1, column))
                    if column > 0 and grid[row][column-1] == 1:
                        oranges_to_rot.append((row, column-1))
                    if column < number_of_columns - 1 and grid[row][column+1] == 1:
                        oranges_to_rot.append((row, column+1))

        #If no oranges were rotted this round, check to exit.
        if not oranges_to_rot:
            break

        #Mark fresh oranges as rotten after checking neighbors.
        for row, column in oranges_to_rot:
            grid[row][column] = 2
        minutes_elapsed += 1

        #Check if any fresh oranges remain
        fresh_oranges_exist = False
        for row in range(number_of_rows):
            for column in range(number_of_columns):
                if grid[row][column] == 1:
                    fresh_oranges_exist = True
                    break
            if fresh_oranges_exist:
                break

        if fresh_oranges_exist and not oranges_to_rot:
            return -1

    #After the loop, fresh oranges can still exist
    for row in range(number_of_rows):
        for column in range(number_of_columns):
            if grid[row][column] == 1:
                return -1

    return minutes_elapsed

Big(O) Analysis

Time Complexity

O(m*n*t) – The algorithm iterates until no more oranges rot. In the worst case, it might have to iterate over the entire grid multiple times, where m and n are the dimensions of the grid (rows and columns). In each iteration (time step), we traverse all m*n cells. 't' represents the number of time steps or iterations required for all possible oranges to rot, which in the worst case could depend on the grid size itself. Thus, the overall time complexity is approximately O(m*n*t), where t depends on the worst case distances between fresh oranges and rotten oranges.

Space Complexity

O(1) – The brute force approach primarily operates directly on the input grid and uses a few variables for iteration and counting. Although the explanation mentions marking oranges as 'will rot', this is done in-place on the grid itself or by using a constant number of variables. Therefore, the algorithm's auxiliary space usage does not scale with the size of the grid, denoted as N, where N is the number of cells in the grid, and it remains constant.

Optimal Solution

Approach

The best way to solve this problem is to simulate the rotting process step by step. We treat the grid like a map and track how the rot spreads from existing rotten oranges to nearby fresh ones. This approach avoids repeatedly checking the same oranges.

Here's how the algorithm would work step-by-step:

First, find all the rotten oranges and place them in a waiting line.
Then, imagine the rotting happens in rounds. In each round, take each rotten orange from the waiting line and check its neighbors (up, down, left, and right).
If a neighbor is a fresh orange, make it rotten and add it to the back of the waiting line for the next round.
Count how many rounds it takes for all fresh oranges to become rotten. If there are fresh oranges left after all possible rounds, it's impossible for them to rot.
The final count of rounds is the minimum time needed for all oranges to rot.

Code Implementation

def rotting_oranges(grid):
    rows = len(grid)
    cols = len(grid[0])
    rotten_oranges_queue = []
    fresh_oranges_count = 0
    
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 2:
                rotten_oranges_queue.append((row, col))
            elif grid[row][col] == 1:
                fresh_oranges_count += 1
    
    minutes_elapsed = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    # Start the rotting process simulation.
    while rotten_oranges_queue:
        next_level_rotten_oranges = []

        # Process all oranges rotting at the current minute
        for row, col in rotten_oranges_queue:
            for delta_row, delta_col in directions:
                new_row = row + delta_row
                new_col = col + delta_col

                if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == 1:
                    # Mark fresh orange as rotten.
                    grid[new_row][new_col] = 2
                    fresh_oranges_count -= 1
                    next_level_rotten_oranges.append((new_row, new_col))
        
        if next_level_rotten_oranges:
            minutes_elapsed += 1

        # The next level becomes current.
        rotten_oranges_queue = next_level_rotten_oranges
    
    # If any fresh oranges remain, it's impossible.
    if fresh_oranges_count > 0:
        return -1

    return minutes_elapsed

Big(O) Analysis

Time Complexity

O(m*n) – We iterate through the m*n grid once initially to identify the rotten oranges, which takes O(m*n) time. In the worst-case scenario, where the rot spreads one orange at a time, we might visit each cell a constant number of times (at most 4, checking neighbors) during the rotting process. Thus, the breadth-first search (BFS) propagation of the rot also takes O(m*n) time. Combining these, the overall time complexity is O(m*n) + O(m*n), which simplifies to O(m*n), where m and n are the dimensions of the grid.

Space Complexity

O(N) – The algorithm uses a waiting line (queue) to store the coordinates of rotten oranges. In the worst-case scenario, all oranges in the grid could be rotten initially, so the queue might contain all N cells of the grid, where N is the total number of cells in the grid (rows * columns). Therefore, the auxiliary space used by the queue can grow linearly with the input size N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 immediately since no oranges exist.
Grid with no oranges (all cells are 0)	Return 0 immediately since no oranges exist to rot.
Grid with only fresh oranges (all cells are 1)	Return -1 since oranges will never rot.
Grid with only rotten oranges (all cells are 2)	Return 0 since all oranges are already rotten.
Grid with one rotten orange and the rest fresh oranges	The solution should correctly calculate the time for all fresh oranges to rot.
Grid with dimensions 1x1	The solution should correctly handle this minimal grid.
Grid with a very large number of oranges and a large grid size	The BFS approach should handle large grids efficiently, but consider potential memory usage if extremely large.
Disjoint fresh orange groups where some groups cannot be reached by rotten oranges	Return -1 if any fresh oranges remain after processing all possible rotting steps.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for the grid elements? Are they limited to 0, 1, and 2?
What should I return if there are no fresh oranges initially?
Can the grid be empty or null? What about rows or columns with zero length?
If no oranges rot, or all are already rotten, should I return 0?
Are the dimensions of the grid (rows and columns) guaranteed to be within certain bounds?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Examine every orange in the grid to see if it's rotten.
If an orange is rotten, check its immediate neighbors (up, down, left, and right).
If any of those neighbors are fresh, mark them as 'will rot' in the next time step.
Repeat this process for all rotten oranges.
Once you've checked all oranges and marked those that will rot, update the grid to make those marked oranges rotten.
Count one time step or minute of rotting.
Repeat the whole process (steps 1-6) again and again until no more fresh oranges are turning rotten during a time step.
Finally, check if any fresh oranges still remain in the grid. If so, it's impossible to rot all oranges, and we return -1; otherwise, return the number of time steps it took.

Code Implementation

def rotting_oranges_brute_force(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    minutes_elapsed = 0

    while True:
        oranges_to_rot = []

        # Iterate through the grid to find rotten oranges
        for row in range(number_of_rows):
            for column in range(number_of_columns):
                if grid[row][column] == 2:
                    #Check adjacent cells for fresh oranges to rot.
                    if row > 0 and grid[row-1][column] == 1:
                        oranges_to_rot.append((row-1, column))
                    if row < number_of_rows - 1 and grid[row+1][column] == 1:
                        oranges_to_rot.append((row+1, column))
                    if column > 0 and grid[row][column-1] == 1:
                        oranges_to_rot.append((row, column-1))
                    if column < number_of_columns - 1 and grid[row][column+1] == 1:
                        oranges_to_rot.append((row, column+1))

        #If no oranges were rotted this round, check to exit.
        if not oranges_to_rot:
            break

        #Mark fresh oranges as rotten after checking neighbors.
        for row, column in oranges_to_rot:
            grid[row][column] = 2
        minutes_elapsed += 1

        #Check if any fresh oranges remain
        fresh_oranges_exist = False
        for row in range(number_of_rows):
            for column in range(number_of_columns):
                if grid[row][column] == 1:
                    fresh_oranges_exist = True
                    break
            if fresh_oranges_exist:
                break

        if fresh_oranges_exist and not oranges_to_rot:
            return -1

    #After the loop, fresh oranges can still exist
    for row in range(number_of_rows):
        for column in range(number_of_columns):
            if grid[row][column] == 1:
                return -1

    return minutes_elapsed

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find all the rotten oranges and place them in a waiting line.
Then, imagine the rotting happens in rounds. In each round, take each rotten orange from the waiting line and check its neighbors (up, down, left, and right).
If a neighbor is a fresh orange, make it rotten and add it to the back of the waiting line for the next round.
Count how many rounds it takes for all fresh oranges to become rotten. If there are fresh oranges left after all possible rounds, it's impossible for them to rot.
The final count of rounds is the minimum time needed for all oranges to rot.

Code Implementation

def rotting_oranges(grid):
    rows = len(grid)
    cols = len(grid[0])
    rotten_oranges_queue = []
    fresh_oranges_count = 0
    
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 2:
                rotten_oranges_queue.append((row, col))
            elif grid[row][col] == 1:
                fresh_oranges_count += 1
    
    minutes_elapsed = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    # Start the rotting process simulation.
    while rotten_oranges_queue:
        next_level_rotten_oranges = []

        # Process all oranges rotting at the current minute
        for row, col in rotten_oranges_queue:
            for delta_row, delta_col in directions:
                new_row = row + delta_row
                new_col = col + delta_col

                if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == 1:
                    # Mark fresh orange as rotten.
                    grid[new_row][new_col] = 2
                    fresh_oranges_count -= 1
                    next_level_rotten_oranges.append((new_row, new_col))
        
        if next_level_rotten_oranges:
            minutes_elapsed += 1

        # The next level becomes current.
        rotten_oranges_queue = next_level_rotten_oranges
    
    # If any fresh oranges remain, it's impossible.
    if fresh_oranges_count > 0:
        return -1

    return minutes_elapsed

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 immediately since no oranges exist.
Grid with no oranges (all cells are 0)	Return 0 immediately since no oranges exist to rot.
Grid with only fresh oranges (all cells are 1)	Return -1 since oranges will never rot.
Grid with only rotten oranges (all cells are 2)	Return 0 since all oranges are already rotten.
Grid with one rotten orange and the rest fresh oranges	The solution should correctly calculate the time for all fresh oranges to rot.
Grid with dimensions 1x1	The solution should correctly handle this minimal grid.
Grid with a very large number of oranges and a large grid size	The BFS approach should handle large grids efficiently, but consider potential memory usage if extremely large.
Disjoint fresh orange groups where some groups cannot be reached by rotten oranges	Return -1 if any fresh oranges remain after processing all possible rotting steps.