733.flood-fill.md

733. Flood Fill

Clarification Questions

• Can we modify the image directly or create a new one?
• Is the starting poisition valid?
• Is target color different from the starting pixel?

Test Cases

Edge / Corner Cases

• All the adjecent cells of the starting pixel have different color, so the image will not be changed.
• The color of the starting pixel is the same as the new color.
• There are some pixels with the same color as the starting pixel, but not connected to the starting pixel.

Traversal

We can use either BFS or DFS to traverse the image and change the color of the pixels. Here we need to pay attention that we only change the color of the pixels that have the same color as the starting pixel.

DFS

fun floodFill(image: Array<IntArray>, sr: Int, sc: Int, color: Int): Array<IntArray> {
    dfs(image, sr, sc, image[sr][sc], color)
    return image
}

fun dfs(image: Array<IntArray>, x: Int, y: Int, originalColor: Int, newColor: Int) {
    val m = image.size
    val n = image[0].size
    if (x !in 0 until m || y !in 0 until n) return  // out of bound
    if (image[x][y] == newColor) return             // visited
    if (image[x][y] != originalColor) return        // invalid

    image[x][y] = newColor

    for (dir in directions) {
        val newX = x + dir[0]
        val newY = y + dir[1]
        // Or optionally, we skip the invalid state here.
        if (newX !in 0 until m || newY !in 0 until n) continue
        if (image[newX][newY] != sourceColor) continue
        if (image[newX][newY] == targetColor) continue
        dfs(image, newX, newY, originalColor, newColor)
    }
}

BFS

fun floodFill(image: Array<IntArray>, sr: Int, sc: Int, color: Int): Array<IntArray> {
    bfs(image, sr, sc, image[sr][sc], color)
    return image
}

fun bfs(image: Array<IntArray>, sr: Int, sc: Int, color: Int): Array<IntArray> {
    val m = image.size
    val n = image[0].size
    val originalColor = image[sr][sc]
    
    val queue = ArrayDeque<Pair<Int, Int>>()
    queue.addLast(sr to sc)
    image[sr][sc] = color   // mark as visited
    while (queue.isNotEmpty()) {
        val (x, y) = queue.removeFirst()
        
        for (dir in directions) {
            val newX = x + dir[0]
            val newY = y + dir[1]
            if (newX !in 0 until m || newY !in 0 until n) continue
            if (image[newX][newY] != originalColor) continue
            if (image[newX][newY] == color) continue

            queue.addLast(newX to newY)
            image[newX][newY] = color   // mark as visited
        }
    }
    return image
}

fun bfs(image: Array<IntArray>, sr: Int, sc: Int, color: Int): Array<IntArray> {
    val m = image.size
    val n = image[0].size
    val originalColor = image[sr][sc]
    
    val queue = ArrayDeque<Pair<Int, Int>>()
    queue.addLast(sr to sc)
    while (!queue.isEmpty()) {
        val (x, y) = queue.removeFirst()
        if (x !in 0 until m || y !in 0 until n) continue
        if (image[x][y] != originalColor) continue
        if (image[x][y] == color) continue
        image[x][y] = color
        
        for (dir in directions) {
            val newX = x + dir[0]
            val newY = y + dir[1]
            queue.addLast(newX to newY)
        }
    }
    return image
}

• Time Complexity: O(m * n).
• Space Complexity: O(m * n).