What is the time complexity of Rotting Oranges?

The optimal solution has a time complexity of O(m*n).

What data structures are used to solve Rotting Oranges?

This problem uses Array, Breadth-First Search, Matrix. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Rotting Oranges?

Insight 1: Breadth-First Search (BFS) is the ideal algorithm for this problem because we need to find the shortest time for the oranges to rot, and BFS explores the grid level by level. Insight 2: The key to efficiently tracking time is to store the time elapsed along with the coordinates of the rotten oranges in the queue.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Rotting Oranges - LeetCode 994 Solution

Q: What is the space complexity of Rotting Oranges?

The space complexity is O(m*n).

Q: Which companies ask LeetCode 994. Rotting Oranges in interviews?

This problem is frequently asked at Anduril, ByteDance, Citadel, DP world, Deutsche Bank and 20 more companies.

Rotting Oranges - Complete Solution Guide

Rotting Oranges is LeetCode problem 994, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem asks us to find the minimum time (in minutes) it takes for all fresh oranges in a grid to rot. The grid contains empty cells (0), fresh oranges (1), and rotten oranges (2). Every minute, a fresh orange that is adjacent (4-directionally: up, down, left, right) to a rotten orange becomes rotten itself. If it's impossible for all fresh oranges to rot, we should return -1. If there are no fresh oranges initially, the answer is 0.

Solution Approach

The solution uses Breadth-First Search (BFS) to simulate the rotting process. It starts by identifying all the rotten oranges and adding their coordinates along with an initial time of 0 to a queue. Then, the algorithm processes the queue level by level. For each rotten orange, it checks its four adjacent cells. If a fresh orange is found, it's marked as rotten, the number of fresh oranges is decremented, and the new rotten orange is added to the queue with an incremented time. The algorithm continues until the queue is empty. Finally, it checks if any fresh oranges remain. If so, it returns -1; otherwise, it returns the maximum time elapsed during the rotting process.

Step-by-Step Algorithm

Step 1: Initialize variables: `rows`, `cols` (dimensions of the grid), `q` (a queue to store rotten oranges and their rotting time), `fresh_oranges` (count of fresh oranges).
Step 2: Iterate through the grid and count the number of fresh oranges. Add the coordinates and initial time (0) of all rotten oranges to the queue `q`.
Step 3: If `fresh_oranges` is 0, return 0 (no oranges to rot).
Step 4: Initialize `minutes_elapsed` to 0.
Step 5: Perform BFS: While the queue `q` is not empty, dequeue an element (row, col, minutes). Update `minutes_elapsed` to be the maximum of its current value and the `minutes` value dequeued.
Step 6: For each of the four possible directions (up, down, left, right) from the current cell (row, col), check if the adjacent cell is within the grid boundaries and contains a fresh orange.
Step 7: If an adjacent fresh orange is found, mark it as rotten (set its value to 2), decrement `fresh_oranges`, and enqueue the coordinates of the newly rotten orange and the incremented time (minutes + 1).
Step 8: After the BFS traversal, if `fresh_oranges` is still greater than 0, it means some fresh oranges could not be rotted. Return -1.
Step 9: Otherwise, return `minutes_elapsed` (the maximum time it took for all possible oranges to rot).

Key Insights

Insight 1: Breadth-First Search (BFS) is the ideal algorithm for this problem because we need to find the shortest time for the oranges to rot, and BFS explores the grid level by level.
Insight 2: The key to efficiently tracking time is to store the time elapsed along with the coordinates of the rotten oranges in the queue.
Insight 3: We need to keep track of the number of fresh oranges at the start and decrement it as they rot. This helps us determine if all fresh oranges have rotted at the end. Handling edge cases where no fresh oranges are present initially is important.

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(m*n)

Topics

This problem involves: Array, Breadth-First Search, Matrix.

Companies

Asked at: Anduril, ByteDance, Citadel, DP world, Deutsche Bank, Docusign, Expedia, Flipkart, Informatica, Intuit, Lyft, Myntra, Nutanix, PhonePe, Roblox, Salesforce, Samsung, ServiceNow, VMware, Wix, X, Zepto, ZipRecruiter, Zoox, eBay.

Rotting Oranges | LeetCode 994

Medium

Array Breadth-First Search Matrix

Time: O(m*n)Space: O(m*n)

Solution Code

Available in:

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        int fresh_oranges = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    fresh_oranges += 1;
                } else if (grid[r][c] == 2) {
                    q.add(new int[]{r, c, 0});
                }
            }
        }

        if (fresh_oranges == 0) {
            return 0;
        }

        int minutes_elapsed = 0;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int r = current[0];
            int c = current[1];
            int minutes = current[2];
            minutes_elapsed = Math.max(minutes_elapsed, minutes);

            for (int[] dir : directions) {
                int dr = dir[0];
                int dc = dir[1];
                int nr = r + dr;
                int nc = c + dc;

                if (0 <= nr && nr < rows && 0 <= nc && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh_oranges -= 1;
                    q.add(new int[]{nr, nc, minutes + 1});
                }
            }
        }

        if (fresh_oranges > 0) {
            return -1;
        } else {
            return minutes_elapsed;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 994: Rotting Oranges - Detailed explanation and solution approaches.

Topics

Array Breadth-First Search Matrix

Companies

AndurilByteDanceCitadelDP worldDeutsche BankDocusignExpediaFlipkart

Stats

Difficulty:Medium

Languages:4

Companies:25

Problem #:994

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Initialize variables: `rows`, `cols` (dimensions of the grid), `q` (a queue to store rotten oranges and their rotting time), `fresh_oranges` (count of fresh oranges).
2
Step 2: Iterate through the grid and count the number of fresh oranges. Add the coordinates and initial time (0) of all rotten oranges to the queue `q`.
3
Step 3: If `fresh_oranges` is 0, return 0 (no oranges to rot).
4
Step 4: Initialize `minutes_elapsed` to 0.
5
Step 5: Perform BFS: While the queue `q` is not empty, dequeue an element (row, col, minutes). Update `minutes_elapsed` to be the maximum of its current value and the `minutes` value dequeued.
6
Step 6: For each of the four possible directions (up, down, left, right) from the current cell (row, col), check if the adjacent cell is within the grid boundaries and contains a fresh orange.
7
Step 7: If an adjacent fresh orange is found, mark it as rotten (set its value to 2), decrement `fresh_oranges`, and enqueue the coordinates of the newly rotten orange and the incremented time (minutes + 1).
8
Step 8: After the BFS traversal, if `fresh_oranges` is still greater than 0, it means some fresh oranges could not be rotted. Return -1.
9
Step 9: Otherwise, return `minutes_elapsed` (the maximum time it took for all possible oranges to rot).

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(m*n)

📝

Why?

The time complexity is O(m*n) because each cell is visited at most a constant number of times. The space complexity is O(m*n) due to the queue potentially holding all the cells in the grid in the worst case.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Depth-First Search (DFS)

While DFS can also explore the grid, it's not ideal for finding the *minimum* time. DFS could potentially take longer paths, leading to incorrect time calculation.

Time: O(m*n)Space: O(m*n) in the worst case due to recursion stack

Trade-offs: BFS is preferred because it guarantees finding the shortest path (minimum time) to rot the oranges, while DFS doesn't.

Dynamic Programming

Dynamic programming is not a suitable approach for this problem because the state transition depends on neighboring cells simultaneously, making it difficult to define a recurrence relation. It's more complex to implement correctly.

Time: Potentially O(m*n) but with high constant factorsSpace: Potentially O(m*n)

Trade-offs: BFS is more intuitive and easier to implement than dynamic programming for this problem.

✨

Key Insights

1Insight 1: Breadth-First Search (BFS) is the ideal algorithm for this problem because we need to find the shortest time for the oranges to rot, and BFS explores the grid level by level.
2Insight 2: The key to efficiently tracking time is to store the time elapsed along with the coordinates of the rotten oranges in the queue.
3Insight 3: We need to keep track of the number of fresh oranges at the start and decrement it as they rot. This helps us determine if all fresh oranges have rotted at the end. Handling edge cases where no fresh oranges are present initially is important.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: No fresh oranges initially. The code correctly handles this by checking `if fresh_oranges == 0:` and returning 0 in this case.
Edge case 2: Some fresh oranges are completely isolated and cannot be reached by rotten oranges. The code identifies this by checking `if fresh_oranges > 0:` after the BFS traversal and returns -1.
Edge case 3: The grid contains only empty cells and rotten oranges. The logic still functions correctly, as the `fresh_oranges` count will remain 0, and the function returns 0.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the edge case where some fresh oranges are unreachable and cannot rot. This leads to an incorrect result (not returning -1).

✗Common mistake 2: Not using BFS, which guarantees the minimum time. Using DFS or other search algorithms might lead to incorrect results.

✗Common mistake 3: Incorrectly updating the `minutes_elapsed`. The maximum time elapsed should be updated during the BFS traversal when dequeuing an element, not when enqueuing.

✗Common mistake 4: Not correctly updating the grid to mark the fresh oranges as rotten.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Spread of a disease. The grid can represent a city, where each cell represents a person. Rotten oranges are infected people, and fresh oranges are susceptible people. The algorithm can predict how long it takes for a disease to spread through the city.

🏦Real-world scenario 2: Signal propagation in a network. The grid can represent a network, where each cell is a node. Rotten oranges are nodes with a signal, and fresh oranges are nodes without a signal. The algorithm can calculate the time it takes for a signal to propagate throughout the network.

🎮Real-world scenario 3: Forest fire spread. The grid can represent a forest, where each cell is a tree. Rotten oranges represent trees that are on fire, and fresh oranges are trees that are not on fire. The algorithm can predict the time it takes for a fire to spread through the forest, given wind direction and tree density.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 3, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Rotting Oranges"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether breadth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?