Largest Forest Patch

Medium

A nature reserve map is a rectangular grid plan with m rows and n columns. A cell holds 1 if it is covered by forest and 0 if it is open field. A forest patch is a group of forest cells linked through their top, bottom, left or right neighbours; touching diagonally does not join patches. There is no forest beyond the edges of the map. The size of a patch is the number of cells in it. Return the size of the largest patch, or 0 if the map has no forest.

Example 1

plan=[[1, 1, 0, 0], [0, 1, 0, 1], [1, 0, 0, 1], [1, 0, 1, 1]] → 4

There are three patches: three cells in the top-left corner, two cells at the bottom left and four cells on the right. The largest has 4 cells.

Example 2

plan=[[1, 0, 1], [0, 1, 0], [1, 0, 1]] → 1

The cells touch only at the corners, so each one is a separate patch of size 1.

Example 3

plan=[[0, 0], [0, 0]] → 0

There is no forest at all, so the answer is 0.

Constraints

1 ≤ m, n ≤ 50
All rows have the same number of cells
Every cell is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Array Matrix

Similar problems

Drain the Landlocked Ponds Medium Land Regions on a Map Medium A Board Cut by Slashes Medium Landlocked Land Cells Medium Route With the Highest Bottleneck Medium

Input

plan=[[1, 1, 0, 0], [0, 1, 0, 1], [1, 0, 0, 1], [1, 0, 1, 1]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 62 tests on the server, hidden ones included.