Matrix Graphs¶
Table of Contents¶
- 200. Number of Islands (Medium)
- 1020. Number of Enclaves (Medium)
- 1254. Number of Closed Islands (Medium)
- 695. Max Area of Island (Medium)
- 417. Pacific Atlantic Water Flow (Medium)
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;
}
1020. Number of Enclaves¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, depth first search, breadth first search, union find, matrix
1020. Number of Enclaves - Python Solution
from typing import List
# DFS
def numEnclaves(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
visited = set()
def dfs(r, c):
if (
r not in range(m)
or c not in range(n)
or grid[r][c] == 0
or (r, c) in visited
):
return
grid[r][c] = 0
visited.add((r, c))
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 (
(r in [0, m - 1] or c in [0, n - 1])
and grid[r][c] == 1
and (r, c) not in visited
):
dfs(r, c)
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 1 and (r, c) not in visited:
count += 1
return count
grid = [[0, 0, 0, 0], [1, 0, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
print(numEnclaves(grid)) # 3
1254. Number of Closed Islands¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, depth first search, breadth first search, union find, matrix
1254. Number of Closed Islands - Python Solution
from typing import List
# DFS
def closedIsland(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
visited = set()
def dfs(r, c):
if (
r not in range(m)
or c not in range(n)
or grid[r][c] == 1
or (r, c) in visited
):
return
grid[r][c] = 1
visited.add((r, c))
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 (
(r in [0, m - 1] or c in [0, n - 1])
and grid[r][c] == 0
and (r, c) not in visited
):
dfs(r, c)
island = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 0 and (r, c) not in visited:
island += 1
dfs(r, c)
return island
grid = [
[1, 1, 1, 1, 1, 1, 1, 0],
[1, 0, 0, 0, 0, 1, 1, 0],
[1, 0, 1, 0, 1, 1, 1, 0],
[1, 0, 0, 0, 0, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 0],
]
print(closedIsland(grid)) # 2
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;
}
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)]