DFS Application | Graph Problems | Max Area of Island

Introduction:

In this tutorial, we are going to implement DFS  to solve another important problem. this is a good question for interview point of view.

Problem Statement: Leetcode

Input:

[[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

Solution:
So basically we are going to use DFS to solve this problem, and we will use a 2D 
vector to track the already visited element.
let's see the code:

Full Code:

int helper(vector<vector<int>>& grid,int x, int y, vector<vector<int>>&visited){
        if(x<0 || x>=grid.size() || y<0 || y>=grid[x].size())
            return 0;
        if(grid[x][y]==0){
            return 0;
        }
        if(visited[x][y]==1){
            return 0;
        }
        visited[x][y]=1;
       // cout<<x<<" "<<y<<endl;
        int l=helper(grid,x-1,y,visited);
        int r=helper(grid,x+1,y,visited);
        int t=helper(grid,x,y-1,visited);
        int b=helper(grid,x,y+1,visited);
        return 1+l+r+t+b;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int maxarea=0;
        vector<vector<int>>visited(grid.size(),vector<int>(grid[0].size(),0));
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j]==1 && visited[i][j]==0){
                    cout<<i<<" "<<j<<endl;
                    int area=helper(grid,i,j,visited);
                    if(area>maxarea){
                        maxarea=area;
                    }
                }
                else{
                    continue;
                }
            }
        }
        return maxarea;
    }