Rotting Oranges Leetcode Solution

Rotting Oranges Leetcode Problem :

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.

jump game leetcode

Rotting Oranges Leetcode Solution :

Constraints :

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2.

Example 1:

  • Input: grid = [[0,2]]
  • Output: 0
  • Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Intuition :

The intuition of the solution is to perform a BFS on the rotten oranges at the same time and increment the counter.

The neighbors are added only if they are good oranges and their value is set to 2 “rotten”.

Approach :

  • find all oranges which are rotten from the beginning
  • for each of them find fresh neighboring oranges, add them to the queue
  • repeat 2 untill there are no fresh oranges near rotten ones
  • check if fresh oranges are still in the grid

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code :

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription