200. Number of Islands

/**
 * DFS Solution
 *
 * Time Complexity: O(M * N). Visiting all cells of the grid twice.
 *
 * Space Complexity: O(M * N). In worst case if all the cells of the grid are
 * '1', then the recursion stack will be M*N. Also visited array will take M*N
 * space.
 *
 * M = Number of rows in the grid. N = Number of columns in the grid.
 */
class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        if (grid.length == 1 && grid[0].length == 1) {
            if (grid[0][0] == '1') {
                return 1;
            } else {
                return 0;
            }
        }

        int count = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfsHelper(grid, i, j, visited);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfsHelper(char[][] grid, int i, int j, boolean[][] visited) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1' || visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        dfsHelper(grid, i + 1, j, visited);
        dfsHelper(grid, i - 1, j, visited);
        dfsHelper(grid, i, j + 1, visited);
        dfsHelper(grid, i, j - 1, visited);
    }
}

/**
 * BFS Solution
 *
 * Time Complexity: O(M * N). Visiting all cells of the grid twice.
 *
 * Space Complexity: O(M * N). Visited array will take M*N space
 *
 * If allowed to modify the grids input array, the space complexity will reduce
 * to O(M + N) or O(min(m,n)). Max size taken by the queue is size of the
 * diagonal of the array.
 *
 * M = Number of rows in the grid. N = Number of columns in the grid.
 */
class Solution {
    private static final int[][] dirs = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    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;
        if (rows == 1 && cols == 1) {
            if (grid[0][0] == '1') {
                return 1;
            } else {
                return 0;
            }
        }

        int count = 0;
        boolean[][] visited = new boolean[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] != '1' || visited[i][j]) {
                    continue;
                }

                count++;

                Queue<int[]> queue = new LinkedList();
                queue.offer(new int[] { i, j });
                visited[i][j] = true;

                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    for (int[] dir : dirs) {
                        int x = cell[0] + dir[0];
                        int y = cell[1] + dir[1];
                        if (x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] != '1' || visited[x][y]) {
                            continue;
                        }
                        queue.offer(new int[] { x, y });
                        visited[x][y] = true;
                    }
                }
            }
        }
        return count;
    }
}