My accepted attempt. What is the order?


  • 0
    Z

    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()){
                    ultimateParents.add(rowCol);
                }
                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;
                    }
                    ultimateParents.add(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);
                        }
                    }
                }
                list.add(ultimateParents.size());
            }
            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){
                output.add(map.get(rc.row).get(rc.col));
            }
            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;
                }
            }
        }
    }
    
    

Log in to reply
 

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