Easy Java Solution Beats 93%


  • 1
    public class Solution {
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            List<Integer> res = new ArrayList();
            int[][] matrix = new int[m][n];
            int[] roots = new int[m * n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    roots[j + i * n] = j + i * n;
                }
            }
            int count = 0;
            int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            for (int[] pos : positions) {
                count++;
                int ox = pos[0];
                int oy = pos[1];
                matrix[ox][oy] = 1;
                for (int[] d : dirs) {
                    int x = ox + d[0];
                    int y = oy + d[1];
                    if (x >= m || x < 0 || y >= n || y < 0) continue;
                    if (matrix[x][y] == 1) {
                        int root1 = find(roots, y + x * n);
                        int root2 = find(roots, oy + ox * n);
                        if (root1 != root2) {
                            roots[root1] = root2;
                            count--;
                        }
                    }
                }
                res.add(count);
            }
            
            return res;
        }
        
        private int find(int[] roots, int key) {
            while (roots[key] != key) {
                roots[key] = roots[roots[key]];
                key = roots[key];
            }
            return key;
        }
    }
    

Log in to reply
 

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