Leetcode Number Of Islands

In this post we'll have a look at LeetCode problem #200 called Number Of Islands.

The problem statement is quite straightforward. Given a grid of 1s and 0s, we need to find the total number of islands in a given grid.

They mention:

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

For example:

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

And another example:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

How do we solve it?

My approach is to look at each (unvisited) cell in the grid, if it contains 1 then (recursively) expand outward from there as long as its neighbour also has a 1. This is called BFS (breadth first search).

When we visit a cell, we'll mark that cell as visited, such that we'll not visit it again later.

Here's the solution:

class Solution:
    def numIslands(self, grid):

        ROWS, COLS = len(grid), len(grid[0])
        res = 0
        visited = set()

        def dfs(r,c):
            if r<0 or c<0 or r>=ROWS or c>=COLS or (r,c) in visited or grid[r][c] != "1":
                return

            visited.add((r,c))
            dfs(r+1,c)
            dfs(r-1,c)
            dfs(r,c+1)
            dfs(r,c-1)

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == "1" and (r,c) not in visited:
                    res += 1
                    dfs(r,c)

        return res

The code itself is also very straightforward to understand. I hope you find it helpful.

Note that we can avoid using a visited set by simply marking 1s with some symbol, like a # sign.

--
Cover Photo by Sacha Gregoire on Unsplash