JavaScript Algorithms: Number of Islands (LeetCode)

Photo by Upgraded Points on Unsplash

Description

Given an m x n 2d grid map of '1's (land) and '0's (water), return the number of islands.

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.

Example 1:

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

Example 2:

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

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

Solution

Let’s take a look at Example 1.

As we can see, it looks like a graph. But unlike graphs which have children, here we have top-right-bottom-left neighbors. So, we can say that we need to find all the connected components in this graph. In graph theory, a component of an undirected graph is an induced subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the rest of the graph.

In Example 1 we have only one connected component.

Example 2 — three.

In this problem we have two edge cases:

• Four edges of the grid are all surrounded by water (we need to check whether we’re out of the grid or not)
• We should visit each 1 only once (avoid infinite recursion)

We can solve this problem by using a Breadth-first search or Depth-first search algorithms. Let’s start with DFS.

Let’s go through this 2D array and if we see 1, we’re going to calldfs and increment some islands counter. And we should keep in mind our edge cases. The first can be solved by checking whether we’re inside the drid:

if (
  i >= 0 &&
  j >= 0 &&
  i < grid.length &&
  j < grid[i].length &&
  grid[i][j] === '1'
) {...}

And the second can be solved by changing each visited cell by 0. Let’s look at the whole solution:

DFS submissions details

The time complexity of this solution is O(nm) since we’re visiting each element in the 2D array once. The space complexity of this solution is O(nm) as well in the case the whole grid is filled with 1.

Now, let’s figure out how we can solve this problem using BFS.

We can go through all cells and do the same things — call the bfs algorithm every time when we see 1 and increment some counter.

The space and time complexity of this solution is the same as the DFS algorithm.

I hope, it was useful for you. Thanks for reading! Looking forward to your feedback. See you soon ✌️