Command Palette

Search for a command to run...

Hectal
Problem 22.3 · Depth-First SearchMedium

Max Area of Island

PatternGraph DFS and Flood FillMatrix Traversal

What it teaches: A DFS that returns a value: the size of the region it explored.

Practise it on judges as “Max Area of Island”.

The problem

Given a grid of 0s and 1s, return the area (cell count) of the largest island, or 0 if there is none.

Example 1

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

Constraints

  • 1 ≤ rows, cols ≤ 50

Pattern clues in the wording

  • → Largest connected region

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
grid = [[0,0,1,0],[0,1,1,1],[0,0,1,0]]
5
2
grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
4
3
grid = [[0,0,0,0,0,0,0,0]]
0

From slow to fast

Approaches

1. DFS returning area · O(rows × cols)
1

DFS returning area

Time O(rows × cols) Space O(rows × cols)

DFS sinks the island and returns 1 + the sum of the neighbours' results.

Approach 1
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int best = 0;
        for (int r = 0; r < grid.length; r++)
            for (int c = 0; c < grid[0].length; c++)
                best = Math.max(best, area(grid, r, c));
        return best;
    }

    private int area(int[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] == 0) return 0;
        g[r][c] = 0;
        return 1 + area(g, r + 1, c) + area(g, r - 1, c) + area(g, r, c + 1) + area(g, r, c - 1);
    }
}

Verdict: One pass.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No land
  • Whole grid is land

Mistakes people make

  • Forgetting to sink cells (they get counted many times).

Interview

Follow-up questions

What if you may flip one 0 to 1 to make the largest island (Making A Large Island)?