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 on the island.

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

Test Cases

Example 1:

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

Solution

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int mx = 0;
        int count[1] = {0};
        for(int i=0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if (grid[i][j] == 1) {
                    count[0] = 0;
                    dfs(grid, n, m, i, j, count);
                    mx = max(count[0], mx);
                }
            }
        }
        return mx;
    }

    void dfs(vector<vector<int>> &grid, int n, int m, int x, int y, int* count) {
        count[0]++;
        grid[x][y] = 2;
        int dir[5] = {-1,0,1,0,-1};
        for(int i=0; i<4; i++) {
            int nx = x+dir[i], ny = y+dir[i+1];
            if(nx>=0 && ny>=0 && nx<n && ny <m && grid[nx][ny] == 1) {
                dfs(grid,n,m,nx,ny,count);
            }
        }
    }
};
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int max = 0;
        int[] count = new int[]{0};
        for(int i=0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if (grid[i][j] == 1) {
                    count[0] = 0;
                    dfs(grid, n, m, i, j, count);
                    max = Math.max(count[0], max);
                }
            }
        }
        return max;
    }

    private void dfs(int[][] grid, int n, int m, int x, int y, int[] count) {
        count[0]++;
        grid[x][y] = 2;
        int[] dir = new int[]{-1,0,1,0,-1};
        for(int i=0; i<4; i++) {
            int nx = x+dir[i], ny = y+dir[i+1];
            if(nx>=0 && ny>=0 && nx<n && ny <m && grid[nx][ny] == 1) {
                dfs(grid,n,m,nx,ny,count);
            }
        }
    }
}
Time Complexity: O(nm)
Space Complexity: O(1)