Problem Statement in English

You’re given an integer matrix grid. Your task is to find the area of the largest island in that matrix. An island is a bunch of vertically and/or horizontally connected cells in the matrix with $1$ as their value. Islands are surrounded by water, indicated by a value of $0$.

The area is basically the number of vertically/horizontally connected neighbouring cells.

Approach

We absolutely have to iterate over every cell in grid. There’s no way around that, but, we can completely eliminate redundant computations. How?

Let’s say we iterate over each row, and within that, each column. Every time we find a $1$, that means it’s part of an island. Since we know that, we can check its neighbours in a plus pattern, fanning out from the central node - the node that we discovered has a value of $1$.

We can keep track of every node we visit, by adding it to a Set. This means that every time we are about to check a new index in grid, we can check if it already exists in the seen Set. If it does, there’s no need to process that cell again, and we can simply skip it.

The recursive approach, in this case, makes reading the code and understanding it really easy.

Solution in Python


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        s = set()

        # only to be called on 1 cells
        def recursiveCall(i: int, j: int) -> int:
            localAnswer = 1

            s.add(f"{i} {j}")

            # prev row, same col
            if i - 1 >= 0 and grid[i - 1][j] == 1 and f"{i-1} {j}" not in s:
                localAnswer += recursiveCall(i - 1, j)
            # next row, same col
            if i + 1 < len(grid) and grid[i + 1][j] == 1 and f"{i+1} {j}" not in s:
                localAnswer += recursiveCall(i + 1, j)
            # same row, prev col
            if j - 1 >= 0 and grid[i][j - 1] == 1 and f"{i} {j-1}" not in s:
                localAnswer += recursiveCall(i, j - 1)
            # same row, next col
            if j + 1 < len(grid[i]) and grid[i][j + 1] == 1 and f"{i} {j+1}" not in s:
                localAnswer += recursiveCall(i, j + 1)

            return localAnswer

        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 1 and f"{i} {j}" not in s:
                    ans = max(recursiveCall(i, j), ans)

        return ans

Complexity

  • Time: $O(n^2)$
    Since we need a nested loop to iterate over grid.

  • Space: $O(n^2)$
    Since we store upto $n^2$ elements (assuming grid is $n\times n$)

Note: We can improve this parameter by simply using grid itself to track visited cells. All we need to do is, once we visit a cell, if it was $1$, we make it $0$ once we’ve finished processing it. This way we avoid redundant processing while using no extra space, hence achieving $O(1)!$

And we are done.