CODING

Day 20: The “Max Area of Island” problem

Problem:

Given a non-empty 2D array grid of 0's and 1's, 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.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[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]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

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

Given the above grid, return 0.

Note: The length of each dimension in the given grid does not exceed 50.

My Solution:

def getAreaOfIsland(i: int, j: int, grid: List[List[int]]):
    if((i<0) or (i>=len(grid)) or (j<0) or (j>=len(grid[i])) ):
        return 0
if(grid[i][j] == 1):
        grid[i][j]=0
        return 1 + (
            getAreaOfIsland(i+1, j, grid)
            + getAreaOfIsland(i-1, j, grid)
            + getAreaOfIsland(i, j-1, grid) 
            + getAreaOfIsland(i, j+1, grid) 
        )
    return 0
def maxAreaOfIsland(grid: List[List[int]]) -> int:
    max_val = 0
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            max_val = max(max_val, getAreaOfIsland(i, j, grid))
    return max_val

Explanation:

This problem is very similar to the “Number of Islands” problem.

I would suggest to have a look at that problem before you solve this.

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 a land, by recursively searching positions in the top, bottom, left and right. Each land occupies an area with value 1.

Once we land on an island (our current position is a land), to mark it as visited, we simply remove the visited island from the grid by sinking the land (mark land as water), and recursively sinking 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 there is an island there.

If we find an island,

1. We explore the island.
2. Sum the area of all lands in the island to find the total area.
3. Sink the island, so we don’t visit it again.
4. We update the maximum area, if the island’s area is bigger than the biggest island that we had found so far.

So, for our example, our algorithm works like this:

That’s it! And that’s how you solve the “Max Area of Island” problem.

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

If you would like me to solve and explain any problems, please add them as comments, along with a link to the problem description.

See you tomorrow!

Cheers!