Number of Islands

• BFS

Java

class Coordinate {
    int x, y;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    public int numIslands(boolean[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        
        int n = grid.length;
        int m = grid[0].length;
        int islands = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) {
                    markByBFS(grid, i, j);
                    islands++;
                }
            }
        }
        
        return islands;
    }
    
    private void markByBFS(boolean[][] grid, int x, int y) {
        // magic numbers!
        int[] directionX = {0, 1, -1, 0};
        int[] directionY = {1, 0, 0, -1};
        
        Queue<Coordinate> queue = new LinkedList<>();
        
        queue.offer(new Coordinate(x, y));
        grid[x][y] = false;
        
        while (!queue.isEmpty()) {
            Coordinate coor = queue.poll();
            for (int i = 0; i < 4; i++) {
                Coordinate adj = new Coordinate(
                    coor.x + directionX[i],
                    coor.y + directionY[i]
                );
                if (!inBound(adj, grid)) {
                    continue;
                }
                if (grid[adj.x][adj.y]) {
                    grid[adj.x][adj.y] = false;
                    queue.offer(adj);
                }
            }
        }
    }
    
    private boolean inBound(Coordinate coor, boolean[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        
        return coor.x >= 0 && coor.x < n && coor.y >= 0 && coor.y < m;
    }
}

Python

• Union Find

Java

public class Solution {
    int[] father;
    /**
     * @param grid: a boolean 2D matrix
     * @return: an integer
     */
    public int numIslands(boolean[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int[] xBias = new int[] {0, 0, -1, 1};
        int[] yBias = new int[] {-1, 1, 0, 0};
        father = new int[grid.length * grid[0].length];
        Arrays.fill(father, -1);
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        father[0] = grid[0][0] ? 0 : -2;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            for (int i = 0; i < xBias.length; i++) {
                int newX = current[0] + xBias[i];
                int newY = current[1] + yBias[i];
                if (!isValid(grid, newX, newY)) {
                    continue;
                }
                int oneDPoint = convert2dTo1d(newX, newY, grid[0].length);
                if (father[oneDPoint] == -1) {
                    father[oneDPoint] = -2;
                    queue.offer(new int[] {newX, newY});
                }
                if (grid[newX][newY]) {
                    if (father[oneDPoint] < 0) {
                        father[oneDPoint] = oneDPoint;
                    }
                    if (grid[current[0]][current[1]]) {
                        connect(convert2dTo1d(current[0], current[1], grid[0].length), oneDPoint);
                    }
                }
            }
        }
        
        int result = 0;
        for (int i = 0; i < father.length; i++) {
            if (father[i] == i) {
                result++;
            }
        }
        return result;
    }
    
    private boolean isValid(boolean[][] grid, int newX, int newY) {
        return newX >= 0 && newY >= 0 && newX < grid.length && newY < grid[0].length;
    }
    
    private int convert2dTo1d(int x, int y, int colLength) {
        return x * colLength + y;
    }
    
    private void connect(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            father[rootA] = rootB;
        }
    }
    
    private int find(int x) {
        if (father[x] == x) {
            return x;
        }
        return father[x] = find(father[x]);
    }
}

Python