🍊

Notes on Rotten Oranges Problem

Jul 28, 2024

Rotten Oranges Problem

Problem Statement

  • Given a basket represented by a 2D matrix containing:
    • Rotten Oranges (denoted by 2)
    • Fresh Oranges (denoted by 1)
    • Empty Space (denoted by 0)
  • Determine how many time frames it takes for all fresh oranges to rot, or return -1 if impossible.

Key Points

  • A rotten orange can rot adjacent fresh oranges in one time frame.
  • Only consider adjacency in four directions: up, down, left, right (not diagonal).
  • If there's an empty space (0) separating rotten and fresh oranges, some fresh oranges may remain un-rotten.

Example Explanation

Case 1: All Oranges Can Rot

  • Initial state example: 2 1 0 2 1 1 1 1 0 1 0 1 1 1 2
  • Step-wise transformation:
    1. Time frame 1: Rot adjacent fresh oranges to both 2s.
    2. Time frame 2: Remaining fresh oranges adjacent to rotten.
  • Total time frames to rot all oranges = 2.

Case 2: Not All Oranges Can Rot

  • Modifying the basket by introducing empty spaces can lead to some fresh oranges remaining untouched.
  • Example placement: 2 1 0 2 1 0 1 1 0 1
  • Result: Impossible to rot all oranges due to isolation from rotten ones.
  • Therefore, return -1.

BFS Approach

  • A Breadth-First Search (BFS) algorithm is suitable to solve this problem as it processes each layer of rotten oranges simultaneously.
  • Maintain a queue to store coordinates of rotten oranges and their corresponding time frames.
  • Structure of BFS node:
    • Time frame (elapsed time)
    • x and y coordinates of the oranges

Steps to Solve

  1. Scan the matrix and store locations of all rotten oranges in a queue, initialized at time frame 0.

  2. Process each rotten orange iteratively:

    • Check all four directions for fresh oranges (1).
    • Convert fresh oranges to rotten (2) and add them to the queue with incremented time frame.

  3. Continue until the queue is empty.

  4. If there are leftover fresh oranges (1) after processing, return -1.

Time Complexity

  • The complexity is typically O(n), where n is the number of cells in the grid. A single point could be traversed multiple times from its adjacent cells.

Conclusion

  • Understanding the rotting propagation is key to figuring out the time frames involved.
  • This problem is commonly asked in programming interviews, so mastering the BFS technique is beneficial.
  • Reach out for clarifications or additional examples if needed.

Note: Like, share, and subscribe for more programming content!

Full transcript