# My accepted attempt. What is the order?

• The idea is to do union find and make the row/col combination as the parent which is least in rank. Rank is determined by comparing row and then column. I store a list of ultimate parents. The number of ultimate parents at each level is the number of islands. I think the order is O(klogk) where k is m*n. Log k comes from finding the ultimate parent. Is that correct analysis?

``````class Solution {
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> list = new ArrayList<>();
if (m == 0 || n == 0 || positions.length == 0) return list;
int[][] grid = new int[m][n];

Map<Integer, Map<Integer, RowCol>> map = new HashMap<>();
Set<RowCol> ultimateParents = new HashSet<>();
for(int[] position : positions){
int row = position[0];
int col = position[1];
grid[row][col] = 1;
RowCol rowCol = new RowCol(row, col, null);
if(!map.containsKey(row)){
map.put(row, new HashMap<>());
}
map.get(row).put(col, rowCol);

List<RowCol> neighbors = getSurroundingNeighbors(row, col, grid, map);
if(neighbors.isEmpty()){
}
else{
Collections.sort(neighbors);
RowCol ultimate = findUltimate(neighbors.get(0));
if(ultimate.compareTo(rowCol) >0){
ultimate.parent = rowCol;
ultimateParents.remove(ultimate);
ultimate = rowCol;
}else{
rowCol.parent = ultimate;
}

for(int i = 1; i< neighbors.size(); i++){
RowCol neighbor = map.get(neighbors.get(i).row).get(neighbors.get(i).col);
RowCol rowCol1 = findUltimate(neighbor);
if(rowCol1 != ultimate) {
rowCol1.parent = ultimate;
ultimateParents.remove(rowCol1);
}
}
}
}
return list;
}

private RowCol findUltimate(RowCol neighbor) {
if (neighbor.parent == null) return neighbor;
return findUltimate(neighbor.parent);
}

private List<RowCol> getSurroundingNeighbors(int row, int col, int[][] grid, Map<Integer, Map<Integer, RowCol>> map) {
List<RowCol> rowCols = new ArrayList<>();
if (row - 1 >= 0) {
if (grid[row - 1][col] == 1) {
rowCols.add(new RowCol(row - 1, col, null));
}
}
if (row + 1 < grid.length) {
if (grid[row + 1][col] == 1) {
rowCols.add(new RowCol(row + 1, col, null));
}
}
if (col - 1 >= 0) {
if (grid[row][col - 1] == 1) {
rowCols.add(new RowCol(row, col - 1, null));
}
}
if (col + 1 < grid[0].length) {
if (grid[row][col + 1] == 1) {
rowCols.add(new RowCol(row, col + 1, null));
}
}
List<RowCol> output = new ArrayList<>();
for(RowCol rc : rowCols){
}
return output;
}

class RowCol implements Comparable<RowCol>, Comparator<RowCol> {
int row;
int col;
RowCol parent;

public RowCol(int row, int col, RowCol parent) {
this.row = row;
this.col = col;
this.parent = parent;
}

public boolean equals(Object obj) {
if (obj == null) return false;
if (!(obj instanceof RowCol)) return false;
if (obj == this) return true;
RowCol rowCol = (RowCol) obj;
return rowCol.row == this.row && rowCol.col == this.col;
}

public int hashCode() {
return 23 * row + 23 * col;
}

public int compareTo(RowCol rowCol) {
if (this.row < rowCol.row) {
return -1;
}

if (this.row > rowCol.row) {
return 1;
} else {
return this.col - rowCol.col;
}
}

public int compare(RowCol o1, RowCol rowCol) {
if (o1.row < rowCol.row) {
return -1;
}

if (o1.row > rowCol.row) {
return 1;
} else {
return o1.col - rowCol.col;
}
}
}
}

``````

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