Problem

You are given an m x n binary matrix grid. An island is a group of 1's connected in one of 4 directions, 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.

Source: https://leetcode.com/problems/max-area-of-island

Constraints

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

Asymptotic Complexity

• Time: O(n x m), note: the grid has 4 x n x m edges
• Space: no additional space required

Strategy

• For each cell in the grid, use a depth first search to determine the island's area. Stop recursing when a 0 is found, otherwise increment the current island's area and continue searching. After visiting a cell, set its value to 0 so it isn't revisited.

Special Cases

• If the DFS search result is a 1, the neighbor to the right must be 0, and can be skipped
• To reduce memory, store a pointer to the grid instead of including it in each DFS call

Implementation

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        _grid = &grid; //to reduce the DFS stack size
        auto maxArea = 0;
        for (auto y = 0; y < grid.size(); ++y) {
            for (auto x = 0; x < grid[0].size(); ++x) {
                const auto area = dfs(x, y);
                maxArea = max(maxArea, area);
                if (area == 1) {
                    ++x; //jump over the neighbor
                }
            }
        }

        return maxArea;
    }

private:
    vector<vector<int>>* _grid{nullptr};

    int dfs(int8_t x, int8_t y) {
        if (x < 0 || y < 0 || x >= (*_grid)[0].size() || y >= (*_grid).size() || (*_grid)[y][x] == 0) {
            return 0;
        }

        auto area = 1;
        (*_grid)[y][x] = 0;
        area += dfs(x, y - 1);//N
        area += dfs(x + 1, y);//E
        area += dfs(x, y + 1);//S
        area += dfs(x - 1, y);//W
        return area;        
    }
};