This page did not load. You can still read it on the original site — the toolbar below keeps your place in the directory.

Leetcode: 733. Flood Fill DFS Primary idea: DFS BFS, starting from the starting node and checking the 4 neighbour nodes recursively. Time…

Leetcode: 733. Flood Fill

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]]

iOS Interview - Leetcode 733. Flood Fill

DFS

BFS

Comments