Max Area of Island

Problem

You are given a matrix grid where grid[i] is either a 0 (representing water) or 1 (representing land).

An island is defined as a group of 1’s connected horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

The area of an island is defined as the number of cells within the island.

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

Examples

Example 1:

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

Output: 6

Explanation: 1’s cannot be connected diagonally, so the maximum area of the island is 6.

Constraints

• 1 <= grid.length, grid[i].length <= 50

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.

Solution

Visit each cell as start of an island. Run DFS while counting number of visited cells, and mark each as visited.

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        const int ROWS = grid.size();
        const int COLS = grid[0].size();
        int max_area = 0;
 
        std::function<int(int,int)> dfs;
        dfs = [&](int r, int c) -> int {
            // Out of bounds
            if (r < 0 || c < 0 || r >= ROWS || c >= COLS) { return 0; }
            // Non-island cell, skip
            if (grid[r][c] == 0) { return 0; }
            // Island cell, count, mark as visited, and check neighbors
            int area = 1;
            grid[r][c] = 0;
            area += dfs(r - 1, c);
            area += dfs(r + 1, c);
            area += dfs(r, c - 1);
            area += dfs(r, c + 1);
            return area;
        };
 
        // Check if each cell is island
        for (int i = 0; i < ROWS; ++i) {
            for (int j = 0; j < COLS; ++j) {
                int area = dfs(i, j);
                max_area = std::max(max_area, area);
            }
        }
        return max_area;
    }
};