695. Max Area of Island

/**
 * DFS Recursive Solution.
 *
 * Time Complexity: O(M * N) - All cells in the grids ar visited twice.
 *
 * Space Complexity: O(M * N) - This is for recursion stack and visited boolean
 * array
 *
 * M = Number of rows in the grid. N = Number of columns in the grid.
 */
class Solution {
    public int maxAreaOfIsland(int[][] 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;
            }
        }

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

        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]) {
                    int area = dfsHelper(grid, i, j, visited);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }

        return maxArea;
    }

    private int dfsHelper(int[][] 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 0;
        }
        visited[i][j] = true;
        return 1 + dfsHelper(grid, i + 1, j, visited) + dfsHelper(grid, i - 1, j, visited)
                + dfsHelper(grid, i, j + 1, visited) + dfsHelper(grid, i, j - 1, visited);
    }
}

/**
 * DFS Iterative Solution.
 *
 * Time Complexity: O(M * N) - All cells in the grids ar visited twice.
 *
 * Space Complexity: O(M * N) - Visited boolean array. Max size taken by the
 * stack is O(min(M,N)).
 *
 * M = Number of rows in the grid. N = Number of columns in the grid.
 */
class Solution {
    public int maxAreaOfIsland(int[][] 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 maxArea = 0;
        boolean[][] visited = new boolean[rows][cols];
        int[][] dirs = new int[][] { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

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

                Stack<int[]> stack = new Stack();
                stack.push(new int[] { i, j });
                visited[i][j] = true;
                int area = 1;
                while (!stack.isEmpty()) {
                    int[] cell = stack.pop();
                    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;
                        }
                        visited[x][y] = true;
                        area++;
                        stack.push(new int[] { x, y });
                    }
                }

                maxArea = Math.max(maxArea, area);
            }
        }

        return maxArea;
    }
}