DFS O(n ^ 2)


  • 0
    J
    class Solution {
        public int maxAreaOfIsland(int[][] grid) {
            int max = 0;
            if (grid == null || grid.length == 0 || grid[0].length == 0) return max;
            boolean[][] visited = new boolean[grid.length][grid[0].length];
            
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    if (grid[i][j] == 1 && !visited[i][j]) {
                        max = Math.max(max, dfs(grid, i, j, visited));
                    }
                }
            }
            
            return max;
        }
        
        private int dfs(int[][] grid, int i, int j, boolean[][] visited) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == 0 || visited[i][j]) return 0;
            
            visited[i][j] = true;
            
            int sum = 1;
            
            sum += dfs(grid, i + 1, j, visited);
            sum += dfs(grid, i - 1, j, visited);
            sum += dfs(grid, i, j + 1, visited);
            sum += dfs(grid, i, j - 1, visited);
            
            return sum;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.