EasyNo. 0733

Flood Fill — LeetCode 733 Python Solution

Topics
Depth-First Search, Breadth-First Search, Array, Matrix
On a study list
Grind 75
Reading time
3 min

The problem

You are given an image represented by an m x n grid of integers image, where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color.

Python solution

PythonSolution
class Solution:
    def floodFill(
        self, image: List[List[int]], sr: int, sc: int, color: int
    ) -> List[List[int]]:
        def dfs(i: int, j: int):
            image[i][j] = color
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < len(image) and 0 <= y < len(image[0]) and image[x][y] == oc:
                    dfs(x, y)

        oc = image[sr][sc]
        if oc != color:
            dirs = (-1, 0, 1, 0, -1)
            dfs(sr, sc)
        return image

Complexity

Time
O(m × n)
Space · auxiliary
O(m × n)

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 733. Flood Fill is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0130Surrounded RegionsMedium
0200Number of IslandsMedium
0417Pacific Atlantic Water FlowMedium
0463Island PerimeterEasy
0529MinesweeperMedium
0695Max Area of IslandMedium

Frequently asked questions

How hard is LeetCode 733. Flood Fill?

LeetCode 733. Flood Fill is rated Easy on LeetCode.

What is the time complexity of LeetCode 733. Flood Fill?

The Python solution on this page runs in O(m × n).

What is the space complexity of LeetCode 733. Flood Fill?

The Python solution on this page uses O(m × n) auxiliary space.

What topics does LeetCode 733. Flood Fill cover?

LeetCode 733. Flood Fill is tagged Depth-First Search, Breadth-First Search, Array and Matrix on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.