# Java Union And Find Method

• I implemented Union and Find Method to solve this problem.

``````class UF {
private int[] list;

public UF(int n) {
list = new int[n];
for (int i = 0; i < n; i++) {
list[i] = i;
}
}

private int root(int i) {
while (i != list[i]) {
list[i] = list[list[i]];
i = list[i];
}
return i;
}

public boolean connected(int i, int j) {
return root(i) == root(j);
}

public void union(int p, int q) {
int i = root(p);
int j = root(q);
list[i] = j;
}

public int maxUnion(char[][] grid) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < list.length; i++) {
int x = i / grid[0].length;
int y = i % grid[0].length;
if (grid[x][y] == '1') {
}
}
return set.size();
}
}

public class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

int height = grid.length;
int width = grid[0].length;
int totalSize = height * width;
UF uf = new UF(totalSize);
for (int i = 0; i < totalSize; i++) {
int x = i / width;
int y = i % width;
int up = x - 1;
int right = y + 1;
if (up >= 0 && grid[x][y] == grid[up][y] && grid[x][y] == '1')
uf.union(i, i - width);
if (right < width && grid[x][y] == grid[x][right]
&& grid[x][y] == '1')
uf.union(i, i + 1);
}
return uf.maxUnion(grid);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.