Jobs

Interviews

Discussions

Rotting Oranges #11 Most Asked

Medium

TikTok

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.

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 #11 Most Asked

Medium

TikTok

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.

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 should be returned if the grid initially contains no fresh oranges? Should that be considered 0 minutes?
Could the input grid be empty, or have zero rows or columns? How should I handle such cases?
Is it guaranteed that the grid will only contain the values 0, 1, and 2, or should I validate the input values?
What are the maximum dimensions of the grid, i.e., the upper bounds for 'm' and 'n'?
If the grid contains no rotten oranges to begin with but has fresh oranges, is the correct return value -1, as it's impossible for them to rot?

Brute Force Solution

Approach

Imagine we have a grid of fresh and rotten oranges. The brute force approach is to simulate the rotting process minute by minute, checking at each step what happens to all the fresh oranges.

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

First, take a snapshot of the grid at the very beginning.
Then, for the first minute, look at every single fresh orange in the grid.
For each fresh orange, check if it's next to a rotten one from the previous snapshot. If it is, mark it down to become rotten.
After checking every fresh orange, update the grid all at once with the newly rotten ones. This completes one minute.
Repeat this entire process minute by minute: take a new snapshot, find all fresh oranges that will rot, and then update the grid.
Keep track of how many minutes have passed.
If you get to a point where a minute passes but no new oranges rot, and there are still fresh ones left, it's impossible for them to ever rot. We stop and note this impossibility.
If all the oranges eventually become rotten, the answer is the total number of minutes that have passed.

Code Implementation

def rottingOranges(grid):
    if not grid:
        return -1

    rows = len(grid)
    cols = len(grid[0])
    minutes_passed = 0

    while True:
        oranges_to_rot_this_minute = []
        fresh_oranges_count = 0
        previous_grid_snapshot = [row[:] for row in grid]

        for row_index in range(rows):
            for col_index in range(cols):
                if previous_grid_snapshot[row_index][col_index] == 1:
                    fresh_oranges_count += 1
                    is_adjacent_to_rotten = False
                    # Check all four neighbors to see if any were rotten in the previous state.
                    for delta_row, delta_col in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        neighbor_row = row_index + delta_row
                        neighbor_col = col_index + delta_col

                        if 0 <= neighbor_row < rows and 0 <= neighbor_col < cols and previous_grid_snapshot[neighbor_row][neighbor_col] == 2:
                            is_adjacent_to_rotten = True
                            break
                    
                    if is_adjacent_to_rotten:
                        oranges_to_rot_this_minute.append((row_index, col_index))
        
        # If no oranges rotted this minute, the process stops.
        if not oranges_to_rot_this_minute:
            # If there are still fresh oranges left, it's impossible for them all to rot.
            if fresh_oranges_count > 0:
                return -1
            else:
                return minutes_passed

        # Update the grid with all newly rotten oranges for the next minute's simulation.
        for row_index, col_index in oranges_to_rot_this_minute:
            grid[row_index][col_index] = 2

        minutes_passed += 1

Big(O) Analysis

Time Complexity

O((R * C)^2) – Let R be the number of rows and C be the number of columns in the grid. In each minute of the simulation, the algorithm iterates through every single cell of the grid (R * C operations) to find fresh oranges. For each fresh orange found, it checks its neighbors, but the core cost is this full grid scan. This process repeats minute by minute until no more oranges can rot. In the worst-case scenario, where oranges rot one by one in a long chain, the number of minutes could be proportional to the total number of cells (R * C). Therefore, the total operations involve scanning the entire grid (R * C) for a number of minutes that could also be up to R * C, leading to a complexity of O((R * C) * (R * C)), which simplifies to O((R * C)^2).

Space Complexity

O(R * C) – The primary driver of auxiliary space is the snapshot of the grid taken at the beginning of each minute. This snapshot is essentially a copy of the input grid, requiring extra space proportional to the number of cells. In the worst case, we need a grid copy of size R rows by C columns, where R * C is the total number of cells in the grid.

Optimal Solution

Approach

The problem is like a wave spreading outwards simultaneously from all the initially rotten oranges. We can simulate this wave, minute by minute, to see how long it takes for all the fresh oranges to get caught in it.

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

First, take a quick look at the grid to count how many fresh oranges there are. Also, find all the oranges that are already rotten and put them aside as our starting points for the rot.
Imagine time passing in rounds, or minutes. For the first minute, the rot spreads from all the starting rotten oranges to their immediate fresh neighbors.
As these neighbors turn rotten, they become the new sources of rot for the next minute. So, in the second minute, the rot spreads from them.
Continue this process, with the rot spreading outwards in a layer-by-layer fashion each minute. Keep track of how many minutes have passed.
After the rot can't spread any further, check if any fresh oranges are still left. If there are, it means they were unreachable, and the task is impossible.
If all the fresh oranges that we initially counted are now rotten, the answer is the total number of minutes that have passed. If there were no fresh oranges to begin with, the time taken is zero.

Code Implementation

from collections import deque

def oranges_rotting(grid):
    if not grid:
        return 0

    number_of_rows = len(grid)
    number_of_cols = len(grid[0])
    fresh_oranges_count = 0
    rotten_oranges_queue = deque()

    for row_index in range(number_of_rows):
        for col_index in range(number_of_cols):
            if grid[row_index][col_index] == 1:
                fresh_oranges_count += 1
            elif grid[row_index][col_index] == 2:
                rotten_oranges_queue.append((row_index, col_index))

    minutes_elapsed = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    # The queue size represents all oranges that become rotten in the current minute.
    while rotten_oranges_queue and fresh_oranges_count > 0:

        number_rotten_in_current_minute = len(rotten_oranges_queue)
        for _ in range(number_rotten_in_current_minute):
            rotten_row, rotten_col = rotten_oranges_queue.popleft()

            for row_direction, col_direction in directions:
                neighbor_row = rotten_row + row_direction
                neighbor_col = rotten_col + col_direction

                if 0 <= neighbor_row < number_of_rows and 0 <= neighbor_col < number_of_cols and grid[neighbor_row][neighbor_col] == 1:
                    grid[neighbor_row][neighbor_col] = 2
                    rotten_oranges_queue.append((neighbor_row, neighbor_col))
                    fresh_oranges_count -= 1
        
        # Increment time only after all oranges from the current minute have spread rot.
        minutes_elapsed += 1

    # If fresh oranges remain, they were unreachable, so the task is impossible.
    if fresh_oranges_count == 0:
        return minutes_elapsed
    else:
        return -1

Big(O) Analysis

Time Complexity

O(R * C) – The time complexity is determined by the need to visit each cell in the grid. We first iterate through the entire R x C grid to find the initial rotten oranges and count the fresh ones, which takes O(R * C) time. The subsequent Breadth-First Search (BFS) process ensures that each cell is visited and processed at most once as the rot spreads. Therefore, the total operations are proportional to the number of cells in the grid, leading to a time complexity of O(R * C).

Space Complexity

O(M * N) – The primary data structure used for auxiliary space is a queue to manage the layer-by-layer spread of rot, as described by 'put them aside as our starting points'. In the worst-case scenario, where all oranges are initially rotten, this queue would need to store the coordinates of every cell in the grid. If the grid has M rows and N columns, the queue could hold up to M * N elements, leading to a space complexity of O(M * N).

Edge Cases

Case	How to Handle
Grid with no fresh oranges to begin with	The algorithm correctly returns 0 minutes since no time needs to pass.
Grid with no rotten oranges to start, but fresh oranges exist	The rotting process can never start, so the solution must return -1 as it's impossible to rot all oranges.
A fresh orange is isolated and cannot be reached by any rotten orange	After the BFS completes, the solution checks for any remaining fresh oranges and returns -1 if any are found.
The input grid is empty (0 rows or 0 columns)	The initial scan for oranges will find none, leading to a correct return value of 0.
The grid contains only empty cells (all 0s)	No fresh or rotten oranges exist, so the simulation correctly concludes in 0 minutes.
All oranges in the grid are already rotten	No fresh oranges are found in the initial count, so the algorithm returns 0.
A 1x1 grid containing a single fresh or rotten orange	The solution correctly handles this by returning -1 for a single fresh orange and 0 for a single rotten one.
A large grid that requires an efficient solution	A Breadth-First Search (BFS) approach ensures scalability by visiting each cell at most once, performing efficiently within typical constraints.

Grid with no fresh oranges to begin with

How to Handle:

The algorithm correctly returns 0 minutes since no time needs to pass.

Grid with no rotten oranges to start, but fresh oranges exist

How to Handle:

The rotting process can never start, so the solution must return -1 as it's impossible to rot all oranges.

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

How to Handle:

After the BFS completes, the solution checks for any remaining fresh oranges and returns -1 if any are found.

The input grid is empty (0 rows or 0 columns)

How to Handle:

The initial scan for oranges will find none, leading to a correct return value of 0.

The grid contains only empty cells (all 0s)

How to Handle:

No fresh or rotten oranges exist, so the simulation correctly concludes in 0 minutes.

All oranges in the grid are already rotten

How to Handle:

No fresh oranges are found in the initial count, so the algorithm returns 0.

A 1x1 grid containing a single fresh or rotten orange

How to Handle:

The solution correctly handles this by returning -1 for a single fresh orange and 0 for a single rotten one.

A large grid that requires an efficient solution

How to Handle:

A Breadth-First Search (BFS) approach ensures scalability by visiting each cell at most once, performing efficiently within typical constraints.

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 should be returned if the grid initially contains no fresh oranges? Should that be considered 0 minutes?
Could the input grid be empty, or have zero rows or columns? How should I handle such cases?
Is it guaranteed that the grid will only contain the values 0, 1, and 2, or should I validate the input values?
What are the maximum dimensions of the grid, i.e., the upper bounds for 'm' and 'n'?
If the grid contains no rotten oranges to begin with but has fresh oranges, is the correct return value -1, as it's impossible for them to rot?

Brute Force Solution

Approach

Imagine we have a grid of fresh and rotten oranges. The brute force approach is to simulate the rotting process minute by minute, checking at each step what happens to all the fresh oranges.

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

First, take a snapshot of the grid at the very beginning.
Then, for the first minute, look at every single fresh orange in the grid.
For each fresh orange, check if it's next to a rotten one from the previous snapshot. If it is, mark it down to become rotten.
After checking every fresh orange, update the grid all at once with the newly rotten ones. This completes one minute.
Repeat this entire process minute by minute: take a new snapshot, find all fresh oranges that will rot, and then update the grid.
Keep track of how many minutes have passed.
If you get to a point where a minute passes but no new oranges rot, and there are still fresh ones left, it's impossible for them to ever rot. We stop and note this impossibility.
If all the oranges eventually become rotten, the answer is the total number of minutes that have passed.

Code Implementation

def rottingOranges(grid):
    if not grid:
        return -1

    rows = len(grid)
    cols = len(grid[0])
    minutes_passed = 0

    while True:
        oranges_to_rot_this_minute = []
        fresh_oranges_count = 0
        previous_grid_snapshot = [row[:] for row in grid]

        for row_index in range(rows):
            for col_index in range(cols):
                if previous_grid_snapshot[row_index][col_index] == 1:
                    fresh_oranges_count += 1
                    is_adjacent_to_rotten = False
                    # Check all four neighbors to see if any were rotten in the previous state.
                    for delta_row, delta_col in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        neighbor_row = row_index + delta_row
                        neighbor_col = col_index + delta_col

                        if 0 <= neighbor_row < rows and 0 <= neighbor_col < cols and previous_grid_snapshot[neighbor_row][neighbor_col] == 2:
                            is_adjacent_to_rotten = True
                            break
                    
                    if is_adjacent_to_rotten:
                        oranges_to_rot_this_minute.append((row_index, col_index))
        
        # If no oranges rotted this minute, the process stops.
        if not oranges_to_rot_this_minute:
            # If there are still fresh oranges left, it's impossible for them all to rot.
            if fresh_oranges_count > 0:
                return -1
            else:
                return minutes_passed

        # Update the grid with all newly rotten oranges for the next minute's simulation.
        for row_index, col_index in oranges_to_rot_this_minute:
            grid[row_index][col_index] = 2

        minutes_passed += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, take a quick look at the grid to count how many fresh oranges there are. Also, find all the oranges that are already rotten and put them aside as our starting points for the rot.
Imagine time passing in rounds, or minutes. For the first minute, the rot spreads from all the starting rotten oranges to their immediate fresh neighbors.
As these neighbors turn rotten, they become the new sources of rot for the next minute. So, in the second minute, the rot spreads from them.
Continue this process, with the rot spreading outwards in a layer-by-layer fashion each minute. Keep track of how many minutes have passed.
After the rot can't spread any further, check if any fresh oranges are still left. If there are, it means they were unreachable, and the task is impossible.
If all the fresh oranges that we initially counted are now rotten, the answer is the total number of minutes that have passed. If there were no fresh oranges to begin with, the time taken is zero.

Code Implementation

from collections import deque

def oranges_rotting(grid):
    if not grid:
        return 0

    number_of_rows = len(grid)
    number_of_cols = len(grid[0])
    fresh_oranges_count = 0
    rotten_oranges_queue = deque()

    for row_index in range(number_of_rows):
        for col_index in range(number_of_cols):
            if grid[row_index][col_index] == 1:
                fresh_oranges_count += 1
            elif grid[row_index][col_index] == 2:
                rotten_oranges_queue.append((row_index, col_index))

    minutes_elapsed = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    # The queue size represents all oranges that become rotten in the current minute.
    while rotten_oranges_queue and fresh_oranges_count > 0:

        number_rotten_in_current_minute = len(rotten_oranges_queue)
        for _ in range(number_rotten_in_current_minute):
            rotten_row, rotten_col = rotten_oranges_queue.popleft()

            for row_direction, col_direction in directions:
                neighbor_row = rotten_row + row_direction
                neighbor_col = rotten_col + col_direction

                if 0 <= neighbor_row < number_of_rows and 0 <= neighbor_col < number_of_cols and grid[neighbor_row][neighbor_col] == 1:
                    grid[neighbor_row][neighbor_col] = 2
                    rotten_oranges_queue.append((neighbor_row, neighbor_col))
                    fresh_oranges_count -= 1
        
        # Increment time only after all oranges from the current minute have spread rot.
        minutes_elapsed += 1

    # If fresh oranges remain, they were unreachable, so the task is impossible.
    if fresh_oranges_count == 0:
        return minutes_elapsed
    else:
        return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Grid with no fresh oranges to begin with	The algorithm correctly returns 0 minutes since no time needs to pass.
Grid with no rotten oranges to start, but fresh oranges exist	The rotting process can never start, so the solution must return -1 as it's impossible to rot all oranges.
A fresh orange is isolated and cannot be reached by any rotten orange	After the BFS completes, the solution checks for any remaining fresh oranges and returns -1 if any are found.
The input grid is empty (0 rows or 0 columns)	The initial scan for oranges will find none, leading to a correct return value of 0.
The grid contains only empty cells (all 0s)	No fresh or rotten oranges exist, so the simulation correctly concludes in 0 minutes.
All oranges in the grid are already rotten	No fresh oranges are found in the initial count, so the algorithm returns 0.
A 1x1 grid containing a single fresh or rotten orange	The solution correctly handles this by returning -1 for a single fresh orange and 0 for a single rotten one.
A large grid that requires an efficient solution	A Breadth-First Search (BFS) approach ensures scalability by visiting each cell at most once, performing efficiently within typical constraints.

Grid with no fresh oranges to begin with

How to Handle:

The algorithm correctly returns 0 minutes since no time needs to pass.

Grid with no rotten oranges to start, but fresh oranges exist

How to Handle:

The rotting process can never start, so the solution must return -1 as it's impossible to rot all oranges.

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

How to Handle:

After the BFS completes, the solution checks for any remaining fresh oranges and returns -1 if any are found.

The input grid is empty (0 rows or 0 columns)

How to Handle:

The initial scan for oranges will find none, leading to a correct return value of 0.

The grid contains only empty cells (all 0s)

How to Handle:

No fresh or rotten oranges exist, so the simulation correctly concludes in 0 minutes.

All oranges in the grid are already rotten

How to Handle:

No fresh oranges are found in the initial count, so the algorithm returns 0.

A 1x1 grid containing a single fresh or rotten orange

How to Handle:

The solution correctly handles this by returning -1 for a single fresh orange and 0 for a single rotten one.

A large grid that requires an efficient solution

How to Handle:

A Breadth-First Search (BFS) approach ensures scalability by visiting each cell at most once, performing efficiently within typical constraints.

0/0 TikTok questions completed

0/0 completed