iOS Interview - Leetcode 733. Flood Fill

May 08, 2024 • 3 min read • #swift, #interview, #leetcode

DFS

Primary idea: DFS BFS, starting from the starting node and checking the 4 neighbour nodes recursively.
Time Complexity: O(n)
Space Complexity: O(n)

func floodFill(_ image: [[Int]], _ sr: Int, _ sc: Int, _ color: Int) -> [[Int]] {
    guard image[sr][sc] != color else { return image }

    var newImage = image
    let oldColor = image[sr][sc]

    dfs(&newImage, sr, sc, oldColor, color)

    return newImage
}

private func dfs(_ image: inout [[Int]], _ row: Int, _ column: Int, _ oldColor: Int, _ newColor: Int) {
    image[row][column] = newColor

    if row + 1 < image.count, image[row + 1][column] == oldColor {
        dfs(&image, row + 1, column, oldColor, newColor)
    }

    if row > 0, image[row - 1][column] == oldColor {
        dfs(&image, row - 1, column, oldColor, newColor)
    }

    if column + 1 < image[row].count, image[row][column+1] == oldColor {
        dfs(&image, row, column+1, oldColor, newColor)
    }

    if column > 0, image[row][column-1] == oldColor {
        dfs(&image, row, column-1, oldColor, newColor)
    }
}

print(floodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2)) // [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
print(floodFill([[0,0,0],[0,0,0]], 0, 0, 0)) // [[0, 0, 0], [0, 0, 0]]

BFS

Primary idea: BFS, starting from the starting node and use a queue to add 4 neighbour nodes.
Time Complexity: O(n)
Space Complexity: O(n)

func floodFill(_ image: [[Int]], _ sr: Int, _ sc: Int, _ newColor: Int) -> [[Int]] {
    let oldColor = image[sr][sc]
    if oldColor == newColor { return image }

    let height = image.count
    let width = image[0].count
    var result = image
    var queue = [(Int, Int)]()
    var queueIndex = 0 // head of "queue"
    var queueCount = 1 // count of "queue"
    queue.append((sr, sc))

    while queueIndex < queueCount {
        let (row, col) = queue[queueIndex]
        queueIndex += 1

        if row < 0 || row >= height || col < 0 || col >= width { continue }
        if result[row][col] != oldColor { continue }

        result[row][col] = newColor

        queue.append((row - 1, col))
        queue.append((row + 1, col))
        queue.append((row, col - 1))
        queue.append((row, col + 1))
        queueCount += 4
    }

    return result
}

print(floodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2)) // [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
print(floodFill([[0,0,0],[0,0,0]], 0, 0, 0)) // [[0, 0, 0], [0, 0, 0]]