Skip to content

934.shortest-bridge.md

Latest commit

 

History

History
339 lines (293 loc) · 12 KB

934.shortest-bridge.md

File metadata and controls

339 lines (293 loc) · 12 KB

934. Shortest Bridge

Breakdowns

  1. How to find the two islands?

DFS or BFS to find the connected components.

  1. How to find the shortest path between the two islands?

Enqueue each nodes in one island and start BFS to find the shortest path to another island.

Traversal

We can traverse to find the first island (by DFS or BFS), then BFS to find the shortest path to the second island.

  • To find the first island (by DFS or BFS), we only traverse the 1 cells, and skip the 0 and visited cells.
  • To find the shortest path between the two islands, we start from the first island, and traverse the 1 and 0 cells to find the second island. And for 1 cells, it could be either the first island or the second island, we need to distinguish them.

Pitfalls

There are some key points to consider in the implementation:

  • We need to break the loop when we find the first cell of island. Otherwise, we will visit all islands, not just the first one. The following code will add cells on each 1 to the first island, including the second island.
val islands = Array(2) { HashSet<Pair<Int, Int>>() }
for (x in 0 until grid.size) {
    for (y in 0 until grid[0].size) {
        for (i in 0 until islands.size) {
            if (grid[x][y] == 1 && islands[i].contains(x to y).not()) {
                dfs(grid, x, y, islands[i])
            }
            // OR this's also wrong
            if (grid[x][y] == 1 && islands[0].contains(x to y).not() && islands[0].contains(x to y).not())
        }
    }
}
  • We enqueue all cells in 1st island to the queue, and then start BFS to find the shortest path to the second island. We need to distinguish the first island and the second island, so we use different visited set during the BFS. (Or we can change the value of the grid to mark the visited nodes.) We lost the way to distinguish the two islands if we use the same visited set:
// We omit some code, just focus on the key part!!
// There are all cells in the first island in queue and visited set.
fun bfs(grid: Array<IntArray>, queue: ArrayDeque<Pair<Int, Int>>, visited: HashSet<Pair<Int, Int>>): Int {
    while (queue.isNotEmpty()) {
        ...
        val (x, y) = queue.removeFirst()
        // The first cell popped from the queue is definitly 1,
        // but it's the first island, not second island.
        // We need to distinguish the two islands.
        if (grid[x][y] == 1) return flip - 1
        for (d in directions) {
            ...
            queue.addLast(newX to newY)
            visited.add(newX to newY)
        }
    }
}
  • If we change the grid value as visited, we need to check if the grid cell is 1 (second island) before we change it when enqueuing the nodes. (See the second implementation.)

Using HashSet as Visited

To avoid the pitfalls, we can use two visited sets to distinguish the two islands. We use the first visited set to mark the first island when finding the first island, and then use the second visited set to mark the second island when finding the shortest path between the two islands.

// This is for second approach, it's the same idea, but we enqueue the nodes with the distance to the queue.
data class Cell(
    val x: Int,
    val y: Int,
    val distance: Int
)

fun shortestBridge(grid: Array<IntArray>): Int {
    val (x, y) = findStart(grid)
    val queue = ArrayDeque<Pair<Int, Int>>()
    // Or we can use a Cell class to store the distance.
    // val queue = ArrayDeque<Cell>()
    val island1 = HashSet<Pair<Int, Int>>()
    findFirstIsland(grid, x, y, island1, queue)
    return findSecondIsland(grid, island1, queue)
}

private fun findStart(grid: Array<IntArray>): Pair<Int, Int> {
    for (x in 0 until grid.size) {
        for (y in 0 until grid[0].size) {
            if (grid[x][y] == 1) return x to y
        }
    }
    // dummy return
    return -1 to -1
}

// General DFS function to find the first island, we traverse only the first island.
// Skip out of bound, visited, and water cells.
private fun findFirstIsland(grid: Array<IntArray>, x: Int, y: Int, visited: HashSet<Pair<Int, Int>>, queue: ArrayDeque<Pair<Int, Int>>) {
    val m = grid.size
    val n = grid[0].size
    if (x !in 0 until m || y !in 0 until n) return
    if (visited.contains(x to y)) return
    if (grid[x][y] != 1) return

    visited.add(x to y)
    queue.addLast(x to y)
    // Or we can enqueue the cell with distance to the queue.
    // queue.addLast(Cell(x, y, 0))

    directions.forEach { d ->
        val newX = x + d[0]
        val newY = y + d[1]
        findFirstIsland(grid, newX, newY, visited, queue)
    }
}

// We start from all cells in the first island, flip and find the shortest path to the second island.
private fun findSecondIsland(grid: Array<IntArray>, island1: HashSet<Pair<Int, Int>>, queue: ArrayDeque<Pair<Int, Int>>): Int {
    val n = grid.size
    // We use a dedicated set to store the visited nodes during this
    // BFS, not expanding the first island. Because we will add the 
    // nodes when enqueuing the adjacent nodes. Then we can't distinguish
    // the first island and the second island.
    val flipSet = HashSet<Pair<Int, Int>>()
    var flip = 0
    while (queue.isNotEmpty()) {
        val size = queue.size
        repeat(size) {
            val (x, y) = queue.removeFirst()
            // Here is the key part to distinguish the two islands: Check if it's not the first island.
            // Minus 1 to subtract the end cell.
            //
            // Or return `cell.distance - 1` if we use the Cell class to store the distance.
            if (grid[x][y] == 1 && island1.contains(x to y).not()) return flip - 1

            for (d in directions) {
                val newX = x + d[0]
                val newY = y + d[1]
                /** The adjacent cell might be 
                 * 1. out of bound
                 * 2. `0's` 
                 * 3. `1's` (first or second island)
                 */
                if (newX !in 0 until n) continue
                if (newY !in 0 until n) continue
                if (island1.contains(newX to newY)) continue
                if (flipSet.contains(newX to newY)) continue

                // Or we can return the distance if we find the second island.
                // if (grid[newX][newY] == 1) return flip - 1

                queue.addLast(newX to newY)

                // Or we can enqueue the cell with distance to the queue.
                // queue.addLast(Cell(newX, newY, cell.distance + 1))

                flipSet.add(newX to newY)
            }
        }
        flip++
    }
    return flip
}
  • Time Complexity: O(n^2).
  • Space Complexity: O(n^2).

Changing the Grid Value as Visited

Please pay attention to the following pitfalls:

  • We change the grid value as visited when we enqueue the nodes. So we can't use grid value to check if we reach the second island when we dequeue the nodes.
private val firstIsland = -1
private val flipIsland = -2

fun shortestBridge(grid: Array<IntArray>): Int {
    val (x, y) = findStart(grid)
    val queue = ArrayDeque<Pair<Int, Int>>()
    dfs(grid, x, y, queue)
    return bfs(grid, queue)
}

private fun findStart(grid: Array<IntArray>): Pair<Int, Int> {
    for (x in 0 until grid.size) {
        for (y in 0 until grid[0].size) {
            if (grid[x][y] == 1) return x to y
        }
    }
    // dummy return
    return -1 to -1
}

private fun dfs(grid: Array<IntArray>, x: Int, y: Int, queue: ArrayDeque<Pair<Int, Int>>) {
    val m = grid.size
    val n = grid[0].size
    if (x !in 0 until m || y !in 0 until n) return
    if (grid[x][y] != 1) return

    grid[x][y] = firstIsland
    queue.addLast(x to y)

    directions.forEach { d ->
        val newX = x + d[0]
        val newY = y + d[1]
        dfs(grid, newX, newY, queue)
    }
}

private fun bfs(grid: Array<IntArray>, queue: ArrayDeque<Pair<Int, Int>>): Int {
    val n = grid.size
    var flip = 0
    while (queue.isNotEmpty()) {
        val size = queue.size
        repeat(size) {
            val (x, y) = queue.removeFirst()
            // This is wrong answer when we mark the node as visited after we add it to the queue, we lose the original value of the grid:
            // if (grid[x][y] == 1) reteurn flip - 1

            for (d in directions) {
                val newX = x + d[0]
                val newY = y + d[1]
                if (newX !in 0 until n) continue
                if (newY !in 0 until n) continue
                if (grid[newX][newY] == firstIsland || grid[newX][newY] == flipIsland) continue

                // We must check if we reach the second island here for the adjacent nodes.
                if (grid[newX][newY] == 1) return flip

                // We enqueue the next node and mark it as visited. Here we lose the original value of the grid.
                queue.addLast(newX to newY)
                grid[newX][newY] = flipIsland
            }
        }
        flip++
    }
    return flip
}

Bidirectional BFS

  1. We find both islands by DFS or BFS. (using different visited sets)
  2. Expand island1 and island2 outwards until they meet.
fun shortestBridge(grid: Array<IntArray>): Int {
    val island1 = HashSet<Pair<Int, Int>>()
    val queue1 = ArrayDeque<Pair<Int, Int>>()
    val (x1, y1) = findStart(grid, island1)
    dfs(grid, x1, y1, island1, queue1)

    val island2 = HashSet<Pair<Int, Int>>()
    val queue2 = ArrayDeque<Pair<Int, Int>>()
    val (x2, y2) = findStart(grid, island1)
    dfs(grid, x2, y2, island2, queue2)

    return bfs(grid, island1, queue1, island2, queue2)
}

private fun findStart(grid: Array<IntArray>, visited: HashSet<Pair<Int, Int>>): Pair<Int, Int> {
    val m = grid.size
    val n = grid[0].size
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (grid[i][j] == 1 && visited.contains(i to j).not()) return i to j
        }
    }
    return -1 to -1
}

private fun dfs(
    grid: Array<IntArray>, 
    x: Int, y: Int, 
    visited: HashSet<Pair<Int, Int>>,
    queue: ArrayDeque<Pair<Int, Int>>
) {
    val m = grid.size
    val n = grid[0].size
    if (x !in 0 until m || y !in 0 until n) return
    if (visited.contains(x to y)) return
    if (grid[x][y] != 1) return
    visited.add(x to y)
    queue.addLast(x to y)
    for (d in directions) {
        val newX = x + d[0]
        val newY = y + d[1]
        dfs(grid, newX, newY, visited, queue)
    }
}

private fun bfs(
    grid: Array<IntArray>,
    island1: HashSet<Pair<Int, Int>>,
    queue1: ArrayDeque<Pair<Int, Int>>,
    island2: HashSet<Pair<Int, Int>>,
    queue2: ArrayDeque<Pair<Int, Int>>
): Int {
    var flip = 0
    while (queue1.isNotEmpty() && queue2.isNotEmpty()) {
        if (queue1.size <= queue2.size) {
            if (expand(grid, queue1, island1, island2)) return flip - 1
            flip++
        } else {
            if (expand(grid, queue2, island2, island1)) return flip - 1
            flip++
        }
    }
    return 0
}

// Return true if they meet.
private fun expand(
    grid: Array<IntArray>,
    queue: ArrayDeque<Pair<Int, Int>>,
    islandFrom: HashSet<Pair<Int, Int>>,
    islandTarget: HashSet<Pair<Int, Int>>
): Boolean {
    val m = grid.size
    val n = grid[0].size
    val size = queue.size
    repeat(size) {
        val (x, y) = queue.removeFirst()
        if (islandTarget.contains(x to y)) return true

        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) continue
            if (islandFrom.contains(newX to newY)) continue

            // Wrong implementation, the adjacent cell might be 0 or 1 (either island1 or island2)
            // if (grid[newX][newY] != 0) continue

            // Wrong implementation, they won't meet. For example, path `A -> X <- B`, we add `X` from `A`.
            // Then we will SKIP `X` because it's in visited set when we're expanding from `B`.
            // if (visited.contains(newX to newY)) continue

            // It could be water (0) or target island (1)
            queue.addLast(newX to newY)
            islandFrom.add(newX to newY)
        }
    }
    return false
}