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

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        directions = [[1,0],[-1,0],[0,1],[0,-1]]
        dq = collections.deque([])
        count = 0
        row, col = len(grid), len(grid[0])
        
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1':
                    count += 1
                    grid[i][j] == '0'
                    dq.append([i,j])
                    while len(dq):
                        x,y = dq.popleft()
                        for dirc in directions:
                            new_x, new_y = x+dirc[0], y+dirc[1]
                            if new_x >= 0 and new_x < row and new_y >= 0 and new_y < col and grid[new_x][new_y] == '1':
                                grid[new_x][new_y] = '0'
                                dq.append([new_x, new_y])         
                    
        return count

• 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

class UnionFind(object):
    def __init__(self, grid):
        row, col = len(grid), len(grid[0])
        self.parent = ['w'] * (row * col)
        self.count = 0

        for r in range(row):
            for c in range(col):
                if grid[r][c] == '1':
                    self.parent[(col * r) + c] = -1
    
    def find(self, index):
        if self.parent[index] == 'w':
            return index
        
        if self.parent[index] > -1:
            self.parent[index] = self.find(self.parent[index])
            return self.parent[index]
        
        return index
    
    def union(self, vertexA, vertexB):
        aIndex = self.find(vertexA)
        bIndex = self.find(vertexB)

        if aIndex == bIndex or self.isWater(aIndex, bIndex):
            return
        
        if self.parent[aIndex] > self.parent[bIndex]:
            self.parent[bIndex] += self.parent[aIndex]
            self.parent[aIndex] = bIndex
        else:
            self.parent[aIndex] += self.parent[bIndex]
            self.parent[bIndex] = aIndex
    
    def isWater(self, aIndex, bIndex):
        return self.parent[aIndex] == 'w' or self.parent[bIndex] == 'w'
		
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        row, col = len(grid), len(grid[0])
        uf = UnionFind(grid)

        for r in range(row):
            for c in range(col):
                
                if grid[r][c] is '1':
                    parentIndex = (col * r) + c

                    # right
                    if c < col - 1:
                        right = parentIndex + 1
                        uf.union(parentIndex, right)
                    
                    # down
                    if r < row - 1:
                        down = (col * (r+1)) + c
                        uf.union(parentIndex, down)
        
        islands = 0
        for ele in uf.parent:
            if ele is not 'w' and ele < 0:
                islands +=1

        return islands