DSA Visualizations | Hello Interview

Rotting Oranges

DESCRIPTION (credit Leetcode.com)

You are given an m x n grid representing a box of oranges. Each cell in the grid can have one of three values:

"E" representing an empty cell
"F" representing a fresh orange
"R" representing a rotten orange

Every minute, any fresh orange that is adjacent (4-directionally: up, down, left, right) to a rotten orange becomes rotten.

Write a function that takes this grid as input and returns the minimum number of minutes that must elapse until no cell has a fresh orange. If it is impossible to rot every fresh orange, return -1.

EXAMPLES

Example 1:

Input:


grid = [
["R", "F"],
["F", "F"],
]

Output: 2

Explanation:

After Minute 1: The rotting orange at grid[0][0] rots the fresh oranges at grid[0][1] and grid[1][0]. After Minute 2: The rotting orange at grid[1][0] (or grid[0][1]) rots the fresh orange at grid[1][1].

So after 2 minutes, all the fresh oranges are rotten.

Example 2:

Input:


grid = [
["R", "E"],
["E", "F"],
]

Output: -1

Explanation:

The two adjacent oranges to the rotten orange at grid[0][0] are empty, so after 1 minute, there are no fresh oranges to rot. So it is impossible to rot every fresh orange.

Example 3:

Input:


grid = [
["R", "F", "F", "F"],
["F", "F", "F", "R"],
["E", "E", "F", "F"],
]

Output: 2

Run your code to see results here

Explanation

We can model this problem as a graph where each cell is a node and the edges are the connections between adjacent cells.

The key to this problem is recognizing that we can simulate the rotting process using a breadth-first search (BFS) traversal of the graph (since any rotting orange will cause its neighbors to rot in the next minute).

Step 1: Initialize BFS Queue and Count Fresh Oranges

We can start by iterating over each cell in the grid and adding the position of all the rotten oranges to a queue. As we iterate, we can also count the number of fresh oranges in the grid - which will help us determine if there are any fresh oranges left after the BFS traversal.

Step 2: BFS Traversal

Next, we find all the oranges that will rot in the next minute. For each rotten orange in the BFS queue, we check if any of its neighbors are fresh oranges. If so, we turn the fresh orange into a rotten orange and add it to the queue to prepare for the next minute (shown in orange in the diagrams below). We also decrement the count of fresh oranges.

When we have finished processing all the rotten oranges in the queue, we increment the minute counter and repeat the process until there are no more fresh oranges left or the queue is empty.

The state of the orange box after each minute. The oranges that became rotten during this minute are colored in orange, while the "visited" oranges are dimmed.

If fresh_oranges is 0, then all oranges have become rotten, and we return the number of minutes it took to make all the oranges rotten. Otherwise, we return -1, as not all oranges can become rotten.

Solution

from collections import deque

class Solution:
    def rotting_oranges(self, grid):
        if not grid:
            return -1

        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh_oranges = 0

        # Step 1: Initialize BFS Queue and Count Fresh Oranges
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "R":
                    queue.append((r, c))
                elif grid[r][c] == "F":
                    fresh_oranges += 1


        # Step 2: Perform BFS to Simulate Rotting Process
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        minutes = 0
        while queue and fresh_oranges > 0:
            minutes += 1

            # process all the rotten oranges at the current minute
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "F":
                        grid[nx][ny] = "R"
                        fresh_oranges -= 1
                        queue.append((nx, ny))

        return minutes if fresh_oranges == 0 else -1

Complexity Analysis

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. The worst-case scenario is that all the cells in the grid are fresh oranges, and we have to visit all of them to rot them.

Space Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. The space complexity is dominated by the queue used for the BFS traversal, which can contain at most m * n elements in the worst case.

Next: 01-Matrix

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Minimum Knight Moves

01-Matrix

Rotting Oranges

DESCRIPTION (credit Leetcode.com)

You are given an m x n grid representing a box of oranges. Each cell in the grid can have one of three values:

"E" representing an empty cell
"F" representing a fresh orange
"R" representing a rotten orange

Every minute, any fresh orange that is adjacent (4-directionally: up, down, left, right) to a rotten orange becomes rotten.

Write a function that takes this grid as input and returns the minimum number of minutes that must elapse until no cell has a fresh orange. If it is impossible to rot every fresh orange, return -1.

EXAMPLES

Example 1:

Input:


grid = [
["R", "F"],
["F", "F"],
]

Output: 2

Explanation:

So after 2 minutes, all the fresh oranges are rotten.

Example 2:

Input:


grid = [
["R", "E"],
["E", "F"],
]

Output: -1

Explanation:

The two adjacent oranges to the rotten orange at grid[0][0] are empty, so after 1 minute, there are no fresh oranges to rot. So it is impossible to rot every fresh orange.

Example 3:

Input:


grid = [
["R", "F", "F", "F"],
["F", "F", "F", "R"],
["E", "E", "F", "F"],
]

Output: 2

Run your code to see results here

Explanation

We can model this problem as a graph where each cell is a node and the edges are the connections between adjacent cells.

Step 1: Initialize BFS Queue and Count Fresh Oranges

Step 2: BFS Traversal

When we have finished processing all the rotten oranges in the queue, we increment the minute counter and repeat the process until there are no more fresh oranges left or the queue is empty.

The state of the orange box after each minute. The oranges that became rotten during this minute are colored in orange, while the "visited" oranges are dimmed.

If fresh_oranges is 0, then all oranges have become rotten, and we return the number of minutes it took to make all the oranges rotten. Otherwise, we return -1, as not all oranges can become rotten.

Solution

from collections import deque

class Solution:
    def rotting_oranges(self, grid):
        if not grid:
            return -1

        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh_oranges = 0

        # Step 1: Initialize BFS Queue and Count Fresh Oranges
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "R":
                    queue.append((r, c))
                elif grid[r][c] == "F":
                    fresh_oranges += 1


        # Step 2: Perform BFS to Simulate Rotting Process
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        minutes = 0
        while queue and fresh_oranges > 0:
            minutes += 1

            # process all the rotten oranges at the current minute
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "F":
                        grid[nx][ny] = "R"
                        fresh_oranges -= 1
                        queue.append((nx, ny))

        return minutes if fresh_oranges == 0 else -1

Complexity Analysis

Next: 01-Matrix

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA Guided Practice Hello Interview Premium

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103