Skip to content

Commit 361b8aa

Browse files
gazeldxgazeldx
committed
827-making-a-large-island.md Simplified Python solution.
1 parent 2e4a38e commit 361b8aa

File tree

4 files changed

+112
-130
lines changed

4 files changed

+112
-130
lines changed

‎README.md

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -85,8 +85,6 @@ You can skip the more difficult problems and do them later.
8585
- [188. Best Time to Buy and Sell Stock IV](en/1-1000/188-best-time-to-buy-and-sell-stock-iv.md) was solved in _Python, JavaScript, Go_.
8686
- [309. Best Time to Buy and Sell Stock with Cooldown](en/1-1000/309-best-time-to-buy-and-sell-stock-with-cooldown.md) was solved in _Python, JavaScript, Go_.
8787

88-
to here now
89-
9088
## Subsequence Problems
9189
- [674. Longest Continuous Increasing Subsequence](en/1-1000/674-longest-continuous-increasing-subsequence.md) was solved in _Python, Java, JavaScript, C#_.
9290
- [300. Longest Increasing Subsequence](en/1-1000/300-longest-increasing-subsequence.md) was solved in _Python, Java, JavaScript, C#_.

‎en/1-1000/827-making-a-large-island.md

Lines changed: 54 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -60,9 +60,9 @@ And this graph may have multiple **connected components** (islands):
6060
## Approach
6161
1. Change one vertex from `0` to `1` to make the largest island means combining the adjacent islands of a `0` vertex.
6262
1. We can mark an island's lands with one same id (`island_id`), and mark another island's lands with another `island_id`. To mark a land, just change its value to the `island_id`.
63-
1. Use a `map` (or an `array`) to map each `island_id` to its area (`land_count`).
63+
1. Use a `map` (or an `array`) to map each `island_id` to its `area`.
6464
1. How to calculate the area of an island? Using `Depth-First Search` or `Breadth-First Search`. See [695. Max Area of Island](695-max-area-of-island.md).
65-
1. Iterate through each `0` (water), then sum the areas (`land_count`) of neighboring islands.
65+
1. Iterate through each `0` (water), then sum the `areas` of neighboring islands.
6666
1. Record the max area and return it.
6767

6868
## Complexity
@@ -71,88 +71,78 @@ And this graph may have multiple **connected components** (islands):
7171

7272
## Python
7373
```python
74+
from collections import defaultdict
75+
7476
class Solution:
7577
def __init__(self):
76-
self.result = 0
77-
self.grid = None
78-
self.land_count = 0
79-
self.land_counts = [0, 0] # Since `island_id` starts from 2, the first two records will not be used
8078
self.island_id = 2
79+
self.island_id_to_area = defaultdict(int)
8180

8281
def largestIsland(self, grid: List[List[int]]) -> int:
8382
self.grid = grid
83+
max_area = 0
8484

85-
for i, row in enumerate(self.grid):
86-
for j, value in enumerate(row):
87-
if value == 1:
88-
self.land_count = 0
89-
85+
for i in range(len(grid)):
86+
for j in range(len(grid[0])):
87+
if self.grid[i][j] == 1:
9088
self.depth_first_search(i, j)
89+
self.island_id += 1
9190

92-
self.land_counts.append(self.land_count)
93-
94-
self.result = max(self.land_count, self.result)
91+
has_water = False
9592

96-
self.island_id += 1
97-
98-
for i, row in enumerate(grid):
99-
for j, value in enumerate(row):
100-
if value == 0:
101-
self.result = max(
102-
self.combined_islands_land_count(i, j),
103-
self.result
104-
)
105-
106-
return self.result
93+
for i in range(len(grid)):
94+
for j in range(len(grid[0])):
95+
if self.grid[i][j] == 0:
96+
has_water = True
97+
max_area = max(max_area, self.combined_islands_area(i, j))
98+
99+
if not has_water:
100+
return len(grid) * len(grid[0])
101+
102+
return max_area
107103

108104
def depth_first_search(self, i, j):
109-
if i < 0 or i >= len(self.grid):
110-
return
111-
112-
if j < 0 or j >= len(self.grid[0]):
105+
if i < 0 or j < 0 or i >= len(self.grid) or j >= len(self.grid[0]):
113106
return
114-
107+
115108
if self.grid[i][j] != 1:
116109
return
117-
118-
self.grid[i][j] = self.island_id
119-
120-
self.land_count += 1
121-
122-
self.depth_first_search(i - 1, j)
123-
self.depth_first_search(i, j + 1)
124-
self.depth_first_search(i + 1, j)
125-
self.depth_first_search(i, j - 1)
126-
127-
def combined_islands_land_count(self, i, j):
128-
used_island_ids = set()
129-
count = 1
130110

131-
count += self.island_land_count(i - 1, j, used_island_ids)
132-
count += self.island_land_count(i, j + 1, used_island_ids)
133-
count += self.island_land_count(i + 1, j, used_island_ids)
134-
count += self.island_land_count(i, j - 1, used_island_ids)
135-
136-
return count
111+
self.grid[i][j] = self.island_id
112+
self.island_id_to_area[self.island_id] += 1
113+
114+
for a, b in [
115+
(-1, 0),
116+
(0, -1), (0, 1),
117+
(1, 0)
118+
]:
119+
m = i + a
120+
n = j + b
121+
self.depth_first_search(m, n)
137122

138-
def island_land_count(self, i, j, used_island_ids):
139-
if i < 0 or i >= len(self.grid):
140-
return 0
141-
142-
if j < 0 or j >= len(self.grid[0]):
143-
return 0
123+
def combined_islands_area(self, i, j):
124+
island_ids = set()
125+
126+
for a, b in [
127+
(-1, 0),
128+
(0, -1), (0, 1),
129+
(1, 0)
130+
]:
131+
m = i + a
132+
n = j + b
133+
134+
if m < 0 or n < 0 or m >= len(self.grid) or n >= len(self.grid[0]):
135+
continue
136+
137+
if self.grid[m][n] != 0:
138+
island_ids.add(self.grid[m][n])
144139

145-
if self.grid[i][j] == 0:
146-
return 0
140+
area = 1
147141

148-
island_id = self.grid[i][j]
142+
for island_id in island_ids:
143+
area += self.island_id_to_area[island_id]
149144

150-
if island_id in used_island_ids:
151-
return 0
152-
153-
used_island_ids.add(island_id)
154-
155-
return self.land_counts[island_id]
145+
return area
156146
```
157147

158148
## Java

‎en/3001-4000/unorganized.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -164,6 +164,9 @@ The improved way with a queue is commonly more efficient. Relaxing **All Edges**
164164
- 647 https://leetcode.cn/problems/palindromic-substrings/ very hard
165165
- 516 https://leetcode.cn/problems/longest-palindromic-subsequence/
166166

167+
### Graph
168+
- 417 https://leetcode.com/problems/pacific-atlantic-water-flow/
169+
167170
### Failed in 2 rounds
168171
- 222 https://leetcode.cn/problems/count-complete-tree-nodes/
169172
- 236 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
@@ -176,5 +179,6 @@ The improved way with a queue is commonly more efficient. Relaxing **All Edges**
176179
- 115 https://leetcode.cn/problems/distinct-subsequences/
177180
- 647 https://leetcode.cn/problems/palindromic-substrings/ https://leetcode.cn/problems/palindromic-substrings/submissions/597748845/
178181
- 516 https://leetcode.cn/problems/longest-palindromic-subsequence/
182+
- 417 https://leetcode.com/problems/pacific-atlantic-water-flow/
179183

180184
2005-02-09 day 2

‎zh/1-1000/827-making-a-large-island.md

Lines changed: 54 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -60,9 +60,9 @@ And this graph may have multiple **connected components** (islands):
6060
## Approach
6161
1. Change one vertex from `0` to `1` to make the largest island means combining the adjacent islands of a `0` vertex.
6262
1. We can mark an island's lands with one same id (`island_id`), and mark another island's lands with another `island_id`. To mark a land, just change its value to the `island_id`.
63-
1. Use a `map` (or an `array`) to map each `island_id` to its area (`land_count`).
63+
1. Use a `map` (or an `array`) to map each `island_id` to its `area`.
6464
1. How to calculate the area of an island? Using `Depth-First Search` or `Breadth-First Search`. See [695. Max Area of Island](695-max-area-of-island.md).
65-
1. Iterate through each `0` (water), then sum the areas (`land_count`) of neighboring islands.
65+
1. Iterate through each `0` (water), then sum the `areas` of neighboring islands.
6666
1. Record the max area and return it.
6767

6868
## Complexity
@@ -71,88 +71,78 @@ And this graph may have multiple **connected components** (islands):
7171

7272
## Python
7373
```python
74+
from collections import defaultdict
75+
7476
class Solution:
7577
def __init__(self):
76-
self.result = 0
77-
self.grid = None
78-
self.land_count = 0
79-
self.land_counts = [0, 0] # Since `island_id` starts from 2, the first two records will not be used
8078
self.island_id = 2
79+
self.island_id_to_area = defaultdict(int)
8180

8281
def largestIsland(self, grid: List[List[int]]) -> int:
8382
self.grid = grid
83+
max_area = 0
8484

85-
for i, row in enumerate(self.grid):
86-
for j, value in enumerate(row):
87-
if value == 1:
88-
self.land_count = 0
89-
85+
for i in range(len(grid)):
86+
for j in range(len(grid[0])):
87+
if self.grid[i][j] == 1:
9088
self.depth_first_search(i, j)
89+
self.island_id += 1
9190

92-
self.land_counts.append(self.land_count)
93-
94-
self.result = max(self.land_count, self.result)
91+
has_water = False
9592

96-
self.island_id += 1
97-
98-
for i, row in enumerate(grid):
99-
for j, value in enumerate(row):
100-
if value == 0:
101-
self.result = max(
102-
self.combined_islands_land_count(i, j),
103-
self.result
104-
)
105-
106-
return self.result
93+
for i in range(len(grid)):
94+
for j in range(len(grid[0])):
95+
if self.grid[i][j] == 0:
96+
has_water = True
97+
max_area = max(max_area, self.combined_islands_area(i, j))
98+
99+
if not has_water:
100+
return len(grid) * len(grid[0])
101+
102+
return max_area
107103

108104
def depth_first_search(self, i, j):
109-
if i < 0 or i >= len(self.grid):
110-
return
111-
112-
if j < 0 or j >= len(self.grid[0]):
105+
if i < 0 or j < 0 or i >= len(self.grid) or j >= len(self.grid[0]):
113106
return
114-
107+
115108
if self.grid[i][j] != 1:
116109
return
117-
118-
self.grid[i][j] = self.island_id
119-
120-
self.land_count += 1
121-
122-
self.depth_first_search(i - 1, j)
123-
self.depth_first_search(i, j + 1)
124-
self.depth_first_search(i + 1, j)
125-
self.depth_first_search(i, j - 1)
126-
127-
def combined_islands_land_count(self, i, j):
128-
used_island_ids = set()
129-
count = 1
130110

131-
count += self.island_land_count(i - 1, j, used_island_ids)
132-
count += self.island_land_count(i, j + 1, used_island_ids)
133-
count += self.island_land_count(i + 1, j, used_island_ids)
134-
count += self.island_land_count(i, j - 1, used_island_ids)
135-
136-
return count
111+
self.grid[i][j] = self.island_id
112+
self.island_id_to_area[self.island_id] += 1
113+
114+
for a, b in [
115+
(-1, 0),
116+
(0, -1), (0, 1),
117+
(1, 0)
118+
]:
119+
m = i + a
120+
n = j + b
121+
self.depth_first_search(m, n)
137122

138-
def island_land_count(self, i, j, used_island_ids):
139-
if i < 0 or i >= len(self.grid):
140-
return 0
141-
142-
if j < 0 or j >= len(self.grid[0]):
143-
return 0
123+
def combined_islands_area(self, i, j):
124+
island_ids = set()
125+
126+
for a, b in [
127+
(-1, 0),
128+
(0, -1), (0, 1),
129+
(1, 0)
130+
]:
131+
m = i + a
132+
n = j + b
133+
134+
if m < 0 or n < 0 or m >= len(self.grid) or n >= len(self.grid[0]):
135+
continue
136+
137+
if self.grid[m][n] != 0:
138+
island_ids.add(self.grid[m][n])
144139

145-
if self.grid[i][j] == 0:
146-
return 0
140+
area = 1
147141

148-
island_id = self.grid[i][j]
142+
for island_id in island_ids:
143+
area += self.island_id_to_area[island_id]
149144

150-
if island_id in used_island_ids:
151-
return 0
152-
153-
used_island_ids.add(island_id)
154-
155-
return self.land_counts[island_id]
145+
return area
156146
```
157147

158148
## Java

0 commit comments

Comments
 (0)