We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Rotting Oranges

Difficulty: Medium

Problem Description

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.

Key Insights

  • Fresh oranges (1) can only become rotten if they are adjacent to a rotten orange (2).
  • The process of rotting spreads like a wave, affecting all adjacent fresh oranges simultaneously each minute.
  • A breadth-first search (BFS) approach is suitable for this problem as it explores all neighbors at the present depth before moving on to nodes at the next depth level.
  • We need to keep track of how many fresh oranges are initially present and how many minutes it takes for all of them to rot.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. Each cell is processed at most once. Space Complexity: O(m * n) in the worst case for the queue used in BFS.

Solution

The solution employs a breadth-first search (BFS) approach. We will:

  1. Initialize a queue to store the positions of all rotten oranges.
  2. Count the total number of fresh oranges.
  3. Perform BFS: for each rotten orange, check its 4-directionally adjacent cells. If an adjacent cell contains a fresh orange, mark it as rotten and add it to the queue.
  4. Keep track of the minutes elapsed.
  5. If all fresh oranges are rotten by the end of the BFS, return the minutes. If any fresh oranges remain, return -1.

Code Solutions

from collections import deque

def orangesRotting(grid):
    m, n = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0

    # Initialize the queue with all rotten oranges and count fresh oranges
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                queue.append((i, j))
            elif grid[i][j] == 1:
                fresh_count += 1

    # Directions for 4-directional adjacency
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    minutes = 0

    # BFS to rot the oranges
    while queue:
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                    grid[nx][ny] = 2  # Rot the fresh orange
                    fresh_count -= 1
                    queue.append((nx, ny))
        minutes += 1

    return minutes - 1 if fresh_count == 0 else -1
← Back to All Questions