Difficulty: Medium Link: Day1 : June LeetCode Challenge
You are given an
m x n binary matrix
grid. An island is a group of
1‘s (representing land) 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 a value
1 in the island.
Return the maximum area of an island in
grid. If there is no island, return
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 answer is not 11, because the island must be connected 4-directionally.
Input: grid = [[0,0,0,0,0,0,0,0]] Output: 0
m == grid.length
n == grid[i].length
1 <= m, n <= 50
We want to find out the maximum area in the grid. A cell would contribute to the area if it is a land (grid[i][j] = 1 )otherwise it is water. Whenever we come on the land, we can explore all the 4 directions to find the connected cells. The total area would be the sum of all such connected cells.
Depth First Search
This is the best technique to traverse any 2D grid if we want to maximise the extant of any quantity (number of continuous cells in this case). We can process the input grid using nested loops and recursively call the dfs whenever we are on the land. The dfs procedure would in-turn recursively check for all the 4 directions and return the total of land cells.
There are chances of infinite loop since we are blindly traversing all the 4 directions and we would revisit some cells again which in-turn would trigger the recursion all over again. For ex, image two 1 connected together. They would keep on calling to their neighbours infinitely. To handle this case, whenever before recursively exploring the 4 directions, we will set the input grid at that cell = 0, so that it does not get counted again.
- Time = O(R∗C), where R is the number of rows in the given
grid, and C is the number of columns. We visit every square once.
- Space = O(R∗C), the space used by the call stack during our recursion.