1

Largest Island

Difficulty: MEDIUM
Avg. time to solve
15 min
Success Rate
90%

Problem Statement
Suggest Edit

You have been given a non-empty grid consisting of only 0s and 1s. You have to find the maximum area of an island in the given grid.

An island is a group of 1s (representing land) connected horizontally, vertically or diagonally. You can assume that all four edges of the grid are surrounded by 0s (representing water).

Note:
If there is no island present in the grid, then the maximum area is 0.
Input Format:
The first line contains an integer 'T' denoting the number of test cases. 

The first input line of each test case contains two space-separated integers ‘N’ and ‘M’ representing the number of rows and columns of the grid, respectively.

The next 'N' lines represent the rows of the grid. Every row contains 'M' single space-separated integers.
Output Format:
For each test case, return the maximum area of the island in the grid.
Note:
You are not required to print the output, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 50
1 <= M <= 50
0 <= GRID[i][j] <= 1

Where 'GRID[i][j]' denotes the grid element.

Time limit: 1 sec
Sample Input 1:
2
4 5
0 0 1 1 0
1 0 1 1 0
0 1 0 0 0 
0 0 0 0 1
1 3
1 1 1
Sample Output 1:
6
3
Explanation of Sample Output 1:
In test case 1, as can be seen from the grid, there are two islands, one with area 1 and the other as 6. So the largest island is 6.

In test case 2, as can be seen from the grid, there is only one island in the grid with area 3. So the island with the largest area is 3.
Sample Input 2:
2
1 5
0 0 0 0 0
4 4
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
Sample Output 2:
0
8
Explanation of Sample Output 2:
In test case 1, as can be seen from the grid, there is no island present and thus largest island area will be zero (0).

In test case 2, as can be seen from the grid, each of the the eight land are connected with each other. So the island with the largest area is 8.
Reset Code
Full screen
copy-code
Console