Max Area of Island

We want to know the area of each connected shape in the grid, then take the maximum of these.

If we are on a land square and explore every square connected to it 4-directionally (and recursively squares connected to those squares, and so on), then the total number of squares explored will be the area of that connected shape.

To ensure we don't count squares in a shape more than once, we can use a variable to keep track of squares we haven't visited before, or we can just change the grid map. It will also prevent us from counting the same shape more than once.

Time Complexity: O(R*C)O(R∗C), where RR is the number of rows in the given grid, and CC is the number of columns. We visit every square once.

Solution: Using DFS

The first version of DFS we check all conditions at thebeginning. Usually in a depth first search, we use a boolean array to mark the visited nodes. But in this problem, we can easily modify the input grid to 0.

int maxAreaOfIsland(vector<vector<int>>& grid) {
    int maxArea = 0;
    for(int i = 0; i < grid.size(); i++){
        for(int j = 0; j < grid[0].size(); j++){
            maxArea = max(maxArea, areaOfIsland(grid, i, j));
        }
    }
    return maxArea;
}

int areaOfIsland(vector<vector<int>>& grid, int i, int j) {
    if(i < 0 || i >= grid.size()) return 0;
    if(j < 0 || j >= grid[0].size()) return 0;

    if(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;
}

Solution: Using DFS

    int dfs(vector<vector<int>> &grid, int i, int j) {
        if (grid[i][j] == 0) return 0;

        grid[i][j] = 0;        
        int area = 1;
        if (i > 0) area += dfs(grid, i-1, j);
        if (i < grid.size()-1) area += dfs(grid, i+1, j);
        if (j > 0) area += dfs(grid, i, j-1);
        if (j < grid.front().size()-1) area += dfs(grid, i, j+1);

        return area;
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {   
        if (grid.empty() || grid.front().empty()) return 0;

        int maxArea = 0;
        for (int i=0; i<grid.size(); i++) {
            for (int j=0; j<grid.front().size(); j++) {
                if (grid[i][j] == 0) continue;
                maxArea = max(maxArea, dfs(grid, i, j));
            }
        }
        return maxArea;
    }