Solution: Number of Islands

Statement#

Let’s consider a scenario with an $(m \times n)$ 2D grid containing binary numbers, where '0' represents water and '1' represents land. If any '1' cells are connected to each other horizontally or vertically (not diagonally), they form an island. Your task is to return the total number of islands in the grid.

Constraints:

• $1 \leq$ grid.length $\leq 300$

• $1 \leq$ grid[i].length $\leq 300$

• grid[i][j] is either '0' or '1'.

Solution#

The key approach is to traverse the 2D grid and join adjacent cell 1s horizontally or vertically. In the end, we return the number of connected components.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

Let’s start by counting the number of cell 1s in the grid. This can be done by declaring an instance of the Union Find class.

Here’s how the Union Find class initializes itself:

• We initialize a variable, count, as $0$.

• We initialize a list, parent, by traversing each element grid[i][j] as follows:

  • If we encounter a cell 1, we append the current index, i * n + j, of the grid according to the row major order and increment count by $1$ (see lines 13–15 in the Union Find class).

  • If a cell 0 is encountered, we append $-1$ to the array (see line 17 in the Union Find class) because cell 0s in the grid will be ignored anyway.

At the end of this traversal, count will contain the number of occurrences of cell 1 in the grid (see line 18 in main.py). Right now, all cell 1s are disconnected from each other. Let’s see how we can connect them to form an island and count the total number of islands in the grid.

For now, we have the count of the total number of cell 1s in the grid stored in count. However, we aim to connect all the neighboring cell 1s on the top, bottom, left, and right into components. This will reduce our count from the total number of cell 1s to the total number of connected components of cell 1s.

We can achieve this by using the union find algorithm to connect neighboring cell 1s, decrementing the count whenever a connection is made.

We’ll update the code by traversing each element of the grid as follows:

• If a cell 1 is encountered, we do the following:

  • We update the value of the grid from 1 to 0.

  • We check the value of each neighbor on the top, bottom, left, and right of the current element. If the value is 1, we perform the union operation between the current element and its neighbor, which consists of 1.

  • Inside the union operation, we check if the parent of the current element and its neighbor is different.

    • If so, we connect these two cells and decrement count by $1$.

    • Otherwise, if their parent is the same, they are already part of a connected component, so we do not decrement count.

• At the end of the traversal, count will contain the total number of islands.

The slides below illustrate how we would like the algorithm to run:

Let’s look at the code for this solution below:

Just the code#

Here’s the complete solution to this problem:

Solution summary#

To recap, the solution to this problem can be divided into the following three parts:

• Count all occurrences of cell 1s in the grid.

• Traverse the grid and if a cell 1 is encountered, perform the union operation between the neighboring cell 1s to connect them into a single component.

• Decrement count by $1$ only if the current element and its neighboring cell 1s aren’t already part of a connected component.

Time complexity#

The time complexity of this solution is $O(m × n)$, where $m$ is the number of rows, and $n$ is the number of columns.

Space complexity#

The space complexity of this solution is $O(m × n)$, as required by the Union Find class.