Jobs

Interviews

Discussions

Rotting Oranges

Medium

Asked by:

+26

More companies

295 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.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1, or 2.

Try coding it in LeetCode

Rotting Oranges

Medium

Asked by:

+20

More companies

295 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.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1, or 2.

Try coding it in LeetCode

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 dimensions of the grid (M and N), and what are the constraints on their values (e.g., minimum size, maximum size)?
Can the grid be empty, or can a row or column be empty?
Is it possible for all oranges to be initially rotten (all 2s)? If so, what should be returned?
What should be returned if there are no fresh oranges initially (i.e., only 0s and 2s)?
Are the grid dimensions guaranteed to be consistent (i.e., all rows have the same number of columns)?

Brute Force Solution

Approach

We are simulating the process of oranges rotting over time. The brute force method involves repeatedly checking the entire grid to see which fresh oranges can become rotten in the next minute.

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

Start by identifying all the oranges that are already rotten.
In each minute, look at every single orange on the grid.
For each fresh orange, check if it is adjacent (up, down, left, or right) to any of the currently rotten oranges.
If a fresh orange is next to a rotten one, mark it as rotten for the next minute.
After checking all oranges, update the grid to reflect the newly rotten ones.
Keep track of how many minutes have passed.
Repeat this process of checking and updating until no more fresh oranges can become rotten.
Finally, check if there are any fresh oranges left. If so, it's impossible to rot them all. Otherwise, the total time passed is the answer.

Code Implementation

def oranges_rotting_brute_force(grid):
    rows = len(grid)
    columns = len(grid[0]) if rows > 0 else 0
    minutes_passed = 0
    fresh_oranges_count = 0
    rotten_oranges_locations = []

    # Count initial fresh oranges and find initially rotten ones
    for row_index in range(rows):
        for column_index in range(columns):
            if grid[row_index][column_index] == 1:
                fresh_oranges_count += 1
            elif grid[row_index][column_index] == 2:
                rotten_oranges_locations.append((row_index, column_index))

    # Keep simulating minutes as long as there are fresh oranges and rotting can occur
    while fresh_oranges_count > 0:
        newly_rotten_this_minute = []
        oranges_rotted_in_this_pass = False

        # Check every cell for fresh oranges adjacent to rotten ones
        for row_index in range(rows):
            for column_index in range(columns):
                if grid[row_index][column_index] == 1:
                    is_adjacent_to_rotten = False
                    # Check adjacent cells
                    for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        neighbor_row, neighbor_column = row_index + dr, column_index + dc
                        if 0 <= neighbor_row < rows and 0 <= neighbor_column < columns and grid[neighbor_row][neighbor_column] == 2:
                            is_adjacent_to_rotten = True
                            break

                    if is_adjacent_to_rotten:
                        newly_rotten_this_minute.append((row_index, column_index))
                        oranges_rotted_in_this_pass = True

        # If no oranges rotted in this pass, it means we can't rot any more
        if not oranges_rotted_in_this_pass:
            break

        # Update the grid and counts for the next minute
        for r, c in newly_rotten_this_minute:
            grid[r][c] = 2
            fresh_oranges_count -= 1
            rotten_oranges_locations.append((r,c))

        minutes_passed += 1

    # If there are still fresh oranges left, it's impossible to rot them all
    if fresh_oranges_count > 0:
        return -1
    else:
        return minutes_passed

Big(O) Analysis

Time Complexity

O(rows * cols) – Let 'rows' be the number of rows and 'cols' be the number of columns in the grid. In the worst case, the simulation might iterate through each cell of the grid multiple times. Each minute, we iterate through all cells to identify fresh oranges adjacent to rotten ones. Since a fresh orange can only become rotten once, and this process continues until no more fresh oranges can rot, each cell is effectively processed a constant number of times throughout the simulation. Thus, the total time complexity is proportional to the total number of cells, which is rows * cols.

Space Complexity

O(rows * cols) – The primary auxiliary space is used to store the locations of rotten oranges that need to be processed in the current and subsequent time steps. In the worst case, all oranges could initially be rotten or become rotten simultaneously, requiring storage for all cells in the grid. This collection of potentially rotten oranges can grow up to the size of the entire grid, which is rows * cols. Therefore, the auxiliary space complexity is proportional to the total number of cells in the grid.

Optimal Solution

Approach

This problem is about finding the minimum time for all fresh oranges to rot. The key idea is to simulate the rotting process layer by layer, similar to how a ripple spreads outwards, starting from the initially rotten oranges.

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

First, identify all the oranges that are already rotten and all the oranges that are fresh.
Imagine a 'rotting wave' starting from each rotten orange. This wave spreads to adjacent fresh oranges in one unit of time.
We can process this wave in 'time steps'. In each time step, all fresh oranges that are next to a rotten orange will become rotten.
Keep track of all the oranges that just became rotten in the current time step. These will be the source of the 'rotting wave' for the next time step.
Continue this process, expanding the 'rotting wave' outwards, until no more fresh oranges can be reached by the rot.
If, after the process stops, there are still some fresh oranges left, it means they are unreachable and will never rot. In this case, it's impossible to rot all oranges.
The total time taken is simply the number of time steps it took for the rotting to reach the farthest fresh orange, or until no more rotting could occur.

Code Implementation

from collections import deque

def orangesRotting(grid):
    rows = len(grid)
    columns = len(grid[0])
    rotten_oranges_queue = deque()
    fresh_oranges_count = 0
    time_elapsed = 0

    # Initialize queue with all rotten oranges and count fresh ones.
    for rowIndex in range(rows):
        for columnIndex in range(columns):
            if grid[rowIndex][columnIndex] == 2:
                rotten_oranges_queue.append((rowIndex, columnIndex, 0))
            elif grid[rowIndex][columnIndex] == 1:
                fresh_oranges_count += 1

    # Directions for adjacent cells: up, down, left, right.
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # Process rotten oranges layer by layer (BFS).
    while rotten_oranges_queue:
        currentRow, currentColumn, currentTime = rotten_oranges_queue.popleft()
        time_elapsed = max(time_elapsed, currentTime)

        # Explore adjacent cells.
        for dr, dc in directions:
            neighborRow = currentRow + dr
            neighborColumn = currentColumn + dc

            # Check if the neighbor is within grid bounds and is a fresh orange.
            if 0 <= neighborRow < rows and 0 <= neighborColumn < columns and grid[neighborRow][neighborColumn] == 1:
                grid[neighborRow][neighborColumn] = 2  # Mark as rotten.
                fresh_oranges_count -= 1
                rotten_oranges_queue.append((neighborRow, neighborColumn, currentTime + 1))

    # If there are still fresh oranges, they are unreachable.
    if fresh_oranges_count > 0:
        return -1

    return time_elapsed

Big(O) Analysis

Time Complexity

O(M * N) – Let M be the number of rows and N be the number of columns in the grid representing the oranges. Each orange cell is visited and processed at most a constant number of times. We initially scan the grid to find fresh and rotten oranges, taking O(M * N) time. Then, we use a Breadth-First Search (BFS) approach, processing each orange cell once when it becomes rotten. In the worst case, every cell might become rotten and be added to the queue. The BFS queue operations (enqueue and dequeue) and neighbor checks take constant time per cell. Therefore, the total time complexity is dominated by visiting each cell at most a few times, resulting in O(M * N).

Space Complexity

O(R*C) – The primary auxiliary data structure used is a queue to store the coordinates of rotten oranges that will spread the rot. In the worst case, all R*C cells in the grid could be added to the queue simultaneously if they are initially rotten or become rotten in the first time step. Therefore, the space complexity is proportional to the total number of cells in the grid, denoted as N, where N = R*C. This results in a space complexity of O(N) or O(R*C).

Edge Cases

Case	How to Handle
Empty grid (m=0 or n=0)	The solution should return 0 minutes immediately if the grid is empty or has zero dimensions, as there are no oranges to rot.
Grid with no fresh oranges initially	If there are no fresh oranges (value 1) present at the start, the rotting time is 0 minutes, regardless of rotten oranges or empty cells.
Grid with only empty cells (all 0s)	If the grid contains only empty cells, no oranges can ever rot, and the function should return 0 minutes if no fresh oranges were present, or -1 if fresh oranges were somehow expected but impossible to rot.
Grid with only fresh oranges and no rotten oranges to start	If there are fresh oranges but no rotten oranges to initiate the rotting process, it's impossible for all fresh oranges to rot, so return -1.
A single fresh orange is isolated and cannot be reached by any rotten orange	If a fresh orange is surrounded by empty cells or other fresh oranges with no path to a rotten orange, it will never rot, leading to an impossible scenario and a return value of -1.
All oranges are already rotten (all 2s)	If all oranges are already rotten, no time is needed for rotting, and the function should return 0.
A grid where fresh oranges form disconnected components, some reachable by rotten oranges and some not	The algorithm must correctly identify all fresh oranges that become rotten and return -1 if any fresh orange remains unrotten.
Very large grid dimensions leading to memory or time limits	A BFS approach using a queue is generally efficient for large grids as it visits each cell at most a constant number of times, scaling well with grid size.

Empty grid (m=0 or n=0)

How to Handle:

The solution should return 0 minutes immediately if the grid is empty or has zero dimensions, as there are no oranges to rot.

Grid with no fresh oranges initially

How to Handle:

If there are no fresh oranges (value 1) present at the start, the rotting time is 0 minutes, regardless of rotten oranges or empty cells.

Grid with only empty cells (all 0s)

How to Handle:

If the grid contains only empty cells, no oranges can ever rot, and the function should return 0 minutes if no fresh oranges were present, or -1 if fresh oranges were somehow expected but impossible to rot.

Grid with only fresh oranges and no rotten oranges to start

How to Handle:

If there are fresh oranges but no rotten oranges to initiate the rotting process, it's impossible for all fresh oranges to rot, so return -1.

A single fresh orange is isolated and cannot be reached by any rotten orange

How to Handle:

If a fresh orange is surrounded by empty cells or other fresh oranges with no path to a rotten orange, it will never rot, leading to an impossible scenario and a return value of -1.

All oranges are already rotten (all 2s)

How to Handle:

If all oranges are already rotten, no time is needed for rotting, and the function should return 0.

A grid where fresh oranges form disconnected components, some reachable by rotten oranges and some not

How to Handle:

The algorithm must correctly identify all fresh oranges that become rotten and return -1 if any fresh orange remains unrotten.

Very large grid dimensions leading to memory or time limits

How to Handle:

A BFS approach using a queue is generally efficient for large grids as it visits each cell at most a constant number of times, scaling well with grid size.

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 dimensions of the grid (M and N), and what are the constraints on their values (e.g., minimum size, maximum size)?
Can the grid be empty, or can a row or column be empty?
Is it possible for all oranges to be initially rotten (all 2s)? If so, what should be returned?
What should be returned if there are no fresh oranges initially (i.e., only 0s and 2s)?
Are the grid dimensions guaranteed to be consistent (i.e., all rows have the same number of columns)?

Brute Force Solution

Approach

We are simulating the process of oranges rotting over time. The brute force method involves repeatedly checking the entire grid to see which fresh oranges can become rotten in the next minute.

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

Start by identifying all the oranges that are already rotten.
In each minute, look at every single orange on the grid.
For each fresh orange, check if it is adjacent (up, down, left, or right) to any of the currently rotten oranges.
If a fresh orange is next to a rotten one, mark it as rotten for the next minute.
After checking all oranges, update the grid to reflect the newly rotten ones.
Keep track of how many minutes have passed.
Repeat this process of checking and updating until no more fresh oranges can become rotten.
Finally, check if there are any fresh oranges left. If so, it's impossible to rot them all. Otherwise, the total time passed is the answer.

Code Implementation

def oranges_rotting_brute_force(grid):
    rows = len(grid)
    columns = len(grid[0]) if rows > 0 else 0
    minutes_passed = 0
    fresh_oranges_count = 0
    rotten_oranges_locations = []

    # Count initial fresh oranges and find initially rotten ones
    for row_index in range(rows):
        for column_index in range(columns):
            if grid[row_index][column_index] == 1:
                fresh_oranges_count += 1
            elif grid[row_index][column_index] == 2:
                rotten_oranges_locations.append((row_index, column_index))

    # Keep simulating minutes as long as there are fresh oranges and rotting can occur
    while fresh_oranges_count > 0:
        newly_rotten_this_minute = []
        oranges_rotted_in_this_pass = False

        # Check every cell for fresh oranges adjacent to rotten ones
        for row_index in range(rows):
            for column_index in range(columns):
                if grid[row_index][column_index] == 1:
                    is_adjacent_to_rotten = False
                    # Check adjacent cells
                    for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        neighbor_row, neighbor_column = row_index + dr, column_index + dc
                        if 0 <= neighbor_row < rows and 0 <= neighbor_column < columns and grid[neighbor_row][neighbor_column] == 2:
                            is_adjacent_to_rotten = True
                            break

                    if is_adjacent_to_rotten:
                        newly_rotten_this_minute.append((row_index, column_index))
                        oranges_rotted_in_this_pass = True

        # If no oranges rotted in this pass, it means we can't rot any more
        if not oranges_rotted_in_this_pass:
            break

        # Update the grid and counts for the next minute
        for r, c in newly_rotten_this_minute:
            grid[r][c] = 2
            fresh_oranges_count -= 1
            rotten_oranges_locations.append((r,c))

        minutes_passed += 1

    # If there are still fresh oranges left, it's impossible to rot them all
    if fresh_oranges_count > 0:
        return -1
    else:
        return minutes_passed

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, identify all the oranges that are already rotten and all the oranges that are fresh.
Imagine a 'rotting wave' starting from each rotten orange. This wave spreads to adjacent fresh oranges in one unit of time.
We can process this wave in 'time steps'. In each time step, all fresh oranges that are next to a rotten orange will become rotten.
Keep track of all the oranges that just became rotten in the current time step. These will be the source of the 'rotting wave' for the next time step.
Continue this process, expanding the 'rotting wave' outwards, until no more fresh oranges can be reached by the rot.
If, after the process stops, there are still some fresh oranges left, it means they are unreachable and will never rot. In this case, it's impossible to rot all oranges.
The total time taken is simply the number of time steps it took for the rotting to reach the farthest fresh orange, or until no more rotting could occur.

Code Implementation

from collections import deque

def orangesRotting(grid):
    rows = len(grid)
    columns = len(grid[0])
    rotten_oranges_queue = deque()
    fresh_oranges_count = 0
    time_elapsed = 0

    # Initialize queue with all rotten oranges and count fresh ones.
    for rowIndex in range(rows):
        for columnIndex in range(columns):
            if grid[rowIndex][columnIndex] == 2:
                rotten_oranges_queue.append((rowIndex, columnIndex, 0))
            elif grid[rowIndex][columnIndex] == 1:
                fresh_oranges_count += 1

    # Directions for adjacent cells: up, down, left, right.
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # Process rotten oranges layer by layer (BFS).
    while rotten_oranges_queue:
        currentRow, currentColumn, currentTime = rotten_oranges_queue.popleft()
        time_elapsed = max(time_elapsed, currentTime)

        # Explore adjacent cells.
        for dr, dc in directions:
            neighborRow = currentRow + dr
            neighborColumn = currentColumn + dc

            # Check if the neighbor is within grid bounds and is a fresh orange.
            if 0 <= neighborRow < rows and 0 <= neighborColumn < columns and grid[neighborRow][neighborColumn] == 1:
                grid[neighborRow][neighborColumn] = 2  # Mark as rotten.
                fresh_oranges_count -= 1
                rotten_oranges_queue.append((neighborRow, neighborColumn, currentTime + 1))

    # If there are still fresh oranges, they are unreachable.
    if fresh_oranges_count > 0:
        return -1

    return time_elapsed

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty grid (m=0 or n=0)	The solution should return 0 minutes immediately if the grid is empty or has zero dimensions, as there are no oranges to rot.
Grid with no fresh oranges initially	If there are no fresh oranges (value 1) present at the start, the rotting time is 0 minutes, regardless of rotten oranges or empty cells.
Grid with only empty cells (all 0s)	If the grid contains only empty cells, no oranges can ever rot, and the function should return 0 minutes if no fresh oranges were present, or -1 if fresh oranges were somehow expected but impossible to rot.
Grid with only fresh oranges and no rotten oranges to start	If there are fresh oranges but no rotten oranges to initiate the rotting process, it's impossible for all fresh oranges to rot, so return -1.
A single fresh orange is isolated and cannot be reached by any rotten orange	If a fresh orange is surrounded by empty cells or other fresh oranges with no path to a rotten orange, it will never rot, leading to an impossible scenario and a return value of -1.
All oranges are already rotten (all 2s)	If all oranges are already rotten, no time is needed for rotting, and the function should return 0.
A grid where fresh oranges form disconnected components, some reachable by rotten oranges and some not	The algorithm must correctly identify all fresh oranges that become rotten and return -1 if any fresh orange remains unrotten.
Very large grid dimensions leading to memory or time limits	A BFS approach using a queue is generally efficient for large grids as it visits each cell at most a constant number of times, scaling well with grid size.

Empty grid (m=0 or n=0)

How to Handle:

The solution should return 0 minutes immediately if the grid is empty or has zero dimensions, as there are no oranges to rot.

Grid with no fresh oranges initially

How to Handle:

If there are no fresh oranges (value 1) present at the start, the rotting time is 0 minutes, regardless of rotten oranges or empty cells.

Grid with only empty cells (all 0s)

How to Handle:

Grid with only fresh oranges and no rotten oranges to start

How to Handle:

If there are fresh oranges but no rotten oranges to initiate the rotting process, it's impossible for all fresh oranges to rot, so return -1.

A single fresh orange is isolated and cannot be reached by any rotten orange

How to Handle:

If a fresh orange is surrounded by empty cells or other fresh oranges with no path to a rotten orange, it will never rot, leading to an impossible scenario and a return value of -1.

All oranges are already rotten (all 2s)

How to Handle:

If all oranges are already rotten, no time is needed for rotting, and the function should return 0.

A grid where fresh oranges form disconnected components, some reachable by rotten oranges and some not

How to Handle:

The algorithm must correctly identify all fresh oranges that become rotten and return -1 if any fresh orange remains unrotten.

Very large grid dimensions leading to memory or time limits

How to Handle:

A BFS approach using a queue is generally efficient for large grids as it visits each cell at most a constant number of times, scaling well with grid size.