695

695. Max Area of Island (Medium)

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:

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.

Companies:
Google, Affirm, Amazon, Qualtrics, Facebook, Uber, DoorDash

Related Topics:
Array, Depth-First Search, Breadth-First Search, Union Find, Matrix

Similar Questions:

• Number of Islands (Medium)
• Island Perimeter (Easy)
• Largest Submatrix With Rearrangements (Medium)
• Detonate the Maximum Bombs (Medium)

Solution 1. DFS

// OJ: https://leetcode.com/problems/max-area-of-island/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), dirs[4][2] = {{0,1},{0,-1},{-1,0},{1,0}}, ans = 0;
        function<int(int, int)> dfs = [&](int i, int j) {
            A[i][j] = 0;
            int cnt = 1;
            for (auto &[dx, dy] : dirs) {
                int x = i + dx, y = j + dy;
                if (x < 0 || x >= M || y < 0 || y >= N || A[x][y] == 0) continue;
                cnt += dfs(x, y);
            }
            return cnt;
        };
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0) continue;
                ans = max(ans, dfs(i, j));
            }
        }
        return ans;
    }
};

Solution 2. BFS

// OJ: https://leetcode.com/problems/max-area-of-island/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(M + N)
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), dirs[4][2] = {{0,1},{0,-1},{-1,0},{1,0}}, ans = 0;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0) continue;
                queue<pair<int, int>> q{{{i, j}}};
                A[i][j] = 0;
                int cnt = 0;
                while (q.size()) {
                    auto [x, y] = q.front();
                    q.pop();
                    for (auto &[dx, dy] : dirs) {
                        int a = x + dx, b = y + dy;
                        if (a < 0 || a >= M || b < 0 || b >= N || A[a][b] == 0) continue;
                        A[a][b] = 0;
                        q.emplace(a, b);
                    }
                    ++cnt;
                }
                ans = max(ans, cnt);
            }
        }
        return ans;
    }
};

Solution 3. Union Find

// OJ: https://leetcode.com/problems/max-area-of-island/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class UnionFind {
    vector<int> id, size;
public:
    UnionFind(int N) : id(N), size(N, 1) {
        iota(begin(id), end(id), 0);
    }
    int find(int x) {
        return id[x] == x ? x : (id[x] = find(id[x]));
    }
    void connect(int x, int y) {
        int p = find(x), q = find(y);
        if (p == q) return;
        id[p] = q;
        size[q] += size[p];
    }
    int getSize(int x) { return size[x]; }
};
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), dirs[4][2] = {{0,1},{0,-1},{-1,0},{1,0}}, ans = 0;
        UnionFind uf(M * N);
        auto key = [&](int x, int y) { return x * N + y; };
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0) continue;
                for (auto &[dx, dy] : dirs) {
                    int a = i + dx, b = j + dy;
                    if (a < 0 || a >= M || b < 0 || b >= N || A[a][b] == 0) continue;
                    uf.connect(key(i, j), key(a, b));
                }
            }
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 1) ans = max(ans, uf.getSize(key(i, j)));
            }
        }
        return ans;
    }
};