LC 733

DFS
Graph
Publish Date:   2022-01-31

Solution to LeetCode 733 Flood Fill.

LeetCode 733

Flood Fill (Easy). [link]

Time complexity O(height*width), space complexity O(1).

class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        if image[sr][sc] == newColor:
            return image
        
        width = len(image[0])
        height = len(image)
        
        self.DFS(image, sc, sr, width, height, image[sr][sc], newColor)
        return image
    
    def DFS(self, image, w, h, width, height, oriColor, newColor):
        if w < 0 or w >= width or h < 0 or h >= height:
            return
        if image[h][w] != oriColor: # pruning if the color is already changed or it shouldn't be changed
            return
        image[h][w] = newColor
        self.DFS(image, w+1, h, width, height, oriColor, newColor)
        self.DFS(image, w-1, h, width, height, oriColor, newColor)
        self.DFS(image, w, h+1, width, height, oriColor, newColor)
        self.DFS(image, w, h-1, width, height, oriColor, newColor)
DFS
  TOC