DSA sheet · Graphs · Grid traversal (DFS / BFS)

Flood Fill

This is the "paint bucket" tool from any drawing app: click a pixel, and the whole same-coloured patch around it changes colour. It is the simplest grid traversal there is, which makes it the ideal place to learn the recursive grid DFS template: a "false condition" base case, change the cell, then 4 calls. The teacher also shows why the recolouring itself works as the visited marker, and a one-line base case (new colour = old colour) that is easy to skip but turns out to be essential.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Graph basics and grids as graphs
• Part A · Flood fill with DFS (the teacher's code)
• Part B · Flood fill with BFS
• Part C · Revision page

Part 0 · Graph basics and grids as graphs

Nodes, edges, and the two kinds of graph input

A graph is nodes joined by edges. Edges can be undirected (a)—(b), directed (a)→(b), or weighted (a)—4—(b). The teacher reminds us that graphs come in two looks:

• Nodes and edges (an edge list, an adjacency matrix, or an adjacency list). Here we must store the children of each node, usually in an adjacency list:

n = 3
edges = [[0, 1], [1, 2]]
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)          # undirected
print(adj)                    # [[1], [0, 2], [1]]

• A grid / matrix. Every cell is a node, and its children are the cells next to it. We don't store anything, because the children can be found from the index: up is (r-1, c), down is (r+1, c), left is (r, c-1), right is (r, c+1). Flood Fill is this kind.

            (r-1, c)
               ↑
 (r, c-1)  ←  (r, c)  →  (r, c+1)
               ↓
            (r+1, c)       diagonals are NOT neighbours here

Visited, connected components, BFS and DFS

Because neighbours point back at each other ((r, c) is a child of (r+1, c) and the other way round), a traversal must remember which cells it has already handled. Otherwise it bounces between two cells forever. That memory is the visited marker. All the cells you can reach from a start cell form its connected component. In Flood Fill, that's exactly the patch we must repaint. To reach them we can use DFS (recursion: go deep in one direction first) or BFS (a queue: spread ring by ring).

Grid toolkit: bounds and directions

• Bounds check: a cell is inside the grid only if 0 <= r < rows and 0 <= c < cols, with rows = len(image) and cols = len(image[0]). Check this before reading image[r][c]. (In Python, image[-1] silently means the last row, which is a sneaky bug.)
• dr / dc arrays: the 4 moves stored as pairs. The teacher's order: dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1] → (−1,0) up, (1,0) down, (0,−1) left, (0,1) right. Then the neighbours are (r + dr[i], c + dc[i]) for i = 0..3.
• Marking visited in place: sometimes the change you make to a cell is enough to stop you entering it again. Flood Fill is such a case (Part A, step 4).

rows, cols = 3, 3
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
r, c = 0, 2                       # top-right corner
inside = []
for i in range(4):
    nr, nc = r + dr[i], c + dc[i]
    if 0 <= nr < rows and 0 <= nc < cols:
        inside.append((nr, nc))
print(inside)                     # [(1, 2), (0, 1)]

Part A · Flood fill with DFS

LeetCode 733

1The question in simple words

You get an image as an m × n grid of integers. Each number is a pixel's colour. You also get a start pixel (sr, sc) (source row, source column) and a new color.

1. Remember the start pixel's colour, the original colour.
2. Repaint the start pixel with color.
3. Repaint every pixel that touches a repainted pixel up, down, left or right (not diagonally) and has the original colour. Keep spreading.
4. Stop when no more such pixels exist. Return the image.

      c0 c1 c2
 r0 [ 1, 1, 1 ]
 r1 [ 1,1, 0 ]     ← start (1,1), original = 1
 r2 [ 1, 0, 1 ]

      c0 c1 c2
 r0 [ 2, 2, 2 ]
 r1 [ 2, 2, 0 ]
 r2 [ 2, 0, 1 ]    ← never reached

The bottom-right 1 has the original colour, but it only touches the patch diagonally (through (1,1)). Its up and left neighbours are 0s. So the paint can't reach it, and it stays 1.

2What the constraints tell us

• 1 ≤ m, n ≤ 50 → at most 50 × 50 = 2,500 cells (2.5 × 10³). The teacher compares this with the rough 10⁸-operations limit for TLE: we're nowhere near it, so visiting each cell a few times is completely fine.
• Colour values are below 2¹⁶ = 65,536 → they fit in a normal int, so there's nothing to worry about (no "long" needed in Java/C++; Python ints never overflow anyway).
• 0 ≤ sr < m, 0 ≤ sc < n → the start is always inside the grid.
• A 50 × 50 patch could make the recursion up to 2,500 deep. Python's default limit is 1000, so in Python we raise it (or use BFS, Part B).

3Intuition: spilled paint

Pour paint on the start pixel. It runs into every neighbouring pixel that has the same old colour, then from those into their same-coloured neighbours, and so on. It stops at any different colour (a wall) and at the image border. The question doesn't ask for speed, it just says "repaint everything reachable". So any traversal that reaches every cell of the patch works, BFS or DFS. The teacher starts with DFS.

4Building the logic step by step

Step 1: read the original colour first

original = image[sr][sc]. We need it because a pixel may only be repainted if its colour equals the original. A 0 next to the start must not become 2. And once we start painting, the start cell itself will no longer show the original colour, so we must save it before we change anything.

Step 2: the base case: new colour = original colour

The teacher asks: what if the start is already colour 1 and we're told to paint it 1? Repainting 1s into 1s changes nothing, so return the image straight away.

Step 3: what does the DFS function need?

The teacher's rule: pass whatever changes between calls, or whatever the function can't otherwise know. That means the row and column (they change every call), the image, the new color, and the original colour (so every cell can be compared with it).

Step 4: no visited array needed, because the paint is the mark

Normally (in "90% of graph problems", as the teacher says) we keep a visited grid so we don't enter a cell twice. Here the work itself does the marking:

• We only enter a cell if it has the original colour.
• The first thing we do on entering is paint it with the new colour.
• So when a neighbour later looks back at it, it is no longer the original colour → "don't enter". That's exactly what visited would have said.

Her example: from (1,1) we go up into (0,1) and paint it. From (0,1), the cell below, (1,1), is a child again. But (1,1) is already 2, not 1, so we don't go there. No extra memory is needed.

Step 5: write the "false condition" first

In recursive DFS the teacher prefers to check when we must not continue, and return at once. Reasons to refuse a cell:

1. r < 0 or r >= rows: off the top or bottom (≥, because indexes stop at rows − 1);
2. c < 0 or c >= cols: off the left or right;
3. image[r][c] != original: a wall (a different colour), or a cell we already painted.

If none of these is true, the cell is inside and has the original colour, so paint it.

Step 6: paint, then 4 calls

After painting, visit the 4 children with 4 calls: (r+1, c), (r, c+1), (r-1, c), (r, c-1). We call blindly; any call into a bad cell just hits the false condition and returns. The teacher shows the same 4 calls can be written as a loop over dr/dc. Both are shown below.

Step 7: change the input or copy it?

The teacher's interview note: we paint the given image directly. If the interviewer doesn't want the input changed, make a copy first ([row[:] for row in image]) and paint the copy. Ask.

5Approach steps

1. original = image[sr][sc]. If original == color → return the image.
2. Call dfs(sr, sc), then return the image.
3. dfs(r, c): if out of bounds or image[r][c] != original → return.
4. Set image[r][c] = color.
5. Call dfs on down, right, up, left.

6Code (Python)

import sys

class Solution:
    def floodFill(self, image, sr, sc, color):
        sys.setrecursionlimit(10000)           # a 50 x 50 patch can go 2500 deep
        original = image[sr][sc]
        if original == color:                  # nothing to change (and avoids endless calls)
            return image
        self.dfs(image, sr, sc, color, original)
        return image

    def dfs(self, image, r, c, color, original):
        rows, cols = len(image), len(image[0])
        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != original:
            return                             # the "false condition"
        image[r][c] = color                    # paint = mark visited
        self.dfs(image, r + 1, c, color, original)   # down
        self.dfs(image, r, c + 1, color, original)   # right
        self.dfs(image, r - 1, c, color, original)   # up
        self.dfs(image, r, c - 1, color, original)   # left

import sys

class Solution:
    def floodFill(self, image, sr, sc, color):
        sys.setrecursionlimit(10000)
        original = image[sr][sc]
        if original == color:
            return image
        rows, cols = len(image), len(image[0])
        dr = [-1, 1, 0, 0]                     # up, down, left, right
        dc = [0, 0, -1, 1]

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != original:
                return
            image[r][c] = color
            for i in range(4):
                dfs(r + dr[i], c + dc[i])

        dfs(sr, sc)
        return image

7Code line by line

8Dry run with the call stack

Example 1, start (1,1), original 1, color 2. Call order inside each cell: down, right, up, left (the first code block). "✗" = the call returns at once.

1 2 2
1 2 0
1 0 1

2 2 2
2 2 0
2 0 1

2 2 2
2 2 0
2 0 1

Notice step 13: the left neighbour of the start was painted long ago through the "up" branch. When the start finally tries "left", the call bounces off. That's the DFS order from Doubt 3.

9Complexity & remember

• Time O(m·n). The teacher's counting: in the worst case (all pixels the original colour) every cell is painted once. Each painted cell makes 4 calls, including ones that bounce off walls or the border. That's about 4 · (rows · cols) calls, and dropping the constant 4 gives O(m·n). For 50 × 50 that's around 10⁴ calls, which is instant.
• Space O(m·n) for the recursion stack. In the worst case (all the same colour) the calls can chain through almost every cell before any of them returns, so the stack holds about rows · cols calls. No visited grid is used.

Part B · Flood fill with BFS

The teacher says this question works just as well with BFS ("also very simple") and leaves it for the next videos. Here is what changes. Everything about the colours, the base case and the paint-as-visited idea stays the same.

1–2Question & constraints

Same as Part A. A small bonus: BFS has no recursion, so the depth limit doesn't matter.

3Intuition

The paint spreads in rings: first the start, then its 4 neighbours, then theirs. A queue keeps the cells that are painted but whose neighbours haven't been checked yet.

4What changes from DFS

• Instead of "enter, then check the false condition", we check a neighbour before putting it in the queue: inside the grid and equal to original.
• We paint it at the moment we push it. That's the BFS form of "mark when you push", and it stops the same cell from being queued twice by two neighbours.
• The original == color check is still needed. Without it, a painted cell still equals original, and cells would be pushed again and again forever.

5Approach steps

1. original = image[sr][sc]. If it equals color, return.
2. Paint (sr, sc), push it.
3. While the queue isn't empty: pop (r, c). For each of the 4 directions: if (nr, nc) is inside and equals original → paint it, push it.
4. Return the image.

6Code (Python)

from collections import deque

class Solution:
    def floodFill(self, image, sr, sc, color):
        original = image[sr][sc]
        if original == color:
            return image
        rows, cols = len(image), len(image[0])
        dr = [-1, 1, 0, 0]
        dc = [0, 0, -1, 1]
        image[sr][sc] = color
        queue = deque([(sr, sc)])
        while queue:
            r, c = queue.popleft()
            for i in range(4):
                nr, nc = r + dr[i], c + dc[i]
                if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original:
                    image[nr][nc] = color          # paint when pushed
                    queue.append((nr, nc))
        return image

7Line by line (only the new lines)

8Dry run (directions up, down, left, right)

Step 3 shows "paint when pushed" at work: (0,0) was pushed by (0,1) and is already 2, so (1,0) doesn't push it again.

9Complexity & remember

• Time O(m·n): each cell is painted and pushed at most once, and looks at 4 neighbours.
• Space O(m·n) worst case for the queue (in practice only the current "ring" of cells).

Part C · Revision page

s = Solution()
print(s.floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2))   # [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
print(s.floodFill([[0, 0, 0], [0, 0, 0]], 0, 0, 0))              # [[0, 0, 0], [0, 0, 0]]
print(s.floodFill([[5]], 0, 0, 7))                               # [[7]]
print(s.floodFill([[1, 2], [2, 1]], 0, 0, 3))                    # [[3, 2], [2, 1]]
print(s.floodFill([[4, 4], [4, 4]], 1, 0, 9))                    # [[9, 9], [9, 9]]

Based on this video: Flood Fill | Graph