Rotting Oranges LeetCode Solution
Rotting Oranges LeetCode Solution : Hello geeks😁, in this article we are going to discuss the Rotting Oranges problem on LeetCode.
We would be discussing:
- Problem statement
- Different approaches
- Time complexity
- Space complexity
Understanding the Problem Statement
Given Statement: You are given an m x n grid where each cell can have one of three values:
0representing an empty cell,1representing a fresh orange, or2representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Example 2:
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.
Example 3:
Input: grid = [[0,2]]
Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]is0,1, or2.
Explanation: In this example, the process goes as follows:
- Minute 0: Initial state.
- Minute 1: (0,0) rots adjacent (1,0) and (0,1) oranges.
- Minute 2: (1,0) rots (2,0) and (1,1) oranges. (0,1) rots (1,1) and (0,2) oranges.
- Minute 3: (2,0) rots (2,1) and (1,0) oranges. (1,1) rots (2,1) and (1,2) oranges.
- Minute 4: (2,1) rots (2,2) orange. (1,2) rots (2,2) orange.
All oranges are now rotten.
How to Approach Rotting Oranges LeetCode Solution?
The above given problem can be solved using multiple approaches.
Approach 1: Brute Force
Explanation:
Imagine you have a grid of oranges, some of which are rotten and some are fresh. You want to make all the fresh oranges rotten. But there’s a rule: a rotten orange can only make its adjacent (up, down, left, and right) fresh oranges rotten in one minute. Our task is to find out the minimum time it will take to make all the fresh oranges rotten.
Algorithm:
- Start with an initial time of 0 minutes.
- Create a queue to hold the positions of the rotten oranges.
- Put all the initially rotten oranges in the queue.
- While there are still oranges in the queue:Increment the time by 1, simulating the passage of time.
- Process all the oranges in the current minute:Check the neighboring oranges of the current rotten orange.
- If a neighboring orange is fresh, mark it as rotten and put it in the queue.
- After processing all the oranges in the current minute, check if there are still fresh oranges left. If yes, it’s not possible to make all oranges rotten, so return -1.
- If all fresh oranges have become rotten, return the time taken minus 1.
Rotting Oranges LeetCode Solution In C, C++, Java, Python And Javascript:
C
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// Define a struct for a coordinate
struct Coordinate {
int x;
int y;
};
// Implement the Brute Force approach
int orangesRotting(int** grid, int gridSize, int* gridColSize) {
// Create a queue to hold the positions of the rotten oranges
struct Coordinate* queue = malloc(sizeof(struct Coordinate) * (gridSize * (*gridColSize)));
int front = 0, rear = 0; // Queue pointers
// Initialize the queue with the positions of the initially rotten oranges
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < *gridColSize; j++) {
if (grid[i][j] == 2) {
struct Coordinate coord = {i, j};
queue[rear++] = coord;
}
}
}
// Define directions for adjacent cells (up, down, left, and right)
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// Initialize time and fresh orange count
int minutes = 0, freshCount = 0;
// BFS to make oranges rotten
while (front < rear) {
int currentSize = rear - front;
bool hasFresh = false;
for (int i = 0; i < currentSize; i++) {
struct Coordinate current = queue[front++];
for (int j = 0; j < 4; j++) {
int newX = current.x + directions[j][0];
int newY = current.y + directions[j][1];
if (newX >= 0 && newX < gridSize && newY >= 0 && newY < *gridColSize && grid[newX][newY] == 1) {
grid[newX][newY] = 2;
struct Coordinate newCoord = {newX, newY};
queue[rear++] = newCoord;
freshCount--;
hasFresh = true;
}
}
}
if (hasFresh) {
minutes++;
}
}
// If there are still fresh oranges, return -1; otherwise, return minutes
return (freshCount == 0) ? minutes : -1;
}C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Implement the Brute Force approach
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
queue<pair<int, int>> rotten;
int freshCount = 0;
// Enqueue the coordinates of all the rotten oranges and count the number of fresh oranges
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
rotten.push({i, j});
} else if (grid[i][j] == 1) {
freshCount++;
}
}
}
int minutes = 0;
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!rotten.empty() && freshCount > 0) {
int size = rotten.size();
for (int i = 0; i < size; i++) {
int x = rotten.front().first;
int y = rotten.front().second;
rotten.pop();
for (auto dir : directions) {
int newX = x + dir.first;
int newY = y + dir.second;
if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1) {
grid[newX][newY] = 2;
rotten.push({newX, newY});
freshCount--;
}
}
}
minutes++;
}
return (freshCount == 0) ? minutes : -1;
}
};Python
# Implement the Brute Force approach
def orangesRotting(grid):
m, n = len(grid), len(grid[0])
rotten = []
fresh_count = 0
# Enqueue the coordinates of all the rotten oranges and count the number of fresh oranges
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
rotten.append((i, j))
elif grid[i][j] == 1:
fresh_count += 1
minutes = 0
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while rotten and fresh_count > 0:
size = len(rotten)
for _ in range(size):
x, y = rotten.pop(0)
for dir_x, dir_y in directions:
new_x, new_y = x + dir_x, y + dir_y
if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 1:
grid[new_x][new_y] = 2
rotten.append((new_x, new_y))
fresh_count -= 1
minutes += 1
return minutes if fresh_count == 0 else -1
# Read input, create grid, and call orangesRotting function
# Note: You need to handle input reading and grid creation
Javascript
// Implement the Brute Force approach
function orangesRotting(grid) {
const m = grid.length;
const n = grid[0].length;
const rotten = [];
let freshCount = 0;
// Enqueue the coordinates of all the rotten oranges and count the number of fresh oranges
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 2) {
rotten.push([i, j]);
} else if (grid[i][j] === 1) {
freshCount++;
}
}
}
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let minutes = 0;
while (rotten.length > 0 && freshCount > 0) {
const size = rotten.length;
for (let i = 0; i < size; i++) {
const [x, y] = rotten.shift();
for (const [dirX, dirY] of directions) {
const newX = x + dirX;
const newY = y + dirY;
if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] === 1) {
grid[newX][newY] = 2;
rotten.push([newX, newY]);
freshCount--;
}
}
}
minutes++;
}
return freshCount === 0 ? minutes : -1;
}
// Read input, create grid, and call orangesRotting function
Java
import java.util.*;
// Implement the Brute Force approach
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
Queue<int[]> rotten = new LinkedList<>();
int freshCount = 0;
// Enqueue the coordinates of all the rotten oranges and count the number of fresh oranges
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
rotten.offer(new int[] {i, j});
} else if (grid[i][j] == 1) {
freshCount++;
}
}
}
int minutes = 0;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!rotten.isEmpty() && freshCount > 0) {
int size = rotten.size();
for (int i = 0; i < size; i++) {
int[] coords = rotten.poll();
int x = coords[0];
int y = coords[1];
for (int[] dir : directions) {
int newX = x + dir[0];
int newY = y + dir[1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1) {
grid[newX][newY] = 2;
rotten.offer(new int[] {newX, newY});
freshCount--;
}
}
}
minutes++;
}
return (freshCount == 0) ? minutes : -1;
}
}
public class Main {
public static void main(String[] args) {
// Read input, create grid, and call Solution's orangesRotting function
// Note: You need to handle input reading and grid creation
}
}
Time Complexity: O(m * n)
Space Complexity: O(m * n)
Approach 2: Using BFS with Multiple Sources
Explanation:
Think of the oranges as if they are in a queue, and each minute, the oranges at the front of the queue make their neighbors rotten. We repeat this process until there are no more fresh oranges left. Our goal is to find the minimum time needed for all oranges to become rotten.
Algorithm:
- Start with an initial time of 0 minutes.
- Create a queue to hold the positions of the rotten oranges.
- Put all the initially rotten oranges in the queue.
- While there are still oranges in the queue:Increment the time by 1, simulating the passage of time.
- Process all the oranges in the current minute:Check the neighboring oranges of the current rotten orange.
- If a neighboring orange is fresh, mark it as rotten and put it in the queue.
- After processing all the oranges in the current minute, check if there are still fresh oranges left. If yes, it’s not possible to make all oranges rotten, so return -1.
- If all fresh oranges have become rotten, return the time taken minus 1.
Rotting Oranges LeetCode Solution In C, C++, Java, Python And Javascript:
C
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// Define a struct for a coordinate
struct Coordinate {
int x;
int y;
};
// Implement the BFS with Multiple Sources approach
int orangesRotting(int** grid, int gridSize, int* gridColSize) {
// Create a queue to hold the positions of the rotten oranges
struct Coordinate* queue = malloc(sizeof(struct Coordinate) * (gridSize * (*gridColSize)));
int front = 0, rear = 0; // Queue pointers
// Initialize the queue with the positions of the initially rotten oranges
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < *gridColSize; j++) {
if (grid[i][j] == 2) {
struct Coordinate coord = {i, j};
queue[rear++] = coord;
}
}
}
// Define directions for adjacent cells (up, down, left, and right)
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// Initialize time and fresh orange count
int minutes = 0, freshCount = 0;
// BFS to make oranges rotten
while (front < rear) {
int currentSize = rear - front;
bool hasFresh = false;
for (int i = 0; i < currentSize; i++) {
struct Coordinate current = queue[front++];
for (int j = 0; j < 4; j++) {
int newX = current.x + directions[j][0];
int newY = current.y + directions[j][1];
if (newX >= 0 && newX < gridSize && newY >= 0 && newY < *gridColSize && grid[newX][newY] == 1) {
grid[newX][newY] = 2;
struct Coordinate newCoord = {newX, newY};
queue[rear++] = newCoord;
freshCount--;
hasFresh = true;
}
}
}
if (hasFresh) {
minutes++;
}
}
// If there are still fresh oranges, return -1; otherwise, return minutes
return (freshCount == 0) ? minutes : -1;
}
int main() {
// Read input, create grid, and call orangesRotting function
// Note: You need to handle input reading and grid creation
return 0;
}
C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Implement the BFS with Multiple Sources approach
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
queue<pair<int, int>> rotten;
int freshCount = 0;
// Enqueue the coordinates of all the rotten oranges and count the number of fresh oranges
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
rotten.push({i, j});
} else if (grid[i][j] == 1) {
freshCount++;
}
}
}
int minutes = 0;
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!rotten.empty() && freshCount > 0) {
int size = rotten.size();
for (int i = 0; i < size; i++) {
int x = rotten.front().first;
int y = rotten.front().second;
rotten.pop();
for (auto dir : directions) {
int newX = x + dir.first;
int newY = y + dir.second;
if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1) {
grid[newX][newY] = 2;
rotten.push({newX, newY});
freshCount--;
}
}
}
minutes++;
}
return (freshCount == 0) ? minutes : -1;
}
};
int main() {
// Read input, create grid, and call Solution's orangesRotting function
// Note: You need to handle input reading and grid creation
return 0;
}
Java
import java.util.*;
// Implement the BFS with Multiple Sources approach
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
Queue<int[]> rotten = new LinkedList<>();
int freshCount = 0;
// Enqueue the coordinates of all the rotten oranges and count the number of fresh oranges
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
rotten.offer(new int[] {i, j});
} else if (grid[i][j] == 1) {
freshCount++;
}
}
}
int minutes = 0;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!rotten.isEmpty() && freshCount > 0) {
int size = rotten.size();
for (int i = 0; i < size; i++) {
int[] coords = rotten.poll();
int x = coords[0];
int y = coords[1];
for (int[] dir : directions) {
int newX = x + dir[0];
int newY = y + dir[1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1) {
grid[newX][newY] = 2;
rotten.offer(new int[] {newX, newY});
freshCount--;
}
}
}
minutes++;
}
return (freshCount == 0) ? minutes : -1;
}
}
public class Main {
public static void main(String[] args) {
// Read input, create grid, and call Solution's orangesRotting function
// Note: You need to handle input reading and grid creation
}
}
Javascript
// Implement the BFS with Multiple Sources approach
function orangesRotting(grid) {
const m = grid.length;
const n = grid[0].length;
const rotten = [];
let freshCount = 0;
// Enqueue the coordinates of all the rotten oranges and count the number of fresh oranges
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 2) {
rotten.push([i, j]);
} else if (grid[i][j] === 1) {
freshCount++;
}
}
}
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let minutes = 0;
while (rotten.length > 0 && freshCount > 0) {
const size = rotten.length;
for (let i = 0; i < size; i++) {
const [x, y] = rotten.shift();
for (const [dirX, dirY] of directions) {
const newX = x + dirX;
const newY = y + dirY;
if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] === 1) {
grid[newX][newY] = 2;
rotten.push([newX, newY]);
freshCount--;
}
}
}
minutes++;
}
return freshCount === 0 ? minutes : -1;
}
// Read input, create grid, and call orangesRotting function
Python
# Implement the BFS with Multiple Sources approach
def orangesRotting(grid):
m, n = len(grid), len(grid[0])
rotten = []
fresh_count = 0
# Enqueue the coordinates of all the rotten oranges and count the number of fresh oranges
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
rotten.append((i, j))
elif grid[i][j] == 1:
fresh_count += 1
minutes = 0
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while rotten and fresh_count > 0:
size = len(rotten)
for _ in range(size):
x, y = rotten.pop(0)
for dir_x, dir_y in directions:
new_x, new_y = x + dir_x, y + dir_y
if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 1:
grid[new_x][new_y] = 2
rotten.append((new_x, new_y))
fresh_count -= 1
minutes += 1
return minutes if fresh_count == 0 else -1
# Read input, create grid, and call orangesRotting function
# Note: You need to handle input reading and grid creationTime Complexity: O(m * n)
Space Complexity: O(m * n)
An orange becomes rotten if it is adjacent to a rotten orange either vertically or horizontally (up, down, left, or right). Diagonal adjacent oranges do not affect the rotting process.
Can there be more than one rotten orange initially in the grid?
We start counting minutes from 0, so the actual time it takes for all fresh oranges to become rotten is the total minutes minus 1.
Conclusion
In this tutorial, we delved into the Rotting Oranges problem on LeetCode. We learned how to approach this problem using a breadth-first search (BFS) algorithm. By simulating the rotting process and tracking the minutes using BFS, we were able to determine the minimum time required for all fresh oranges to become rotten.
The BFS approach showcased here not only solved the problem but also demonstrated the practical application of graph traversal in solving real-world scenarios. This problem serves as a reminder of the importance of considering adjacent elements in various computational tasks. Feel free to explore different approaches to the problem and experiment with optimizations for even larger grids. Happy coding!
