Show problems as
Classic problem #695MediumArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix

Max Area of Island

Real-world version: Widest Moss Patch
Tracked in this browser only
Read Max Area of Island on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A courtyard is paved with square slabs laid out as grid. Entry grid[r][c] is 1 when that slab is mossy and 0 when it is clean.

A patch is a group of mossy slabs that you can walk between by stepping from one slab to a mossy slab sharing an edge with it, so slabs that only touch at a corner belong to different patches. The size of a patch is how many slabs it holds.

Return the size of the largest patch in the courtyard, or 0 when no slab is mossy.

Examples

Example 1

Input
grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1],[0,0,1,0]]
Output
4

The three slabs in the top-left corner form one patch of size 3. The slabs at (1,3), (2,2), (2,3) and (3,2) share edges and form a patch of size 4, which is the largest.

Example 2

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

The two mossy slabs meet only at a corner, so each is a patch of size 1 on its own.

Example 3

Input
grid = [[0,0,0],[0,0,0]]
Output
0

No slab is mossy, so there is no patch at all.

Constraints

  • m == grid.length
  • n == grid[r].length
  • 1 <= m, n <= 50
  • grid[r][c] is 0 or 1.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_area_of_island(grid: list[list[int]]) -> int:
Java
public int maxAreaOfIsland(int[][] grid)

More on the same topics