FastPrepFastPrep
Problem Brief

Find Largest House Area

OA

The city authorities conduct a study of the houses in a residential area for a city planning scheme. The area is depicted in an aerial view and divided into an N x M grid. If a grid cell contains some part of a house roof, then it is assigned the value 1; otherwise, the cell represents a vacant plot and is assigned the value 0. Clusters of adjacent grid cells with value 1 represent a single house. Diagonally placed grids with value 1 do not represent a single house. The area of a house is the number of 1's that it spans.

Write an algorithm to find the area of the largest house.

Input

The first line of the input consists of two space-separated integers - rows and cols representing the number of rows (N) and the number of columns in the grid (M), respectively. The next N lines consist of M space-separated integers representing the grid.

Output

Print an integer representing the area of the largest house.

Constraints

The elements of the grid consist of 0s and 1s only.

1Example 1

Input
grid = [[0, 0, 0, 0, 0], [0, 1, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 1, 0], [0, 0, 1, 0, 0]]
Output
3
Explanation
The area of the biggest house is 3. So, the output is 3.
public int findLargestHouseArea(int[][] grid) {
  // write your code here
}
Input

grid

[[0, 0, 0, 0, 0], [0, 1, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 1, 0], [0, 0, 1, 0, 0]]

Output

3

Sign in to submit your solution.