Max Area of Island

Medium Graphs Matrix Graphs Original on LeetCode

Max Area of Island is a medium graphs problem solved with the matrix graphs pattern. The best approach, optimal (sink each island once), runs in O(m · n) time and O(m · n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (flood fill from every land cell) up.

Problem

You are given an m x n grid of 0s (water) and 1s (land). An island is a group of land cells joined horizontally or vertically; cells that only touch at a corner belong to different islands. Everything outside the grid is water.

The area of an island is the number of land cells in it. Return the largest area of any island in the grid, or 0 if the grid has no land.

Examples

Example 1

Input
grid = [[1,1,0,0,1],[0,1,0,1,1],[0,0,0,0,1],[1,0,1,0,0]]
Output
4
Why
The island on the right covers (0,4), (1,3), (1,4) and (2,4), which is 4 cells; the top-left island has only 3.

Example 2

Input
grid = [[0,0,0],[0,0,0]]
Output
0
Why
There is no land at all, so the largest area is 0.

Example 3

Input
grid = [[1,0,1],[0,1,0],[1,0,1]]
Output
1
Why
Cells that touch only at corners are separate islands, so every island has area 1.

Constraints

  • 1 <= m, n <= 50 where the grid has m rows and n columns.
  • Every cell is 0 (water) or 1 (land).
  • Land cells are connected only up, down, left and right.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (flood fill from every land cell)O((m · n)²)O(m · n)
Optimal (sink each island once)O(m · n)O(m · n)

1Brute force (flood fill from every land cell)

TimeO((m · n)²)Up to m · n starting cells, and each BFS can visit all m · n cells.
SpaceO(m · n)The visited matrix and the queue for one BFS.

Treat each land cell as a possible starting point. From each one, run a fresh BFS with a brand-new visited array and count how many cells it reaches. The largest count is the answer. Cells of the same island are explored again and again, which is what makes this slow.

  1. For every cell (i, j) that is land, create a fresh visited matrix.
  2. BFS from (i, j) over land neighbours, counting cells as they are dequeued.
  3. Keep the maximum count seen.
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, best = 0;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 1) continue;
                boolean[][] seen = new boolean[m][n];
                ArrayDeque<int[]> q = new ArrayDeque<>();
                q.add(new int[] { i, j });
                seen[i][j] = true;
                int area = 0;
                while (!q.isEmpty()) {
                    int[] c = q.poll();
                    area++;
                    for (int[] d : dirs) {
                        int r = c[0] + d[0], s = c[1] + d[1];
                        if (r >= 0 && r < m && s >= 0 && s < n && grid[r][s] == 1 && !seen[r][s]) {
                            seen[r][s] = true;
                            q.add(new int[] { r, s });
                        }
                    }
                }
                best = Math.max(best, area);
            }
        }
        return best;
    }
}

2Optimal (sink each island once)

TimeO(m · n)Each cell is pushed at most once and checks 4 neighbours.
SpaceO(m · n)The stack can hold most of the grid when one island fills it.

Scan the grid once. When you hit land, flood-fill its whole island with an explicit stack, turning every visited cell into water and counting it. Because sunk cells are water, no island is ever explored twice, so the total work is linear in the grid size.

  1. For each cell that is still land, set it to 0 and push it on a stack.
  2. Pop cells one by one, add 1 to the area, and push every land neighbour after setting it to 0.
  3. When the stack is empty, the island is fully counted; update the best area.
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, best = 0;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        ArrayDeque<int[]> st = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 1) continue;
                grid[i][j] = 0;
                st.push(new int[] { i, j });
                int area = 0;
                while (!st.isEmpty()) {
                    int[] c = st.pop();
                    area++;
                    for (int[] d : dirs) {
                        int r = c[0] + d[0], s = c[1] + d[1];
                        if (r >= 0 && r < m && s >= 0 && s < n && grid[r][s] == 1) {
                            grid[r][s] = 0;
                            st.push(new int[] { r, s });
                        }
                    }
                }
                best = Math.max(best, area);
            }
        }
        return best;
    }
}

Edge cases to test

  • No land anywhere (answer 0)
  • The whole grid is land (answer m · n)
  • Diagonal neighbours, which do not join islands
  • A single row or a single column

Hints

Hint 1

An island is a connected component of land cells. How would you visit every cell of one component?

Hint 2

Count the cells while you flood-fill the component, and mark each one so it is never counted twice.

Hint 3

Mark visited land by turning it into water; then one scan over the grid touches each cell a constant number of times.

FAQ

What is the best time complexity for Max Area of Island?

Optimal (sink each island once) runs in O(m · n) time and O(m · n) extra space. Each cell is pushed at most once and checks 4 neighbours.

Which pattern does Max Area of Island use?

It is a graphs problem that uses the matrix graphs pattern. Other problems with the same pattern: Flood Fill, Maximum Number of Points From Grid Queries, Contain Virus.

Is there a brute force solution for Max Area of Island?

Yes. Brute force (flood fill from every land cell) takes O((m · n)²) time and O(m · n) space. Treat each land cell as a possible starting point.

Which edge cases should I test for Max Area of Island?

No land anywhere (answer 0); The whole grid is land (answer m · n); Diagonal neighbours, which do not join islands; A single row or a single column.