DFS: Connected Components and Flood Fill
Apply DFS to count connected components, solve number-of-islands on a 2D grid, and implement flood fill for image processing.
DFS: Connected Components and Flood Fill is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Connected Components Defined
A connected component in an undirected graph is a maximal set of vertices such that there is a path between every pair of vertices in the set. A single graph can have multiple disconnected components. Finding connected components is the foundation of many graph problems: grouping, merging, island counting, and account consolidation all reduce to this primitive.
from collections import defaultdict
# Graph with 3 components: {0,1,2}, {3,4}, {5}
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,2),(3,4)]:
graph[u].append(v)
graph[v].append(u)
# Node 5 is isolated (no edges)
for node in [0,1,2,3,4,5]:
if node not in graph:
graph[node] = []
# We need DFS or BFS from each unvisited node
# to discover all components
print('Graph has nodes 0-5 with components: {0,1,2}, {3,4}, {5}')Counting Connected Components with DFS
Iterate over all nodes. For each unvisited node, launch a DFS to mark all reachable nodes as visited. Each DFS launch corresponds to discovering one new component. Count the number of DFS launches to get the number of components. This O(V + E) algorithm works correctly whether the graph is connected or not.
from collections import defaultdict
def count_components(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
def dfs(node):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
dfs(nb)
for node in range(n):
if node not in visited:
dfs(node)
count += 1
return count
print(count_components(6, [(0,1),(0,2),(1,2),(3,4)])) # 3
print(count_components(5, [(0,1),(1,2),(3,4)])) # 2Number of Islands
Number of Islands (LeetCode #200) is the canonical connected-components problem on a 2D grid. Each '1' cell belongs to an island; adjacent '1' cells (up/down/left/right) form the same island. Count the number of distinct islands using DFS: iterate over all cells, and when you find an unvisited '1', start a DFS that marks all connected '1' cells (flood fill), then increment the count.
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != '1':
return
grid[r][c] = '#' # mark visited in-place
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count
grid = [['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']]
print(num_islands(grid)) # 3Flood Fill Algorithm
Flood Fill (LeetCode #733) replaces all connected cells of a given starting colour with a new colour — exactly like the paint-bucket tool in image editors. Use DFS: starting from the source pixel, recursively recolour all neighbours that match the original colour. The key edge case: if the starting cell's colour already equals the new colour, return immediately to avoid infinite recursion.
def flood_fill(image, sr, sc, new_color):
original = image[sr][sc]
if original == new_color:
return image # edge case: same color, nothing to do
rows, cols = len(image), len(image[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if image[r][c] != original:
return
image[r][c] = new_color
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
dfs(sr, sc)
return image
image = [[1,1,1],[1,1,0],[1,0,1]]
result = flood_fill(image, 1, 1, 2)
for row in result: print(row)
# [[2,2,2],[2,2,0],[2,0,1]]Max Area of Island
Max Area of Island (LeetCode #695) extends island counting: for each island, return the size of the largest one. During the DFS flood fill, count the cells you mark. The DFS returns the size of the current island, and you track the maximum across all islands. This is a simple augmentation of the connected-components pattern.
def max_area_of_island(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
max_area = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return 0
if grid[r][c] != 1:
return 0
grid[r][c] = 0 # mark visited
return (1 + dfs(r+1,c) + dfs(r-1,c) +
dfs(r,c+1) + dfs(r,c-1))
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
max_area = max(max_area, dfs(r, c))
return max_area
grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0]]
print(max_area_of_island(grid)) # 6Pacific Atlantic Water Flow
Pacific Atlantic Water Flow (LeetCode #417) asks which cells can flow to both the Pacific (top/left edges) and Atlantic (bottom/right edges) oceans. Instead of simulating water flowing down, use reverse DFS: water flows up from the oceans. Do two DFS sweeps — one from Pacific borders, one from Atlantic borders — collecting reachable cells. The intersection is the answer.
def pacific_atlantic(heights):
rows, cols = len(heights), len(heights[0])
pac = set(); atl = set()
def dfs(r, c, visited, prev_h):
if (r,c) in visited or r < 0 or r >= rows or c < 0 or c >= cols:
return
if heights[r][c] < prev_h:
return # water can't flow uphill in reverse
visited.add((r,c))
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(r+dr, c+dc, visited, heights[r][c])
for r in range(rows):
dfs(r, 0, pac, heights[r][0]) # Pacific left
dfs(r, cols-1, atl, heights[r][cols-1]) # Atlantic right
for c in range(cols):
dfs(0, c, pac, heights[0][c]) # Pacific top
dfs(rows-1, c, atl, heights[rows-1][c]) # Atlantic bottom
return sorted(pac & atl) # intersection
print(pacific_atlantic([[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]))Iterative DFS for Connected Components
Use iterative DFS (with an explicit stack) to avoid Python's recursion limit on large grids. The iterative version is equivalent to recursive DFS but uses a stack instead of the call stack. Push the starting node, then pop, mark visited, and push unvisited neighbours. This handles grids up to millions of cells safely where recursive DFS would cause a stack overflow.
def count_components_iterative(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
for start in range(n):
if start in visited:
continue
# Iterative DFS
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for nb in graph[node]:
if nb not in visited:
stack.append(nb)
count += 1
return count
print(count_components_iterative(6, [(0,1),(0,2),(1,2),(3,4)])) # 3Surrounded Regions
Surrounded Regions (LeetCode #130) captures all 'O' regions that are completely surrounded by 'X' borders. A region is NOT captured if any of its 'O' cells touches the board's edge. The trick: instead of finding surrounded regions directly, do a DFS from all border 'O' cells and mark everything reachable as safe. Then flip: all remaining 'O' cells are surrounded and become 'X', and safe cells are restored to 'O'.
def solve(board):
if not board:
return
rows, cols = len(board), len(board[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if board[r][c] != 'O':
return
board[r][c] = 'S' # safe: connected to border
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
# Mark border-connected O's as safe
for r in range(rows):
dfs(r, 0); dfs(r, cols-1)
for c in range(cols):
dfs(0, c); dfs(rows-1, c)
# Flip: surrounded O -> X, safe S -> O
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O': board[r][c] = 'X'
elif board[r][c] == 'S': board[r][c] = 'O'
board = [['X','X','X','X'],['X','O','O','X'],
['X','X','O','X'],['X','O','X','X']]
solve(board)
print([board[1][1], board[3][1]]) # X, OCount Sub-Islands
Count Sub-Islands (LeetCode #1905) finds islands in grid2 that are entirely contained within an island in grid1. DFS from each '1' cell in grid2: an island is a sub-island if every cell it visits is also '1' in grid1. The trick: visit ALL cells of the island (to mark them as explored) but track whether ALL of them were also '1' in grid1. Don't short-circuit on the first '0' in grid1 — you'd miss marking other cells of the same island.
def count_sub_islands(grid1, grid2):
rows, cols = len(grid2), len(grid2[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return True
if grid2[r][c] != 1:
return True
grid2[r][c] = 0 # mark visited
is_sub = grid1[r][c] == 1 # this cell must be in grid1
is_sub = dfs(r+1,c) and is_sub # note: AND not short-circuit OR
is_sub = dfs(r-1,c) and is_sub
is_sub = dfs(r,c+1) and is_sub
is_sub = dfs(r,c-1) and is_sub
return is_sub
count = 0
for r in range(rows):
for c in range(cols):
if grid2[r][c] == 1 and dfs(r, c):
count += 1
return count
print(count_sub_islands([[1,1,1],[1,0,1],[1,1,1]],
[[1,1,1],[1,0,1],[1,1,1]])) # 1DFS vs BFS for Connected Components
Both DFS and BFS correctly find all connected components with the same O(V + E) time and O(V) space complexity. DFS is simpler to implement recursively for connected-components problems, while BFS is preferred when you also need shortest-path information. In grid problems, DFS is more cache-friendly because it explores deep into one direction before backtracking, accessing nearby memory locations sequentially.
# DFS advantages for connected components:
# - Simpler recursive implementation
# - Lower constant factor for small graphs
# - Can restore grid state during backtracking (if needed)
# BFS advantages:
# - Finds shortest path while traversing
# - Better for wide, shallow graphs (avoids deep recursion)
# - Multi-source initialisation is natural
# Same asymptotic complexity: O(V + E) time, O(V) space
# Grid (m rows, n cols): O(mn) time and space
print('DFS and BFS: same O(V+E) complexity for component counting')Islands with Constraints: Shapes and Perimeters
Island Perimeter (LeetCode #463) counts the total perimeter of the single island in a grid. For each land cell ('1'), add 4 to the perimeter, then subtract 2 for each adjacent land cell (shared edges). This O(mn) formula-based approach requires no DFS — but understanding that it is equivalent to a DFS that counts boundary edges reinforces the connection between grid problems and graph reasoning.
def island_perimeter(grid):
rows, cols = len(grid), len(grid[0])
perimeter = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
perimeter += 4 # start with 4 sides
# Subtract shared edges with adjacent land cells
if r > 0 and grid[r-1][c] == 1:
perimeter -= 2 # shared top edge
if c > 0 and grid[r][c-1] == 1:
perimeter -= 2 # shared left edge
return perimeter
grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
print(island_perimeter(grid)) # 16Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: connected components via DFS with visited tracking, number of islands and flood fill as canonical 2D grid applications, and advanced patterns like reverse DFS from borders (surrounded regions) and multi-DFS with constraint tracking (sub-islands). Next up we tackle cycle detection in directed and undirected graphs.
Frequently asked questions
Is the “DFS: Connected Components and Flood Fill” lesson free?
Yes — the full text of “DFS: Connected Components and Flood Fill” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “DFS: Connected Components and Flood Fill”?
Apply DFS to count connected components, solve number-of-islands on a 2D grid, and implement flood fill for image processing. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “DFS: Connected Components and Flood Fill” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Graph Representations and Traversal Setup
- BFS: Shortest Path and Level Traversal
- DFS: Connected Components and Flood Fill
- Cycle Detection in Directed and Undirected Graphs