DEV Community

Cover image for Leetcode Number Of Islands
Omkar Bhagat
Omkar Bhagat

Posted on

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Discussion (0)