Problem Statement in English

You’re give a grid, with elements that are strings - either "1", or "0". "1" indicates that the cell is part of an island. You’ve to count the number of islands.

Approach

This problem is a subset of another one that I’ve covered.

Solution in Python



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

        # only to be called only on cells that are "1"
        def recursiveCall(i: int, j: int):
            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:
                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:
                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:
                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:
                recursiveCall(i, j + 1)

        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:
                    recursiveCall(i, j)
                    ans += 1
        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.