Tuesday, August 18, 2015

Leetcode: Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
Understand the problem:
This problem is an alternative view of connected components in a undirected graph. It could be easily solved by using either DFS or BFS. 

DFS Solution (Java):
public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        
        boolean[][] visited = new boolean[rows][cols];
        int result = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    result++;
                    numIslandsHelper(grid, visited, i, j, rows, cols);
                }
            }
        }
        
        return result;
    }
    
    private void numIslandsHelper(char[][] grid, boolean[][] visited, int i, int j, int numRows, int numCols) {
        if (i < 0 || i >= numRows) {
            return;
        }
        
        if (j < 0 || j >= numCols) {
            return;
        }
        
        if (visited[i][j]) {
            return;
        }
        
        // If water
        if (grid[i][j] == '0') {
            return;
        }
        
        // Mark the visted[i][j] = true
        visited[i][j] = true;
        
        // Go up, down, left and right
        numIslandsHelper(grid, visited, i - 1, j, numRows, numCols);
        numIslandsHelper(grid, visited, i + 1, j, numRows, numCols);
        numIslandsHelper(grid, visited, i, j - 1, numRows, numCols);
        numIslandsHelper(grid, visited, i, j + 1, numRows, numCols);
    }
}

A BFS Solution:
public class Solution {
    private Queue<Integer> queue = new LinkedList();
    
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        
        int result = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    result++;
                    numIslandsHelper(grid, visited, i, j, rows, cols);
                }
            }
        }
        return result;
    }
    
    private void numIslandsHelper(char[][] grid, boolean[][] visited, int i, int j, int numRows, int numCols) {
        fill(grid, visited, i, j, numRows, numCols);
        
        while (!queue.isEmpty()) {      
            int cord = queue.poll();
            int x = cord / numCols;
            int y = cord % numCols;
    
            fill(grid, visited, x - 1, y, numRows, numCols);
            fill(grid, visited, x + 1, y, numRows, numCols);
            fill(grid, visited, x, y - 1, numRows, numCols);
            fill(grid, visited, x, y + 1, numRows, numCols);
        }
    }
    
    private void fill(char[][] grid, boolean[][] visited, int i, int j, int numRows, int numCols) {
        if (i < 0 || i >= numRows || j < 0 || j >= numCols) {
            return;
        }
        
        if (visited[i][j] || grid[i][j] == '0') {
            return;
        }
        
        visited[i][j] = true;
        
        queue.offer(i * numCols + j);
    }
}

Update on 1/25/16:
Union-find Solution:
public class Solution {
    private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        int[] parents = new int[m * n];
        int count = 0;
        
        // Step 1: initialize each node, for each's parent is itself
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int id = i * n + j;
                parents[id] = id;
            }
        }
        
        // step 2: iterate each node, and connect the neighbors
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') {
                    continue;
                }
                
                for (int[] row : dir) {
                    int x = i + row[0];
                    int y = j + row[1];
                    if (isValid(grid, x, y)) {
                        int p = i * n + j;
                        int q = x * n + y;
                        connect(parents, p, q);
                    }
                }
            }
        }
        
        // step 3: count the number of cc
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int id = i * n + j;
                if (grid[i][j] == '1' && parents[id] == id) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private boolean isValid(char[][] grid, int x, int y) {
        int m = grid.length;
        int n = grid[0].length;
        
        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1';
    }
    
    private void connect(int[] parents, int p, int q) {
        int pRoot = find(parents, p);
        int qRoot = find(parents, q);
        
        if (pRoot == qRoot) {
            return;
        }
        
        parents[pRoot] = qRoot;
    }
    
    private int find(int[] parents, int id) {
        while (parents[id] != id) {
            id = parents[id];
        }
        
        return id;
    }
}

Updata on 4/21/19:
public class Solution {
    /**
     * @param grid: a boolean 2D matrix
     * @return: an integer
     */
    public int numIslands(boolean[][] grid) {
        // write your code here
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int nRows = grid.length;
        int nCols = grid[0].length;
        
        int[] parents = new int[nRows * nCols];
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }
        
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (grid[i][j]) {
                    union(grid, i, j, parents);
                }
            }
        }
        
        int numIslands = 0;
        
        for (int i = 0; i < parents.length; i++) {
            int nx = i / nCols;
            int ny = i % nCols;
            
            if (grid[nx][ny] && parents[i] == i) {
                numIslands++;
            }
        }
        
        return numIslands;
    }
    
    private void union(boolean[][] grid, int x, int y, int[] parents) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        int nRows = grid.length;
        int nCols = grid[0].length;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dirs[i][0];
            int ny = y + dirs[i][1];
            
            if (nx >= 0 && nx < nRows && ny >= 0 && ny < nCols && grid[nx][ny]) {
                int myParrent = find(parents, x * nCols + y);
                int neighborParrent = find(parents, nx * nCols + ny);
                
                if (myParrent != neighborParrent) {
                    parents[myParrent] = neighborParrent;
                }
            }
        }
    }
    
    private int find(int[] parents, int x) {
        int root = x;
        while (parents[root] != root) {
            root = parents[root];
        }
        
        // path compression
        //
        while (x != root) {
            int temp = parents[x];
            parents[x] = root;
            x = temp;
        }
        
        return root;
    }
}

No comments:

Post a Comment