Leetcode Number Of Islands – DEV Community

On this publish we’ll take a look at LeetCode problem #200 referred to as Quantity Of Islands.

The issue assertion is sort of simple. Given a grid of 1s and 0s, we have to discover the entire variety of islands in a given grid.

They point out:

An island is surrounded by water and is shaped by connecting adjoining lands horizontally or vertically. You could assume all 4 edges of the grid are all surrounded by water.

For instance:

Enter: 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 one other instance:

Enter: 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 will we remedy it?

My method is to take a look at every (unvisited) cell within the grid, if it accommodates 1 then (recursively) broaden outward from there so long as its neighbour additionally has a 1. That is referred to as BFS (breadth first search).

After we go to a cell, we’ll mark that cell as visited, such that we’ll not go to it once more later.

Here is the answer:

class Resolution:
    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 vary(ROWS):
            for c in vary(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 can be very simple to know. I hope you discover it useful.

Notice that we are able to keep away from utilizing a visited set by merely marking 1s with some image, like a # signal.


Cowl Picture by Sacha Gregoire on Unsplash

Add a Comment

Your email address will not be published. Required fields are marked *