Max Area of Island

Easy~20 min

You are given an m x n binary grid where 1 represents land and 0 represents water.

An island is a group of 1s 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 value 1 in the island.

Return the maximum area of an island in the grid. If there is no island, return 0.

Examples

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 largest island (bottom right area) has 6 connected land cells.

Example 2

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

Output: 0

Explanation: There are no islands, so the answer is 0.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is 0 or 1
Expected time complexity: O(m × n)

Code

Ctrl+EnterRun|Ctrl+⇧+EnterSubmit

Output

Run your code to see results

Use Cmd+Enter to run