LeetCode: Flood Fill

Hello,

Here’s my solution for the flood fill problem, found on LeetCode.

If you want me to write about certain topics please let me know in the comments, thank you!

Link to the problem: https://leetcode.com/problems/flood-fill/

"""
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.
"""
from typing import List, Tuple


class Solution:
    def __init__(self):
        self.visited = set()

    def _set_pixel(self, image: List[List[int]], point: Tuple[int, int], value: int):
        try:
            image[point[0]][point[1]] = value
        except IndexError:
            pass

    def _get_pixel(self, image: List[List[int]], point: Tuple[int, int]):
        if point[0] < 0 or point[1] < 0:
            return None
        try:
            return image[point[0]][point[1]]
        except IndexError:
            return None

    def _floodFill(self, image: List[List[int]], point: Tuple[int, int], color: int, newColor: int) -> List[List[int]]:
        pixel = self._get_pixel(image, point)
        if pixel is not None and pixel == color and point not in self.visited:
            self.visited.add(point)
            self._set_pixel(image, point, newColor)
            self._floodFill(image, (point[0], point[1] + 1), color, newColor)
            self._floodFill(image, (point[0], point[1] - 1), color, newColor)
            self._floodFill(image, (point[0] + 1, point[1]), color, newColor)
            self._floodFill(image, (point[0] - 1, point[1]), color, newColor)

    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        point = (sr, sc)
        pixel = self._get_pixel(image, point)
        self.visited = set()
        if pixel is not None:
            self._floodFill(image, point, pixel, newColor)
        return image

if __name__ == '__main__':
    s = Solution()

    out = s.floodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2)
    print("Output", out)
    assert out == [[2,2,2],[2,2,0],[2,0,1]]

    out = s.floodFill([[0,0,0],[0,0,0]], 0, 0, 2)
    print("Output", out)
    assert out == [[2,2,2],[2,2,2]]

    out = s.floodFill([[0,0,0],[0,1,1]], 1, 1, 1)
    print("Output", out)
    assert out == [[0, 0, 0], [0, 1, 1]]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.