- What if there are no rotten oranges at the start? What should the answer be?
- How do you ensure you don't rot the same orange multiple times?
- Why is BFS a better fit than DFS for this problem?
- How do you track the time/minutes as the rotting spreads?
- How to model the spread of rot from multiple sources at once?
- How to handle the case where some fresh oranges are unreachable?
- The problem is a classic multi-source BFS on a grid: all rotten oranges are sources, and rot spreads to adjacent fresh oranges each minute.
- You must track the number of fresh oranges and decrement as you rot them. If any fresh orange remains at the end, return
-1. - Marking oranges as rotten (
2) as soon as they are enqueued prevents double-enqueuing and ensures correctness.
We can use BFS to traverse the grid and rot the fresh oranges. There are two ways to enqueue:
- We can enqueue the rotten oranges only. (Recommended)
- We can enqueue the fresh oranges nearby the rotten oranges only. (Deprecated)
rotten -> fresh
1
rotten -> rotten -> fresh
2
rotten -> rotten -> fresh -> __
3
return 3 - 1 = 2Please note that the way how to enqueue affects the way to check the rotten oranges and increment the minutes.
There are some different ways to implement, just mind the way to enqueue, how to keep track of visited node, when to increment the minutes.
In the following implementation, we start from the initial rotten oranges and enqueue the rotten oranges only, then start to rot the fresh oranges nearby (by setting the fresh oranges to rotten oranges and enqueue them).
// Start from 2
1a
^
|
1b <- 2* -> 1c
|
v
1d
1 mins -> 2 mins
2 -> 1a
1b
1c
1dfun orangesRotting(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
// Enqueue the rotten oranges
val queue = ArrayDeque<Pair<Int, Int>>()
var freshCount = 0
for (i in 0 until m) {
for (j in 0 until n) {
if (grid[i][j] == 2) {
// Enqueue the initial rotten oranges
queue.addLast(i to j)
} else if (grid[i][j] == 1) {
freshCount++
}
}
}
// We can early return by checking the following conditions:
// We have to check if there is not fresh orange first
if (freshCount == 0) return 0
// Then check if there is no rotten orange, because it should return 0 when no fresh and rotten oranges
if (queue.isEmpty()) return -1
var minutes = 0
// We start rot if there is any rotten orange
while (queue.isNotEmpty()) {
// Level by level
val size = queue.size
repeat(size) {
val (x, y) = queue.removeFirst()
// Here we don't do anything or check, because we have already checked when enqueuing
// Start to rot the fresh oranges nearby
for (d in directions) {
val newX = x + d[0]
val newY = y + d[1]
if (newX in 0 until m &&
newY in 0 until n &&
grid[newX][newY] == 1) {
freshCount--
// Mark as rotten (as visited) to avoid duplicate rotting
grid[newX][newY] = 2
// Then enqueue the rotten orange
queue.addLast(newX to newY)
}
}
minutes++
}
}
// `minutes - 1` because we increment the minutes after the last level, which is `D`, there is no more level but we still increment the minutes.
// Queue: A -> B -> C -> D
// Minutes 1 2 3 4
// But minutes should be 3, it's the nubmer of edges.
return if (freshCount > 0) -1 else minutes - 1
}- Time Complexity:
O(m * n), wheremis the number of rows andnis the number of columns. - Space Complexity:
O(m * n), wheremis the number of rows andnis the number of columns.
There are different ways to return the minutes:
- Option 1: Initial
minutes = 0and returnminutes - 1: Because we increment the minutes after the last level, which isD, there is no more level but we still increment the minutes. Because in the last while loop, whenfreshCount == 0, we still add last rotten orange to the queue, the minutes will be incremented by this one more iteration, even if there is no fresh orange rotten.
Queue: A --> B --> C --> D
Minutes: |--1--|--2--|--3--|--4--|
^^^^^^ // Redundant iteration, we have to -1
// It should be 3, the number of edges, but we will increment the minutes to 4.- Option 2: Initial
minutes = -1and returnminutes: See below. - Option 3: Initial
minutes = 0and returnminutes, andwhile (freshCount > 0 && queue.isNotEmpty()) { ... }to ensure the last level (rotten + no fresh orange) is NOT processed. - Option 4: Initial
minutes = 0and returnminutes, and checkif (rotten) minutes++to ensure there is acutally any fresh orange has been rotten.
In multi-source BFS, we may have multiple starting points (e.g. all rotten oranges). Rather than simulate "minute 0" for each of them independently, we treat them as if they’re all connected to an imaginary super-source at time = -1. The super-source isn't a real node, it's just a concept to help us track the time. (It's the same idea as 542. 01 Matrix)
Why initializing to -1? Let's look at the normal minute tracking in BFS (level by level):
// Super-source:
S minutes = -1
/ | \ +1
2 2 2 minutes = 0
/ \ | / \ +1
1 1 1 1 1 ...- Minute 0: All original rottne oranges.
- Minute 1: All fresh oranges nearby the original rotten oranges.
- Minute 2: All fresh oranges nearby those....
var minutes = -1
while (queue.isNotEmpty()) {
val size = queue.size
repeat(size) {
val node = queue.removeFirst()
...
}
minutes++
}- The first level doesn't count time as they are already rotten.
- So
minutes++only after the first level is done.
| fresh | rotten | result |
|---|---|---|
| X | O | zero |
| X | X | zero |
| O | O | N or -1 |
| O | X | -1 |
- No fresh orange at all, no matter there is rotten orange or not: return
0. - No rotten orange: return
-1. - Mind the case that fresh orange will be double enqueued:
2, 2
1, 1
0, 0- Fresh oranges are isolated (not reachable by any rotten orange): return
-1. - All oranges are already rotten: return
0. - Grid with only empty cells: return
0.
- Forgetting to mark oranges as rotten when enqueuing, leading to double-processing.
- Off-by-one error in minute counting (should return
minutes - 1). - Not checking for unreachable fresh oranges at the end.
- Not handling the case where there are no fresh oranges at the start.
We can start from the initial rotten oranges and enqueue the fresh oranges nearby to be rotten.
1a*
|
1b* - 2 - 1c*
|
1d*
1 mins -> 2 mins
1a -> ...
1b
1c
1d We don't enqueue the starting rotten oranges, so we don't have to -1 when returning the minutes.
fun orangesRotting(grid: Array<IntArray>): Int {
// Enqueue the fresh oranges nearby the rotten oranges only
val queue = ArrayDeque<Pair<Int, Int>>()
var minutes = 0
var freshCount = 0
for (x in 0 until m) {
for (y in 0 until n) {
if (grid[x][y] == 2) {
for (d in directions) {
val newX = x + d[0]
val newY = y + d[1]
if (!isValidFresh(grid, newX, newY)) continue
queue.addLast(newX to newY)
}
} else if (grid[x][y] == 1) {
freshCount++
}
}
}
while (!queue.isEmpty()) {
val size = queue.size
var rotten = false
// To rot level by leve
for (i in 0 until size) {
val node = queue.removeFirst()
val x = node.first
val y = node.second
if (!isValidFresh(grid, x, y)) continue
grid[x][y] = 2
freshCount--
rotten = true
directions.forEach { d ->
val newX = x + d.first
val newY = y + d.second
queue.addLast(newX to newY)
}
}
// See below explanation
if (rotten) minutes++
}
// We can track freshCount or just iterate the grid to find the fresh oranges
return if (freshCount > 0) -1 else minutes
}
private fun isValidFresh(grid: Array<IntArray>, x: Int, y: Int): Boolean = x in 0 until grid.size && y in 0 until grid[0].size && grid[x][y] == 1The following implementation is a bit confusing and different from our BFS template, hence we stop maintaining the implementation and notes.
Why do we check rotten then increment the minutes above? Because we might enqueue duplicate fresh orange to rot, the time should not be incremented in that round.
// For this case:
2 2
1 1
// We mark the same fresh orange as 1A and 1B
2 , 2
1A, 1B
Queue = [1A, 1B]
1A -> 1BWhen we dequeue 1A, 1B will be enqueued, but it's already enqueued, so we have to track if 1B is enqueued to avoid duplicate rotting. To fix the duplicate enqueue, we can use a set to track the enqueued fresh oranges, and if we can ensure that we enqueue all the valid fresh oranges only, we don't need to check invalid and rotten state in the loop:
- In valid range (not out of bound).
- Not visited or enqueued (not duplicate), enqueued is super set of visited.
- Fresh orange.
The following implemetation is to enqueue only valid fresh oranges, so we don't need to check rotten when incrementing the minutes or skip the out-of-bound or visited fresh oranges, because we have already checked when enqueuing:
// Here we have to track the enqueued fresh oranges to avoid duplicate rotting.
private val enqueued = HashSet<Pair<Int, Int>>()
fun orangesRotting(grid: Array<IntArray>): Int {
// Enqueue the fresh oranges nearby the rotten oranges only
val queue = ArrayDeque<Pair<Int, Int>>()
var minutes = 0
var freshCount = 0
for (m in 0 until grid.size) {
for (n in 0 until grid[m].size) {
if (grid[m][n] == 2) {
directions.forEach { direction ->
val newM = m + direction.first
val newN = n + direction.second
// Check if it's valid fresh orange and not enqueued
if (isValidFresh(grid, newM, newN)) {
queue.addLast(newM to newN)
enqueued.add(newM to newN)
}
}
} else if (grid[m][n] == 1) {
freshCount++
}
}
}
if (queue.isEmpty() && freshCount > 0) return -1
while (!queue.isEmpty()) {
val size = queue.size
// To rot at the same level
repeat(size) {
val node = queue.removeFirst()
val x = node.first
val y = node.second
// We don't check here, because we have already checked when enqueuing
// if (!isValidFresh(grid, x, y)) continue
grid[x][y] = 2
freshCount--
directions.forEach { d ->
val newX = x + d.first
val newY = y + d.second
if (isValidFresh(grid, newX, newY)) {
queue.addLast(newX to newY)
enqueued.add(newX to newY)
}
}
}
// Here we don't need to check if there is any fresh orange rotten because we enqueue if there is any valid fresh orange to rot, if yes then the queue is not empty
minutes++
}
// We can track freshCount or just iterate the grid to find the fresh oranges
return if (freshCount > 0) -1 else minutes
}
private fun isValidFresh(grid: Array<IntArray>, x: Int, y: Int): Boolean = x in 0 until grid.size && y in 0 until grid[0].size && grid[x][y] == 1 && !enqueued.contains(x to y)