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.
Example :
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
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 :
C++
Java
Python
C++
class Solution {
public:
int orangesRotting(vector>& grid) {
int m = grid.size();
int n = grid[0].size();
vector> visited = grid;
//making queue in which we will fill rotten oranges
queue> q;
int countFreshOrange = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] == 2) {
q.push({i, j});
}
if (visited[i][j] == 1) {
countFreshOrange++;
}
}
}
//q.empty() means there is no rotten orange in the grid and countFreshOrange = 0 means we will rotten the freshoranges in 0 mins
if (countFreshOrange == 0)
return 0;
if (q.empty())
return -1;
int minutes = -1;
// we will cover four directions i.e. up, down, left, right
vector> dirs = {{1, 0},{-1, 0},{0, -1},{0, 1}};
while (!q.empty()) {
int size = q.size();
while (size--) {
auto [x, y] = q.front();
q.pop();
for (auto [dx, dy] : dirs) {
int i = x + dx;
int j = y + dy;
if (i >= 0 && i < m && j >= 0 && j < n && visited[i][j] == 1) {
visited[i][j] = 2;
countFreshOrange--;
q.push({i, j});
}
}
}
minutes++;
}
if (countFreshOrange == 0)
return minutes;
return -1;
}
};
Java
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] visited = grid;
Queue q = new LinkedList<>();
int countFreshOrange = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] == 2) {
q.offer(new int[] {i, j});
}
if (visited[i][j] == 1) {
countFreshOrange++;
}
}
}
if (countFreshOrange == 0)
return 0;
if (q.isEmpty())
return -1;
int minutes = -1;
int[][] dirs = {{1, 0},{-1, 0},{0, -1},{0, 1}};
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
int[] cell = q.poll();
int x = cell[0];
int y = cell[1];
for (int[] dir : dirs) {
int i = x + dir[0];
int j = y + dir[1];
if (i >= 0 && i < m && j >= 0 && j < n && visited[i][j] == 1) {
visited[i][j] = 2;
countFreshOrange--;
q.offer(new int[] {i, j});
}
}
}
minutes++;
}
if (countFreshOrange == 0)
return minutes;
return -1;
}
}
Python
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
s = deque()
visited = set()
for i in range(n):
for j in range(m):
if grid[i][j] == 2:
s.append((i, j))
visited.add((i, j))
k = 0
while s:
flag = 0
for h in range(len(s)):
x, y = s.popleft()
for i, j in [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]:
if 0 <= i < n and 0 <= j < m:
if (i, j) not in visited and grid[i][j] == 1:
visited.add((i, j))
s.append((i, j))
grid[i][j] = 2
if flag == 0:
k += 1
flag = 1
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
return -1
return k
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
Login/Signup to comment