Flood fill starts at one cell of a grid and changes every cell connected to it that has the same value, stopping at cells with a different value. It is the paint bucket in an image editor, the “reveal empty squares” step in Minesweeper, and the core of the interview problems “Flood Fill”, “Number of Islands” and “Max Area of Island”. You implement it with a graph search, either depth-first (recursion or a stack) or breadth-first (a queue). All of them visit each cell once, so they take O(R x C) time on an R by C grid.<\/p>\n
Below are four tested Python versions, the one detail that decides whether a recursive version crashes, and the bugs that most often show up in interviews.<\/p>\n
A grid is an implicit graph: each cell is a node and its neighbors are the cells next to it. Flood fill is a traversal of that graph with three decisions to make:<\/p>\n
That last point is the classic first bug. If the new color equals the old color, a fill never marks anything as visited and recursion runs forever. Return early in that case.<\/p>\n
def flood_fill_dfs(image, sr, sc, new_color):\n old = image[sr][sc]\n if old == new_color:\n return image\n rows, cols = len(image), len(image[0])\n\n def dfs(r, c):\n if not (0 <= r < rows and 0 <= c < cols) or image[r][c] != old:\n return\n image[r][c] = new_color\n dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)\n\n dfs(sr, sc)\n return image\n<\/code><\/pre>\nOn the grid [[1,1,1],[1,1,0],[1,0,1]]<\/code> with start (1, 1) and new color 2, this returns [[2, 2, 2], [2, 2, 0], [2, 0, 1]]<\/code>. The bottom-right 1 is not 4-connected to the start, so it stays 1.<\/p>\nThe weakness is depth. In the worst case (a big region shaped like a snake, or just a large empty grid) the recursion goes as deep as the number of cells. CPython’s default recursion limit is 1000, and filling a 2000 by 2000 grid of zeros with this function raises RecursionError<\/code>. Raising the limit with sys.setrecursionlimit<\/code> can crash the interpreter instead, because the C stack runs out. For anything that is not tiny, use an explicit stack or a queue.<\/p>\nIterative with a stack<\/h2>\ndef flood_fill_stack(image, sr, sc, new_color):\n old = image[sr][sc]\n if old == new_color:\n return image\n rows, cols = len(image), len(image[0])\n image[sr][sc] = new_color\n stack = [(sr, sc)]\n while stack:\n r, c = stack.pop()\n for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):\n if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:\n image[nr][nc] = new_color\n stack.append((nr, nc))\n return image\n<\/code><\/pre>\nNote that the cell is recolored when it is pushed<\/em>, not when it is popped. If you recolor on pop, the same cell can be pushed several times by different neighbors; the result is still right, but the stack can hold up to four entries per cell and you do more work.<\/p>\nIterative with a queue (BFS)<\/h2>\nfrom collections import deque\n\n\ndef flood_fill_bfs(image, sr, sc, new_color, diagonal=False):\n old = image[sr][sc]\n if old == new_color:\n return image\n rows, cols = len(image), len(image[0])\n steps = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n if diagonal:\n steps += [(1, 1), (1, -1), (-1, 1), (-1, -1)]\n image[sr][sc] = new_color\n queue = deque([(sr, sc)])\n while queue:\n r, c = queue.popleft()\n for dr, dc in steps:\n nr, nc = r + dr, c + dc\n if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:\n image[nr][nc] = new_color\n queue.append((nr, nc))\n return image\n<\/code><\/pre>\nUse deque<\/code>, not a list with pop(0)<\/code>, which is O(n). With diagonal=True<\/code> the same example grid fills the bottom-right cell too, because (2, 2) touches (1, 1) diagonally: the result is [[2, 2, 2], [2, 2, 0], [2, 0, 2]]<\/code>.<\/p>\nFor a plain fill, DFS and BFS give identical results; only the visiting order differs. BFS matters when you need distance from the start: the first time BFS reaches a cell is by a shortest path in steps, so you can store the distance as you go. That is the basis of the “01 Matrix” and “rotting oranges” style problems.<\/p>\n
Scanline fill<\/h2>\n
The versions above touch every cell individually and push many neighbors. Scanline fill fills a whole horizontal run of cells at once, then looks at the rows above and below that run and pushes one seed per run it finds. In large uniform areas, as in image editors, this cuts stack traffic a lot.<\/p>\n
def flood_fill_scanline(image, sr, sc, new_color):\n old = image[sr][sc]\n if old == new_color:\n return image\n rows, cols = len(image), len(image[0])\n stack = [(sr, sc)]\n while stack:\n r, c = stack.pop()\n if image[r][c] != old: # already filled through another seed\n continue\n left = c\n while left > 0 and image[r][left - 1] == old:\n left -= 1\n right = c\n while right < cols - 1 and image[r][right + 1] == old:\n right += 1\n for x in range(left, right + 1):\n image[r][x] = new_color\n for nr in (r - 1, r + 1):\n if 0 <= nr < rows:\n x = left\n while x <= right:\n if image[nr][x] == old:\n stack.append((nr, x)) # one seed per run\n while x <= right and image[nr][x] == old:\n x += 1\n else:\n x += 1\n return image\n<\/code><\/pre>\nIt is easy to get scanline wrong: a version that pushes every matching cell above and below, instead of one per run, is correct but loses the optimization. The if image[r][c] != old: continue<\/code> guard is needed because two seeds can end up in the same run. On 2,000 random grids up to 8 by 8, the four versions above produced identical results.<\/p>\nBoundary fill<\/h2>\n
Boundary fill is the same traversal with a different stop rule: spread until you hit a boundary color, whatever the interior contains. Keep the “already filled” check (image[r][c] == fill_color<\/code>) or it will loop forever, and prefer an iterative version for the same recursion-depth reason.<\/p>\nWhere it shows up in interview problems<\/h2>\n\n- Flood Fill<\/strong> (LeetCode 733): exactly the function above.<\/li>\n
- Number of Islands:<\/strong> scan the grid, and every time you meet an unvisited land cell, count one island and flood-fill it so it is not counted again. Practice it in Number Of Islands<\/a> and Size Of Islands<\/a>.<\/li>\n
- Max area of island:<\/strong> same scan, but each flood fill returns the number of cells it visited, and you keep the maximum.<\/li>\n
- Surrounded regions, enclaves:<\/strong> flood from the border inward, then treat whatever was not reached as enclosed.<\/li>\n
- Shortest steps in a grid:<\/strong> BFS with a distance counter, as in 01 Matrix<\/a>.<\/li>\n<\/ul>\n
When the grid must not be modified, keep a separate visited<\/code> set or a boolean grid. When it may be modified, overwriting the cell is simpler and uses no extra memory.<\/p>\nCommon bugs<\/h2>\n\n- New color equals old color.<\/strong> Infinite loop or recursion. Add the early return.<\/li>\n
- Checking bounds after indexing.<\/strong>
image[r][c]<\/code> with r = -1<\/code> does not raise in Python; it silently wraps to the last row. Check 0 <= r < rows<\/code> first.<\/li>\n- Swapping row and column.<\/strong> Image-editing code often uses (x, y) with x as the column; grid problems use (row, col). Mixing them gives a transposed fill.<\/li>\n
- Using a list as a queue<\/strong> with
pop(0)<\/code>.<\/li>\n- Recursing on a large grid<\/strong> in Python. Fine for a 10 by 10 puzzle, a crash on a 2000 by 2000 one.<\/li>\n
- Forgetting diagonals<\/strong> (or adding them) when the problem says otherwise.<\/li>\n<\/ol>\n
Real uses beyond interviews<\/h2>\n
Paint-bucket tools in image editors, region selection (“magic wand”), revealing empty cells in Minesweeper, finding connected regions in maps and game levels, and labeling connected components in image analysis all use the same traversal. Editors typically add a color tolerance (cells count as “the same” when they are close enough) and use scanline or other optimized variants; the grid logic is the same as above. If you want to see the same traversal on general graphs, see this post on flood fill for matrix problems<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"How flood fill works, with tested Python for recursive, stack, queue and scanline versions, 8-way connectivity, the recursion limit and common bugs.<\/p>\n","protected":false},"author":1,"featured_media":2012,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-2013","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-problem-solving"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/2013"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=2013"}],"version-history":[{"count":1,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/2013\/revisions"}],"predecessor-version":[{"id":8760,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/2013\/revisions\/8760"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/2012"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=2013"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=2013"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=2013"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}