Leetcode – Flood Fill Solution in Python

Spread the love

One of the problems you might encounter on Leetcode is the Flood Fill problem, an interesting and typical algorithm question that employs depth-first search (DFS) or breadth-first search (BFS). This article will take you through the problem’s description and a detailed solution in Python.

Problem Description

The problem “Flood Fill” (Leetcode 733) is described as follows:

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image.

To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Approach

For this problem, we can use a simple DFS algorithm. We start from the pixel given in the input, change its color and continue to its neighboring pixels in 4 directions (up, down, left, and right) until there are no neighboring pixels with the same color as the starting pixel. To avoid revisiting the same pixel and causing an infinite loop, we first check if the pixel’s current color is the same as the new color. If it is, we return the image without making any changes.

Python Solution

Here is a Python solution using DFS:

class Solution:
    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]]
        """
        rows, cols, oldColor = len(image), len(image[0]), image[sr][sc]

        # If the color of the starting pixel is the same as the new color, return the image without any changes.
        if oldColor == newColor: 
            return image

        def dfs(r, c):
            # If the pixel is out of the image boundaries or is not the old color, return.
            if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != oldColor:
                return

            # Color the pixel with the new color.
            image[r][c] = newColor

            # Visit the neighboring pixels in 4 directions.
            dfs(r - 1, c)
            dfs(r + 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)

        dfs(sr, sc)
        return image

In this solution, we define a helper function dfs() that uses the DFS algorithm to flood fill the image. If a pixel is out of the image boundaries or if its color is not the old color, we return without making any changes. Otherwise, we color the pixel with the new color and recursively visit its neighboring pixels in 4 directions.

The time complexity of this solution is O(n), where n is the number of pixels in the image. This is because in the worst-case scenario, we have to visit all the pixels in the image. The space complexity is also O(n), which is the maximum depth of the recursion stack.

Testing the Solution

Let’s test our solution with the following example from Leetcode:

s = Solution()
print(s.floodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2))

The expected output is [[2,2,2],[2,2,0],[2,0,1]].

Conclusion

The Flood Fill problem is a typical DFS problem that can be solved using a straightforward DFS algorithm. It provides an excellent opportunity to practice recursion and DFS. Remember, the key to solving such problems is to carefully follow the problem’s rules and constraints, write a clear and efficient algorithm, and thoroughly test your solution with various test cases. This will ensure that your solution works correctly and can handle a variety of inputs.

Leave a Reply