[Leetcode] 733. Flood Fill

Problem Link: https://leetcode.com/problems/flood-fill/

Flood Fill - LeetCode

 

Solution 1. BFS

Time: $O(\text{log } N)$

Space: $O(1)$ 

from collections import deque

class Solution(object):
    def floodFill(self, image, sr, sc, color):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type color: int
        :rtype: List[List[int]]
        """
        m = len(image); n = len(image[0]); target = image[sr][sc]
        if target == color: return image

        queue = deque(); queue.append((sr, sc)); image[sr][sc] = color
        while queue:
            h, w = queue.popleft()
            if h > 0 and image[h-1][w] == target:
                image[h-1][w] = color
                queue.append((h-1, w))
            if h < m - 1 and image[h+1][w] == target:
                image[h+1][w] = color
                queue.append((h+1, w))
            if w > 0 and image[h][w-1] == target:
                image[h][w-1] = color
                queue.append((h, w-1))
            if w < n - 1 and image[h][w+1] == target:
                image[h][w+1] = color
                queue.append((h, w+1))

        return image

 

Solution 2. DFS (Stack)

Time: $O(\text{log } N)$

Space: $O(1)$ 

 

 

from collections import deque

class Solution(object):
    def floodFill(self, image, sr, sc, color):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type color: int
        :rtype: List[List[int]]
        """
        target = image[sr][sc]
        if target == color: return image

        m = len(image); n = len(image[0])
        stack = deque(); stack.append((sr, sc)); image[sr][sc] = color
        while stack:
            h, w = stack.pop()
            if h > 0 and image[h-1][w] == target:
                image[h-1][w] = color
                stack.append((h-1, w))
            if h < m - 1 and image[h+1][w] == target:
                image[h+1][w] = color
                stack.append((h+1, w))
            if w > 0 and image[h][w-1] == target:
                image[h][w-1] = color
                stack.append((h, w-1))
            if w < n - 1 and image[h][w+1] == target:
                image[h][w+1] = color
                stack.append((h, w+1))

        return image

 

Solution 3. DFS (Recursion)

Time: $O(\text{log } N)$

Space: $O(1)$ 

 

from collections import deque

class Solution(object):
    def floodFill(self, image, sr, sc, color):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type color: int
        :rtype: List[List[int]]
        """
        if image[sr][sc] == color: return image

        m = len(image); n = len(image[0]); target = image[sr][sc]
        def fill(h, w):
            if image[h][w] == target:
                image[h][w] = color
                if h > 0: fill(h-1, w)
                if h < m - 1: fill(h+1, w)
                if w > 0: fill(h, w-1)
                if w < n - 1: fill(h, w+1)
        
        fill(sr, sc)
        return image