Skip to content

0695. Max Area of Island

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

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

Example 1:

img

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

Constraints:

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

Analysis

We can use DFS to solve this problem. Once we see a location marked as 1, we will run a DFS to search all the surrounded area whose value is also 1, and keep a count and return it. Finally, we just need to compare all the independent areas and return the maximum. One thing to be mindful is that we need to keep track of all the counted area, we can either 1. rewrite another value to the 1's location if we can alter the orginal grid, 2. use a set or a map to keep a record of the the visited address.

  • Time: O(n^2)
  • Space: O(n^2)

Code

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int res = 0;
        for (int x = 0; x < grid.size(); ++x)
            for (int y = 0; y < grid[0].size(); ++y)
                if (grid[x][y] == 1)
                    res = max(res, dfs(x, y, grid));
        return res;
    }
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int dfs(int x, int y, vector<vector<int>>& g) {
        if (x < 0 || x >= g.size() || y >= g[0].size() || g[x][y] != 1)
          /* !visited.count({x, y}) if not allowed to write the original grid */
            return 0;
        g[x][y] = 2; // rewrite it with a special value
        int res = 1;
        for (auto d : dir) {
          /* visited.insert({x + d[0], y + d[1]}); */
            res += dfs(x + d[0], y + d[1], g);
        }
        return res;
    }
};
Last update: April 1, 2022