Day 1: Max Area of Island

Problem Link:

Explore - LeetCode

Problem Statement:

You are given a 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 0.

Example 1:

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.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

1 <= m, n <= 50

My Solution:

def getArea(row: int, col: int, grid: List[List[int]]):
        if(row < 0 or row >= len(grid) or col < 0 or col >= len(grid[row])):
            return 0
        if(grid[row][col] == 1):
            grid[row][col] = 0
            return 1 + (
                getArea(row + 1, col, grid) + 
                getArea(row - 1, col, grid) + 
                getArea(row, col - 1, grid) + 
                getArea(row, col + 1, grid)
            )
        return 0
    
def maxAreaOfIsland(grid: List[List[int]]) -> int:
    maximumArea = 0
    for row in range(len(grid)):
        for col in range(len(grid[row])):
            maximumArea = max(maximumArea, getArea(row, col, grid))
    return maximumArea

Explanation:

We know, an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. To explore the island, we find out all lands connected to the land, by recursively searching positions in the top, bottom, left, and right. Each land occupies an area with value 1.

Once we know that our current position island, to mark it as visited, we simply remove the visited island from the grid by marking it as water i.e. 0 (sink), and recursively marking all connected lands around it.

Now that we know how to find an island, to solve this problem, at every position in the matrix, we check if it's an island. If we find an island, we sink the island and return that we have found one. Finally, we sum the number of positions at which we found islands.

That’s it!

If you are interested in solving more problems, do follow me and join me on this journey.

See you tomorrow!

Cheers!