[Java/C++] Straightforward dfs solution


  • 23

    The idea is to count the area of each island using dfs. During the dfs, we set the value of each point in the island to 0. The time complexity is O(mn).

    Java version:

        public int maxAreaOfIsland(int[][] grid) {
            int max_area = 0;
            for(int i = 0; i < grid.length; i++)
                for(int j = 0; j < grid[0].length; j++)
                    if(grid[i][j] == 1)max_area = Math.max(max_area, AreaOfIsland(grid, i, j));
            return max_area;
        }
        
        public int AreaOfIsland(int[][] grid, int i, int j){
            if( i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1){
                grid[i][j] = 0;
                return 1 + AreaOfIsland(grid, i+1, j) + AreaOfIsland(grid, i-1, j) + AreaOfIsland(grid, i, j-1) + AreaOfIsland(grid, i, j+1);
            }
            return 0;
        }
    

    C++ version:

        int maxAreaOfIsland(vector<vector<int>>& grid) {
            int max_area = 0;
            for(int i = 0; i < grid.size(); i++)
                for(int j = 0; j < grid[0].size(); j++)
                    if(grid[i][j] == 1)max_area = max(max_area, AreaOfIsland(grid, i, j));
            return max_area;
        }
        
        int AreaOfIsland(vector<vector<int>>& grid, int i, int j){
            if( i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size() && grid[i][j] == 1){
                grid[i][j] = 0;
                return 1 + AreaOfIsland(grid, i+1, j) + AreaOfIsland(grid, i-1, j) + AreaOfIsland(grid, i, j-1) + AreaOfIsland(grid, i, j+1);
            }
            return 0;
        }
    

  • 0

    Hope your advice!


  • 0

    Had same idea but set visited part of island to '-1'so it's easy to debug:

    class Solution {
        int max = 0, maxNow = 0;
        public int maxAreaOfIsland(int[][] grid) {
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1){
                        maxNow = 0;
                        dfs(i, j, grid);}
                }
            }
            return max;
        }
        
        private void dfs(int i, int j, int[][]grid) {
            if (i < 0 || j < 0 || 
                i >= grid.length || j >= grid[0].length ||
                grid[i][j] != 1) return;
            grid[i][j] = -1; // marking part of island visited not to check it next time
            maxNow++;
            
            dfs(i - 1, j, grid);
            dfs(i + 1, j, grid);
            dfs(i, j + 1, grid);
            dfs(i, j - 1, grid);
    
            max = Math.max(max, maxNow);
        }
    }	
    

  • 0
    F

    Worst-case recursion depth will be O(mn), where m is the width of the grid and n is the height, correct?

    So space complexity will be O(mn)?


  • 0

    @FlorenceMachine Yes, the worst space complexity could be O(mn).


  • 0
    F

    Same idea

    class Solution {
        public int maxAreaOfIsland(int[][] grid) {
            int max = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        max = Math.max(max, helper(grid, i, j));
                    }
                }
            }
            return max;
        }
        public int helper(int[][] grid, int i, int j) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
                return 0;
            }
            grid[i][j] = 0;
            return 1 + helper(grid, i - 1, j) + helper(grid, i + 1, j) + helper(grid, i, j - 1) + helper(grid, i, j + 1);
        }
    }
    

  • 0
    This post is deleted!

  • 0
    B

    We may use an extra visited[][] so not to modify the input grid.

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

  • 0
    Z

    @Vincent-Cai Beautiful solution!


Log in to reply
 

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