| fresh | rotten | result |
|---|---|---|
| O | O | N or -1 |
| X | O | zero |
| X | X | zero |
| O | X | -1 |
- No fresh orange, no matter there is rotten orange or not: 0.
- No rotten orange: impossible.
- Mind the case that fresh orange will be double enqueued:
2, 2
1, 1
0, 0We 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.
Or we can 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
}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)