Thinking process

do a bfs or dfs

Mistakes

don't need to use a visited matrix, just change the grid in-place

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

        int n = grid.length;
        int m = grid[0].length;

        int result = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == '1') {
                    result++;
                    bfsHelper(grid, i, j);
                }
            }
        }

        return result;
    }

    private void bfsHelper(char[][] grid, int x, int y) {
        Queue<Integer> queue = new LinkedList<>();//positions need to be visited
        int n = grid.length, m = grid[0].length;

        queue.offer(x * m + y);//start from here

        // int[] x = {-1, 1, 0, 0};//up down left right
        // int[] y = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int code = queue.poll();
            // int posX = pos / m;
            // int posY = pos % m;

            // grid[posX][posY] = '0';

            int i = code / m;  
            int j = code % m;  
            if (i>0 && grid[i-1][j] == '1') {  
                queue.offer((i-1)*m+j);  
                grid[i-1][j] = '0';  
            }  
            if (i<n-1 && grid[i+1][j] == '1') {  
                queue.offer((i+1)*m+j);  
                grid[i+1][j] = '0';  
            }  
            if (j>0 && grid[i][j-1] == '1') {  
                queue.offer(i*m+j-1);  
                grid[i][j-1] = '0';  
            }  
            if (j<m-1 && grid[i][j+1] == '1') {  
                queue.offer(i*m+j+1);  
                grid[i][j+1] = '0';  
            }

        }
    }
}

Number of Islands II - Union and Find

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class UnionFind { 

    public int count = 0; 
    public int[] father; 

    private int find(int x) { 
        if (father[x] == x) return x; 

        father[x] = find(father[x]); 
        return father[x]; 
    } 

    public UnionFind(int size, int total){ 
        father = new int[size]; 
        this.count = total; 

        for (int i = 0; i < size; i++) { 
            father[i] = i; 
        } 
    } 

    //connect two cells 
    public void connect(int a, int b){ 
        int root_a = find(a); 
        int root_b = find(b); 

        if (root_a != root_b) { 
            father[root_a] = root_b; 
            count--;//union decrease number of islands 
        } 
    } 

    //return how many connected islands 
    public int query(){ 
        return count; 
    } 

    public void addCount(){
        this.count++;
    }
} 

public class Solution {
    /**
     * @param n an integer
     * @param m an integer
     * @param operators an array of point
     * @return an integer array
     */
    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        // Write your code here

        List<Integer> res = new ArrayList<>();
        if(operators == null) {
            return res;
        }

        UnionFind uf = new UnionFind(n * m, 0);
        boolean[][] grid = new boolean[n][m];

        //loop through each operator
        for (int i = 0; i < operators.length; i++) {
            int x = operators[i].x;
            int y = operators[i].y;
            // if (grid[x][y]) continue;
            grid[x][y] = true;
            uf.addCount();
                // System.out.println(uf.query());
                //up 
                if (x > 0 && grid[x - 1][y]) { 
                    uf.connect(x * m + y, (x - 1) * m + y); 
                } 

                //down 
                if (x < n - 1 && grid[x + 1][y]) { 
                    uf.connect(x * m + y, (x + 1) * m + y); 
                } 

                //left 
                if (y > 0 && grid[x][y - 1]) { 
                    uf.connect(x * m + y, x * m + y - 1); 
                } 

                //right 
                if (y < m - 1 && grid[x][y + 1]) { 
                    uf.connect(x * m + y, x * m + y + 1); 
                } 

                res.add(uf.query());
        }

        return res;
    }
}