All problems

Max Area of Island

Medium · graph traversal

You are given a map as a rectangular grid of integers, grid. A cell holding 1 is land and a cell holding 0 is water.

An island is a group of land cells joined through shared edges: two land cells belong to the same island if you can walk from one to the other by moving up, down, left or right over land only. Cells that touch only at a corner are not joined. The area of an island is the number of land cells in it.

Return the area of the largest island in grid. If the grid has no land at all, return 0.

Examples

Example 1

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

Output: 4

The top-left island has 3 cells and the bottom-right one has 4, so the answer is 4.

Example 2

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

Output: 1

Every land cell only touches the others at corners, so each is an island of area 1.

Example 3

Input: grid = [[0, 0], [0, 0]]

Output: 0

There is no land.

Constraints

• 1 <= rows, cols <= 30
• Every cell is either 0 (water) or 1 (land).
• All rows have the same length.