首页 > itarticle > algorithm notes: leetcode#695 max area of island

algorithm notes: leetcode#695 max area of island

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

class :
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        max_area = 0
        
        def dfs(i, j):
            if 0 <= i < m and 0 <= j < n and grid[i][j]:
                grid[i][j] = 0
                return 1 + dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)
            return 0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    max_area = max(max_area, dfs(i,j))
        return max_area

Java implementation

class  {
    private int[][] grid;
    
    private int dfs(int i, int j){
        int m = grid.length;
        int n = grid[0].length;
        if((0 <= i) && (i < m) && (0 <= j) && (j < n) && (grid[i][j]==1)){
            grid[i][j] = 0;
            return 1 + dfs(i-1,j) + dfs(i+1,j) + dfs(i,j-1) + dfs(i,j+1);
        }
        return 0;
        }
    
    public int maxAreaOfIsland(int[][] grid) {
        this.grid = grid;
        int m = grid.length;
        int n = grid[0].length;
        int maxArea = 0;
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(this.grid[i][j]==1){
                    int newArea = dfs(i, j);
                    maxArea = maxArea < newArea ? newArea : maxArea;
                }
            }
        }
        return maxArea;
    }
}

Time complexity

O(MN).

Space complexity

O(MN).

Link

695. Max Area of Island
(中文版) 算法笔记: 力扣#695 岛屿的最大面积