[Java/C++] Straightforward dfs solution


  • 11

    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!


  • 1

    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!

Log in to reply
 

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