Skip to content

Commit 24b6848

Browse files
cheehwatangcheehwatang
authored
Merge pull request cheehwatang#75 from cheehwatang/add-200-NumberOfIslands
Add 200. Number of Islands (Union Find)
2 parents f6c614a + 4dcef2c commit 24b6848

File tree

2 files changed

+154
-25
lines changed

2 files changed

+154
-25
lines changed

‎README.md

Lines changed: 50 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,19 @@ As I'm new to [LeetCode](https://leetcode.com/cheehwatang/) and programming in g
3535
<th>Solution</th>
3636
<th>Topics</th>
3737
</tr>
38+
<tr>
39+
<td align="center">January 5th</td>
40+
<td>200. <a href="https://leetcode.com/problems/number-of-islands/">Number of Islands</a></td>
41+
<td align="center">$\text{\color{Dandelion}Medium}$</td>
42+
<td align="center">
43+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_UnionFind.java">Union Find</a>
44+
</td>
45+
<td align="center">
46+
<a href="#array">Array</a><a>, </a>
47+
<a href="#matrix">Matrix</a><a>, </a>
48+
<a href="#union-find">Union Find</a>
49+
</td>
50+
</tr>
3851
<tr>
3952
<td align="center">January 4th</td>
4053
<td>200. <a href="https://leetcode.com/problems/number-of-islands/">Number of Islands</a></td>
@@ -82,21 +95,6 @@ As I'm new to [LeetCode](https://leetcode.com/cheehwatang/) and programming in g
8295
<a href="#math">Math</a>
8396
</td>
8497
</tr>
85-
<tr>
86-
<td align="center">December 31st</td>
87-
<td>797. <a href="https://leetcode.com/problems/all-paths-from-source-to-target/">All Paths From Source to Target</a></td>
88-
<td align="center">$\text{\color{Dandelion}Medium}$</td>
89-
<td align="center">
90-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/797.%20All%20Paths%20From%20Source%20to%20Target/AllPathsFromSourceToTarget_DFS_Recursive_Backtracking.java">Depth-First Search (Backtracking)</a><a>, </a>
91-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/797.%20All%20Paths%20From%20Source%20to%20Target/AllPathsFromSourceToTarget_DFS_Iterative.java">Depth-First Search (Iterative)</a><a> or </a>
92-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/797.%20All%20Paths%20From%20Source%20to%20Target/AllPathsFromSourceToTarget_DFS_Recursive.java">Depth-First Search (Recursive)</a>
93-
</td>
94-
<td align="center">
95-
<a href="#backtracking">Backtracking</a><a>, </a>
96-
<a href="#depth-first-search">Depth-First Search</a><a>, </a>
97-
<a href="#graph">Graph</a>
98-
</td>
99-
</tr>
10098
</table>
10199

102100
</br>
@@ -302,15 +300,17 @@ As I'm new to [LeetCode](https://leetcode.com/cheehwatang/) and programming in g
302300
<td align="center">200</td>
303301
<td><a href="https://leetcode.com/problems/number-of-islands/">Number of Islands</a></td>
304302
<td align="center"><a>Java with </a>
305-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_BFS.java">Breadth-First Search</a><a> or </a>
306-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_DFS.java">Depth-First Search</a>
303+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_BFS.java">Breadth-First Search</a><a>, </a>
304+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_DFS.java">Depth-First Search</a><a> or </a>
305+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_UnionFind.java">Union Find</a>
307306
</td>
308307
<td align="center">$\text{\color{Dandelion}Medium}$</td>
309308
<td align="center">
310309
<a href="#array">Array</a><a>, </a>
311310
<a href="#breadth-first-search">Breadth-First Search</a><a>, </a>
312311
<a href="#depth-first-search">Depth-First Search</a><a>, </a>
313-
<a href="#matrix">Matrix</a>
312+
<a href="#matrix">Matrix</a><a>, </a>
313+
<a href="#union-find">Union Find</a>
314314
</td>
315315
<td></td>
316316
</tr>
@@ -1396,10 +1396,12 @@ As I'm new to [LeetCode](https://leetcode.com/cheehwatang/) and programming in g
13961396
<a href="#array">Array</a><a>, </a>
13971397
<a href="#breadth-first-search">Breadth-First Search</a><a>, </a>
13981398
<a href="#depth-first-search">Depth-First Search</a><a>, </a>
1399-
<a href="#matrix">Matrix</a>
1399+
<a href="#matrix">Matrix</a><a>, </a>
1400+
<a href="#union-find">Union Find</a>
14001401
</td>
14011402
<td><a>Solution Using </a>
1402-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_DFS.java"><em>Depth-First Search</em></a>
1403+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_DFS.java"><em>Depth-First Search</em></a><a> or </a>
1404+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_UnionFind.java"><em>Union Find</em></a>
14031405
</td>
14041406
</tr>
14051407
<tr>
@@ -1609,10 +1611,12 @@ As I'm new to [LeetCode](https://leetcode.com/cheehwatang/) and programming in g
16091611
<a href="#array">Array</a><a>, </a>
16101612
<a href="#breadth-first-search">Breadth-First Search</a><a>, </a>
16111613
<a href="#depth-first-search">Depth-First Search</a><a>, </a>
1612-
<a href="#matrix">Matrix</a>
1614+
<a href="#matrix">Matrix</a><a>, </a>
1615+
<a href="#union-find">Union Find</a>
16131616
</td>
16141617
<td><a>Solution Using </a>
1615-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_BFS.java"><em>Breadth-First Search</em></a>
1618+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_BFS.java"><em>Breadth-First Search</em></a><a> or </a>
1619+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_UnionFind.java"><em>Union Find</em></a>
16161620
</td>
16171621
</tr>
16181622
<tr>
@@ -3332,15 +3336,17 @@ As I'm new to [LeetCode](https://leetcode.com/cheehwatang/) and programming in g
33323336
<td align="center">200</td>
33333337
<td><a href="https://leetcode.com/problems/number-of-islands/">Number of Islands</a></td>
33343338
<td align="center"><a>Java with </a>
3335-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_BFS.java">Breadth-First Search</a><a> or </a>
3336-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_DFS.java">Depth-First Search</a>
3339+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_BFS.java">Breadth-First Search</a><a>, </a>
3340+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_DFS.java">Depth-First Search</a><a> or </a>
3341+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_UnionFind.java">Union Find</a>
33373342
</td>
33383343
<td align="center">$\text{\color{Dandelion}Medium}$</td>
33393344
<td align="center">
33403345
<a href="#array">Array</a><a>, </a>
33413346
<a href="#breadth-first-search">Breadth-First Search</a><a>, </a>
33423347
<a href="#depth-first-search">Depth-First Search</a><a>, </a>
3343-
<a href="#matrix">Matrix</a>
3348+
<a href="#matrix">Matrix</a><a>, </a>
3349+
<a href="#union-find">Union Find</a>
33443350
</td>
33453351
<td></td>
33463352
</tr>
@@ -4803,6 +4809,25 @@ As I'm new to [LeetCode](https://leetcode.com/cheehwatang/) and programming in g
48034809
<th>Topics</th>
48044810
<th>Note</th>
48054811
</tr>
4812+
<tr>
4813+
<td align="center">200</td>
4814+
<td><a href="https://leetcode.com/problems/number-of-islands/">Number of Islands</a></td>
4815+
<td align="center">
4816+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_UnionFind.java">Java</a>
4817+
</td>
4818+
<td align="center">$\text{\color{Dandelion}Medium}$</td>
4819+
<td align="center">
4820+
<a href="#array">Array</a><a>, </a>
4821+
<a href="#breadth-first-search">Breadth-First Search</a><a>, </a>
4822+
<a href="#depth-first-search">Depth-First Search</a><a>, </a>
4823+
<a href="#matrix">Matrix</a><a>, </a>
4824+
<a href="#union-find">Union Find</a>
4825+
</td>
4826+
<td><a>Solution Using </a>
4827+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_BFS.java"><em>Breadth-First Search</em></a><a> or </a>
4828+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/200.%20Number%20of%20Islands/NumberOfIslands_DFS.java"><em>Depth-First Search</em></a>
4829+
</td>
4830+
</tr>
48064831
<tr>
48074832
<td align="center">1971</td>
48084833
<td><a href="https://leetcode.com/problems/find-if-path-exists-in-graph/">Find if Path Exists in Graph</a></td>

‎solutions/200. Number of Islands/NumberOfIslands_UnionFind.java

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
package com.cheehwatang.leetcode;
2+
3+
// Time Complexity : O(m * n),
4+
// where 'm' is the number of rows, and 'n' is the number of columns of the 'grid'.
5+
// We traverse the 'grid' in two occasions,
6+
// 1. Set the set representative (parent) for land '1' in the 'grid' to itself.
7+
// 2. Traverse the 'grid' to find lands, and union the land adjacent to another land.
8+
//
9+
// Space Complexity : O(m * n),
10+
// where 'm' is the number of rows, and 'n' is the number of columns of the 'grid'.
11+
// We used an array to keep track of the set representative (parent) for each position in the 'grid'.
12+
13+
public class NumberOfIslands_UnionFind {
14+
15+
// Approach:
16+
// Using Union-Find data structure, we first make all the land '1' on the 'grid' as separate disjoint sets,
17+
// or separate islands.
18+
// Imagine we start with many islands of only one land '1'.
19+
// As we traverse 'grid' and check if two lands '1' are adjacent to one another,
20+
// we merge (union) the two lands '1' as a single island, reducing the number of islands by one.
21+
// Once we have traversed the whole 'grid',
22+
// we have merged all the lands '1' to their respective islands (disjoint sets).
23+
// Here, we implemented path compression and union by rank to lower time complexity.
24+
25+
public int numIslands(char[][] grid) {
26+
int rows = grid.length;
27+
int columns = grid[0].length;
28+
29+
// 'parent' array to record the set representatives for each position.
30+
// Note that we are hashing the position with 'row' and 'column' into 'landID' "row * column + column".
31+
int[] parent = new int[rows * columns];
32+
33+
// The 'rank' array is used as part of the union by rank implementation,
34+
// with the ranks when merging (union),
35+
// and the node with higher rank to be the parent of the node with lower rank.
36+
int[] rank = new int[rows * columns];
37+
38+
int islands = 0;
39+
// Set up the disjoint set data structure by referencing all the nodes (positions) to itself.
40+
// Additionally, count the number of land '1' as the number of 'islands' at the start.
41+
for (int row = 0; row < rows; row++) {
42+
for (int column = 0; column < columns; column++) {
43+
// If the position is water, move to the next position.
44+
if (grid[row][column] == '0') continue;
45+
// Hash the position as 'landID'.
46+
int landID = row * columns + column;
47+
islands++;
48+
parent[landID] = landID;
49+
}
50+
}
51+
52+
// Creating an array for the directions (up, down, left, right) for simpler execution later.
53+
int[][] directions = new int[][] {{1,0}, {-1,0}, {0,1}, {0,-1}};
54+
for (int row = 0; row < rows; row++) {
55+
for (int column = 0; column < columns; column++) {
56+
// If the position is water, move to the next position.
57+
if (grid[row][column] == '0') continue;
58+
int landID1 = row * columns + column;
59+
// Check all the positions adjacent for land '1'.
60+
for (int[] direction : directions) {
61+
int x = row + direction[0];
62+
int y = column + direction[1];
63+
// If the position is out of bound or is water '0', continue to the next position.
64+
if (x < 0 || x >= rows || y < 0 || y >= columns || grid[x][y] == '0') continue;
65+
// If found a land '1', union the two position and decrease the 'islands' by 1.
66+
int landID2 = x * columns + y;
67+
if (union(landID1, landID2, parent, rank)) islands--;
68+
}
69+
}
70+
}
71+
// Once all the land '1' is in their respective disjoint set, we have the number of 'islands'.
72+
return islands;
73+
}
74+
75+
// Method to find the set representative (parent) of the node, with path compression implemented.
76+
private int find(int landID, int[] parent) {
77+
// Continue to find the parent until the node references itself,
78+
// that the self-referencing node is the set representative.
79+
if (parent[landID] == landID) return landID;
80+
// Compress that path by referencing all the children node along the path directly to the parent node.
81+
return parent[landID] = find(parent[landID], parent);
82+
}
83+
84+
// Method to merge (union) two nodes, with union by rank implemented.
85+
private boolean union(int landID1, int landID2, int[] parent, int[] rank) {
86+
int find1 = find(landID1, parent);
87+
int find2 = find(landID2, parent);
88+
// If the two nodes are already in the same disjoint set (island),
89+
// return false, indicating that the union is not successful.
90+
if (find1 == find2) return false;
91+
92+
// If node 2 'find2' has a higher rank, make node 2 'find2' the parent of node 1 'find1'.
93+
if (rank[find2] > rank[find1]) {
94+
parent[find1] = find2;
95+
}
96+
// If node 1 'find1' has a higher rank, make node 1 'find1' the parent of node 2 'find2'.
97+
else {
98+
parent[find2] = find1;
99+
// If both node has the same rank, increase the rank of the parent (node 1 'find1') by 1.
100+
if (rank[find1] == rank[find2]) rank[find1]++;
101+
}
102+
return true;
103+
}
104+
}

0 commit comments

Comments
 (0)