Number of Islands

Try to solve the Number of Islands problem.

We'll cover the following

Statement#

Let’s consider a scenario with an (m×n)(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≤1 \leq grid.length ≤300\leq 300

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

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

Examples#

canvasAnimation-image

1 of 3

canvasAnimation-image

2 of 3

canvasAnimation-image

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Number of Islands

1

What is the output if the following grid is given as input?

grid=[[1,0,0],[0,0,0],[0,0,1]] grid = \begin{matrix} [[1, 0, 0], \\ [0, 0, 0], \\ [0, 0, 1]] \end{matrix}

A)

1

B)

0

C)

2

D)

3

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Count all occurrences of cell 1s in the grid and store them in a variable called count.

Traverse the grid, and whenever a cell 1 is encountered, check whether this cell 1 has a neighboring cell 1 on its top, bottom, left, or right.

Connect all neighboring cell 1s into a single component, subtract the number of neighbors from count, and change the value of cell 1 in the grid to 0.

At the end of the traversal, count contains the number of islands.

Try it yourself#

Implement your solution in main.py in the following coding playground. You will need the provided supporting code to implement your solution.

Python
main.py
union_find.py
Input #1
Number of Islands

Union Find: Introduction

Solution: Number of Islands