In this post, we are going to solve the 695. Max Area of Island problem of Leetcode. This problem 695. Max Area of Island is a Leetcode medium level problem. Let’s see the code, 695. Max Area of Island – Leetcode Solution.

Problem

You are given an m x n binary matrix grid. An island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1 :

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2 :

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1.

Now, let’s see the code of 695. Max Area of Island – Leetcode Solution.

Max Area of Island – Leetcode Solution

695. Max Area of Island – Solution in Java

class Solution {
    
    public int coverIsland(int[][] grid, int i, int j,int[][] visited){
            
        if(i<0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return 0;
        
        if(visited[i][j] == 1)return 0;
        
        visited[i][j] = 1;
        
          return( 1 + coverIsland(grid,i,j-1,visited)+
                    coverIsland(grid,i-1,j,visited)+
                    coverIsland(grid,i,j+1,visited)+
                    coverIsland(grid,i+1,j,visited) 
                 );

    }
    
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        int[][] visited = new int[grid.length][grid[0].length];
        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] == 0)
                    maxArea = Math.max(maxArea,coverIsland(grid,i,j,visited));
            }
        }
        
        return maxArea;
    }
}

695. Max Area of Island – Solution in C++

class Solution {
public:
    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;
    }
};

695. Max Area of Island – Solution in Python

def dfs(i,j,grid):
    
    if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[i]) or grid[i][j] == 0:
        return 0
    
    grid[i][j] = 0
    
    up = dfs(i,j+1,grid)
    down = dfs(i,j-1,grid)
    left = dfs(i-1,j,grid)
    right = dfs(i+1,j,grid)
    
    return up + down + left + right + 1

class Solution(object):
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        count = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                
                if grid[i][j] == 1:
                    count = max(dfs(i,j,grid), count)
                    
        return count

Note: This problem 695. Max Area of Island is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.