Largest Island
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

Question

Largest Island

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

Accepted Answer

DFS APPROACH

The problem boils down to finding the area of each connected component in the grid, then taking the maximum of them.

If we are on a land cell and explore every cell connected to it 8-directionally (and recursively cells connected to those cells, and so on), then the total number of cells with land explored will be the area of that component.

To ensure we don't count cell in the island more than once, we will mark 1(land) as 0 during the recursion call.

The steps are as follows:

We have a function ‘maxAreaOfIsland’ in which we are iterating over the whole grid. Whenever we encounter a 1(land), we will call the ‘dfsArea’ function.

The ‘dfsArea’ function works as follows:

If indices are out of bound or the value present at the current cell is 0, then return 0.
Else, Mark the cell as 0, so that we don’t count cells in an island more than once.
Call the ‘dfsArea’ function in 8-directions and return 1 + the combined area from eight directions.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), Where ‘N’ is the number of rows in the given grid, and 'M' is the number of columns.

Since all the elements of the grid can be in the recursion stack and thus the space complexity will be O(N * M).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), Where ‘N’ is the number of rows in the given grid, and 'M' is the number of columns.

Since we will be visiting every land cell of the grid and thus the time complexity will be O(N * M).

Accepted Answer

BFS APPROACH

We can also use the breadth-first search technique to explore an island's area.

The ‘bfsArea’ function works as follows:

We will create a queue of integers and put the indices of the current cell (land only) in it.
We will loop until the size of the queue becomes zero.
- We will pop the front element of the queue.
- Then, we push the indices of the 8-direction adjacent cells (only land) into the queue.
- To ensure we don’t push a cell again, we will mark the land cells as 0.

The largest area returned by ‘bfsArea’ will be our answer.

Space Complexity: O(1)Explanation:

O(N + M), where ‘N’ is the number of rows in the given grid, and 'M' is the number of columns.

Since in the worst case when the grid is filled with lands, the size of the queue can grow up to M + N. Thus the space complexity will be O(N + M).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), Where ‘N’ is the number of rows in the given grid, and 'M' is the number of columns.

Since we will be visiting every land cell of the grid and thus the time complexity will be O(N * M).

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:

Input Format:

Output Format:

Note:

Constraints:

Top Paxcom India Software Developer interview questions & answers

Popular interview questions of Software Developer