-
Notifications
You must be signed in to change notification settings - Fork 4
/
remove-islands.py
152 lines (142 loc) · 5.02 KB
/
remove-islands.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
# Remove Islands
# 🟠 Medium
#
# https://www.algoexpert.io/questions/remove-islands
#
# Tags: Array - Matrix - Graph - Depth-First Search
import timeit
from typing import List
# Use depth first search to mark all island cells 4 directionally
# adjacent to a cell in the edge of the matrix as safe, then visit all
# cells in the matrix removing any island that has not been marked as
# safe.
#
# Time complexity: O(m*n) - Where m is the number of rows and n is the
# number of columns.
# Space complexity: O(1) - The exercise asks us to mutate the input
# matrix in place, if we didn't want to we could create a copy using
# O(m*n) memory.
class Solution:
def removeIslands(self, matrix: List[List[int]]) -> List[List[int]]:
NUM_ROWS, NUM_COLS = len(matrix), len(matrix[0])
# Define a function that turns all 1s of a given island into 2s.
def dfs(r: int, c: int) -> None:
# Mark this cell as adjacent to the edge.
matrix[r][c] = 2
dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
for rc, cc in dir:
tr = r + rc
tc = c + cc
if (
0 <= tr < NUM_ROWS
and 0 <= tc < NUM_COLS
and matrix[tr][tc] == 1
):
dfs(tr, tc)
# Update all 1s adjacent to a border.
for c in range(NUM_COLS):
if matrix[0][c]:
dfs(0, c)
if matrix[NUM_ROWS - 1][c]:
dfs(NUM_ROWS - 1, c)
for r in range(NUM_ROWS):
if matrix[r][0]:
dfs(r, 0)
if matrix[r][NUM_COLS - 1]:
dfs(r, NUM_COLS - 1)
# Remove the islands.
for r in range(NUM_ROWS):
for c in range(NUM_COLS):
if matrix[r][c] == 1:
matrix[r][c] = 0
elif matrix[r][c] == 2:
matrix[r][c] = 1
return matrix
def test():
executors = [Solution]
tests = [
[[[1]], [[1]]],
[
[
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
],
[
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
],
],
[
[
[1, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 1, 0],
[1, 1, 0, 0, 1, 0],
[1, 0, 1, 1, 0, 0],
[1, 0, 0, 0, 0, 1],
],
[
[1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1],
[0, 0, 0, 0, 1, 0],
[1, 1, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1],
],
],
[
[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
],
[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
],
],
]
for executor in executors:
start = timeit.default_timer()
for _ in range(1):
for col, t in enumerate(tests):
sol = executor()
result = sol.removeIslands(t[0])
exp = t[1]
assert result == exp, (
f"\033[93m» {result} <> {exp}\033[91m for"
+ f" test {col} using \033[1m{executor.__name__}"
)
stop = timeit.default_timer()
used = str(round(stop - start, 5))
cols = "{0:20}{1:10}{2:10}"
res = cols.format(executor.__name__, used, "seconds")
print(f"\033[92m» {res}\033[0m")
test()