Graph Flood Fill¶
Table of Contents¶
- 733. Flood Fill (Easy)
- 200. Number of Islands (Medium)
- 695. Max Area of Island (Medium)
- 463. Island Perimeter (Easy)
- 130. Surrounded Regions (Medium)
- 417. Pacific Atlantic Water Flow (Medium)
- 827. Making A Large Island (Hard)
733. Flood Fill¶
-
LeetCode | LeetCode CH (Easy)
-
Tags: array, depth first search, breadth first search, matrix
- Replace all the pixels of the same color starting from the given pixel.
- In other words, find the connected component of the starting pixel and change the color of all the pixels in that component.
- Edge cases: If the starting pixel is already the target color, return the image as it is.
- Flood Fill is essentially a graph traversal algorithm (like BFS or DFS) applied to matrices (2D grids). It checks adjacent cells (up, down, left, right) of a starting point to determine whether they belong to the same region. Typically, it involves modifying or marking the cells that belong to the same connected component.
| 1 | 1 | 1 |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
|---|---|---|
| 1 | 2 | 0 |
| 1 | 0 | 1 |
| 1 | 2 | 1 |
|---|---|---|
| 2 | 2 | 0 |
| 1 | 0 | 1 |
| 2 | 2 | 2 |
|---|---|---|
| 2 | 2 | 0 |
| 2 | 0 | 1 |
733. Flood Fill - Python Solution
from collections import deque
from typing import List
# DFS
def floodFillDFS(
image: List[List[int]], sr: int, sc: int, color: int
) -> List[List[int]]:
org = image[sr][sc]
m, n = len(image), len(image[0])
if org == color:
return image
def dfs(r, c):
if r < 0 or r >= m or c < 0 or c >= n or image[r][c] != org:
return None
image[r][c] = color
dfs(r - 1, c)
dfs(r + 1, c)
dfs(r, c - 1)
dfs(r, c + 1)
dfs(sr, sc)
return image
# BFS
def floodFillBFS(
image: List[List[int]], sr: int, sc: int, color: int
) -> List[List[int]]:
org = image[sr][sc]
m, n = len(image), len(image[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
if org == color:
return image
q = deque([(sr, sc)])
while q:
r, c = q.popleft()
image[r][c] = color
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and image[nr][nc] == org:
q.append((nr, nc))
return image
image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
sr = 1
sc = 1
print(floodFillDFS(image, sr, sc, 2))
# [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
print(floodFillBFS(image, sr, sc, 2))
# [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
200. Number of Islands¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, depth first search, breadth first search, union find, matrix
- Count the number of islands in a 2D grid.
- Method 1: DFS
-
Method 2: BFS (use a queue to traverse the grid)
-
How to keep track of visited cells?
- Mark the visited cell as
0(or any other value) to avoid revisiting it. - Use a set to store the visited cells.
- Mark the visited cell as
-
Steps:
- Init: variables
- DFS/BFS: starting from the cell with
1, turn all the connected1s to0. - Traverse the grid, and if the cell is
1, increment the count and call DFS/BFS.
200. Number of Islands - Python Solution
from collections import deque
from copy import deepcopy
from typing import List
# DFS
def numIslandsDFS(grid: List[List[str]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
res = 0
def dfs(r, c):
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != "1":
return
grid[r][c] = "2"
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(m):
for c in range(n):
if grid[r][c] == "1":
dfs(r, c)
res += 1
return res
# BFS + Set
def numIslandsBFS1(grid: List[List[str]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = set()
res = 0
def bfs(r, c):
q = deque([(r, c)])
while q:
row, col = q.popleft()
for dr, dc in dirs:
nr, nc = row + dr, col + dc
if (
nr < 0
or nr >= m
or nc < 0
or nc >= n
or grid[nr][nc] == "0"
or (nr, nc) in visited
):
continue
visited.add((nr, nc))
q.append((nr, nc))
for r in range(m):
for c in range(n):
if grid[r][c] == "1" and (r, c) not in visited:
visited.add((r, c))
bfs(r, c)
res += 1
return res
# BFS + Grid
def numIslandsBFS2(grid: List[List[str]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
res = 0
def bfs(r, c):
q = deque([(r, c)])
while q:
row, col = q.popleft()
for dr, dc in dirs:
nr, nc = dr + row, dc + col
if (
nr < 0
or nr >= m
or nc < 0
or nc >= n
or grid[nr][nc] != "1"
):
continue
grid[nr][nc] = "2"
q.append((nr, nc))
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
grid[i][j] = "2"
bfs(i, j)
res += 1
return res
grid = [
["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"],
]
print(numIslandsDFS(deepcopy(grid))) # 1
print(numIslandsBFS1(deepcopy(grid))) # 1
print(numIslandsBFS2(deepcopy(grid))) # 1
200. Number of Islands - C++ Solution
#include <vector>
#include <iostream>
using namespace std;
class Solution
{
private:
void dfs(vector<vector<char>> &grid, int r, int c)
{
int row = grid.size();
int col = grid[0].size();
if (r < 0 || r >= row || c < 0 || c >= col || grid[r][c] != '1')
{
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public:
int numIslands(vector<vector<char>> &grid)
{
int m = grid.size(), n = grid[0].size();
int res = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == '1')
{
res++;
dfs(grid, i, j);
}
}
}
return res;
}
};
int main()
{
Solution s;
vector<vector<char>> grid = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}};
cout << s.numIslands(grid) << endl;
return 0;
}
695. Max Area of Island¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, depth first search, breadth first search, union find, matrix
695. Max Area of Island - Python Solution
from collections import deque
from typing import List
# DFS
def maxAreaOfIslandDFS(grid: List[List[int]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != 1:
return 0
grid[r][c] = 2
return (
1 + dfs(r - 1, c) + dfs(r + 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
)
area = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
area = max(area, dfs(r, c))
return area
# BFS
def maxAreaOfIslandBFS1(grid: List[List[int]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = set()
res = 0
def bfs(r, c):
q = deque([(r, c)])
area = 0
while q:
row, col = q.popleft()
area += 1
for dr, dc in dirs:
nr, nc = row + dr, col + dc
if (
nr < 0
or nr >= m
or nc < 0
or nc >= n
or grid[nr][nc] == 0
or (nr, nc) in visited
):
continue
visited.add((nr, nc))
q.append((nr, nc))
return area
for r in range(m):
for c in range(n):
if grid[r][c] == 1 and (r, c) not in visited:
visited.add((r, c))
res = max(res, bfs(r, c))
return res
# BFS + Grid
def numIslandsBFS2(grid: List[List[str]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
res = 0
def bfs(r, c):
q = deque([(r, c)])
area = 0
while q:
row, col = q.popleft()
area += 1
for dr, dc in dirs:
nr, nc = row + dr, col + dc
if nr < 0 or nr >= m or nc < 0 or nc >= n or grid[nr][nc] == 0:
continue
q.append((nr, nc))
grid[nr][nc] = 0
return area
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
grid[r][c] = 0
res = max(res, bfs(r, c))
return res
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],
[0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
]
print(maxAreaOfIslandDFS(grid)) # 6
print(maxAreaOfIslandBFS1(grid)) # 6
print(numIslandsBFS2(grid)) # 6
695. Max Area of Island - C++ Solution
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int res = 0;
auto dfs = [&](auto&& self, int r, int c) -> int {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1) {
return 0;
}
grid[r][c] = 0;
return 1 + self(self, r - 1, c) + self(self, r, c - 1) +
self(self, r + 1, c) + self(self, r, c + 1);
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int area = dfs(dfs, i, j);
res = max(res, area);
}
}
}
return res;
}
};
int main() {
Solution s;
vector<vector<int>> 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},
{0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
cout << s.maxAreaOfIsland(grid) << endl;
return 0;
}
463. Island Perimeter¶
-
LeetCode | LeetCode CH (Easy)
-
Tags: array, depth first search, breadth first search, matrix
463. Island Perimeter - Python Solution
from typing import List
# DFS
def islandPerimeterDFS(grid: List[List[int]]) -> int:
# TC: O(m * n)
# SC: O(m * n)
visited = set()
m, n = len(grid), len(grid[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def dfs(r, c):
if (r, c) in visited or grid[r][c] == 0:
return 0
visited.add((r, c))
perimeter = 0
for dr, dc in directions:
nr, nc = r + dr, c + dc
if nr not in range(m) or nc not in range(n) or grid[nr][nc] == 0:
perimeter += 1
else:
perimeter += dfs(nr, nc)
return perimeter
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
return dfs(r, c)
return 0
def islandPerimeter(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
perimeter = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
perimeter += 4
if r > 0 and grid[r - 1][c] == 1:
perimeter -= 2
if c > 0 and grid[r][c - 1] == 1:
perimeter -= 2
return perimeter
grid = [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 0, 0]]
print(islandPerimeterDFS(grid)) # 16
print(islandPerimeter(grid)) # 16
130. Surrounded Regions¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, depth first search, breadth first search, union find, matrix
130. Surrounded Regions - Python Solution
from collections import deque
from copy import deepcopy
from pprint import pprint
from typing import List
# 1. DFS
def solveDFS(board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board and not board[0]:
return None
m, n = len(board), len(board[0])
def capture(r, c):
if r not in range(m) or c not in range(n) or board[r][c] != "O":
return None
board[r][c] = "T"
capture(r + 1, c)
capture(r - 1, c)
capture(r, c + 1)
capture(r, c - 1)
for r in range(m):
for c in range(n):
if board[r][c] == "O" and (r in [0, m - 1] or c in [0, n - 1]):
capture(r, c)
for r in range(m):
for c in range(n):
if board[r][c] == "O":
board[r][c] = "X"
for r in range(m):
for c in range(n):
if board[r][c] == "T":
board[r][c] = "O"
# 2. BFS
def solveBFS(board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board and not board[0]:
return None
m, n = len(board), len(board[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def capture(r, c):
q = deque([(r, c)])
while q:
row, col = q.popleft()
for dr, dc in directions:
nr = row + dr
nc = col + dc
if nr in range(m) and nc in range(n) and board[nr][nc] == "O":
q.append((nr, nc))
board[nr][nc] = "T"
for r in range(m):
for c in range(n):
if board[r][c] == "O" and (r in [0, m - 1] or c in [0, n - 1]):
board[r][c] = "T"
capture(r, c)
for r in range(m):
for c in range(n):
if board[r][c] == "O":
board[r][c] = "X"
for r in range(m):
for c in range(n):
if board[r][c] == "T":
board[r][c] = "O"
board = [
["X", "X", "X", "X"],
["X", "O", "O", "X"],
["X", "X", "O", "X"],
["X", "O", "X", "X"],
]
board1 = deepcopy(board)
solveDFS(board1)
pprint(board1)
# [['X', 'X', 'X', 'X'],
# ['X', 'X', 'X', 'X'],
# ['X', 'X', 'X', 'X'],
# ['X', 'O', 'X', 'X']]
board2 = deepcopy(board)
solveBFS(board2)
pprint(board2)
# [['X', 'X', 'X', 'X'],
# ['X', 'X', 'X', 'X'],
# ['X', 'X', 'X', 'X'],
# ['X', 'O', 'X', 'X']]
417. Pacific Atlantic Water Flow¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, depth first search, breadth first search, matrix
417. Pacific Atlantic Water Flow - Python Solution
from collections import deque
from typing import List
# DFS
def pacificAtlanticDFS(heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
pac, atl = set(), set()
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def dfs(r, c, visited, prev_height):
if (
r not in range(m)
or c not in range(n)
or heights[r][c] < prev_height
or (r, c) in visited
):
return None
visited.add((r, c))
height = heights[r][c]
for dr, dc in directions:
dfs(dr + r, dc + c, visited, height)
for c in range(n):
dfs(0, c, pac, heights[0][c])
dfs(m - 1, c, atl, heights[m - 1][c])
for r in range(m):
dfs(r, 0, pac, heights[r][0])
dfs(r, n - 1, atl, heights[r][n - 1])
return list(pac & atl)
# BFS
def pacificAtlanticBFS(heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
pac, atl = set(), set()
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def bfs(r, c, visited):
q = deque([(r, c)])
visited.add((r, c))
while q:
row, col = q.popleft()
for dr, dc in directions:
nr, nc = row + dr, col + dc
if (
nr in range(m)
and nc in range(n)
and heights[row][col] <= heights[nr][nc]
and (nr, nc) not in visited
):
q.append((nr, nc))
visited.add((nr, nc))
for c in range(n):
bfs(0, c, pac) # top
bfs(m - 1, c, atl) # bottom
for r in range(m):
bfs(r, 0, pac) # left
bfs(r, n - 1, atl) # right
return list(pac & atl)
heights = [
[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],
]
print(pacificAtlanticDFS(heights))
# [(4, 0), (0, 4), (3, 1), (1, 4), (3, 0), (2, 2), (1, 3)]
print(pacificAtlanticBFS(heights))
# [(4, 0), (0, 4), (3, 1), (1, 4), (3, 0), (2, 2), (1, 3)]
827. Making A Large Island¶
-
LeetCode | LeetCode CH (Hard)
-
Tags: array, depth first search, breadth first search, union find, matrix
827. Making A Large Island - Python Solution
from collections import defaultdict
from typing import List
# Flood Fill
def largestIsland(grid: List[List[int]]) -> int:
n = len(grid)
areas = defaultdict(int) # {index: area}
index = 2
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def dfs(r, c, index):
area = 1
grid[r][c] = index
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
area += dfs(nr, nc, index)
return area
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
areas[index] = dfs(r, c, index)
index += 1
if not areas:
return 1
res = max(areas.values())
for r in range(n):
for c in range(n):
if grid[r][c] == 0:
connected = set()
area = 1
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] > 1:
connected.add(grid[nr][nc])
for island in connected:
area += areas[island]
res = max(res, area)
return res
grid = [[1, 0], [0, 1]]
print(largestIsland(grid)) # 3