Number of Islands LeetCode

In computer science, the LeetCode Number of Islands problem tests a programmer’s ability to solve graph problems. The problem can be applied in real-world scenarios such as image processing, where it can be used to identify objects in an image. In this problem, our goal is to identify islands within a grid of 1s and 0s. By solving this puzzle, we learn to navigate grids and understand connections, making it an engaging journey of discovery.

Key takeaways:

• Problem understanding: The problem involves a 2D grid where 1 represents land and 0 represents water. Islands are formed by connecting adjacent lands (horizontally or vertically). The goal is to count the number of distinct islands in the grid.

• Approach: Depth-First Search (DFS) is used to explore and traverse the grid. For each land cell (1), the DFS explores all connected land cells, marking them as visited to avoid revisiting the same island. The DFS traversal ensures that each connected group of 1s is counted as one island.

• Real-world application: This problem can be applied to image processing, where detecting connected components (like objects in an image) is analogous to identifying islands in the grid.

Let’s consider the following illustration to see islands formation within a grid.

The illustration above sets the groundwork for the problem that we will explore in more detail within the problem statement.

Problem statement

Consider a 2D grid of size $(m \times n ).$ Each cell in the grid consists of either 1 or 0. The value of 1 represents land, and a value of 0 represents water. Connecting adjacent 1s horizontally or vertically (not diagonally) forms islands. Our task is to identify the number of islands that exist on the grid.

Some important points that need to be remembered while solving this problem:

• Each cell of the grid either consists of 1s or 0s.

• Diagonal connections within an island are not considered.

• Every row within the grid should be of the same size.

• The grid should contain a minimum of 1 and a maximum of 300 rows and columns, e.g., $1 <= m, n <= 300$.

The LeetCode Number of Islands problem involves determining the number of islands surrounded by the water under these constraints. The result should be an integer representing the number of islands. Now, let's map our previous example to the problem for better understanding.

In the slides above, we discuss how we can explore the whole grid to find the number of islands. Let's quickly test our understanding of this problem.

Knowledge test

Now that we have understood the problem, let’s check our knowledge by finding the number of islands for the examples below:

Note: If you’re stuck, click the “Show Solution” button.

Solution to Number of Islands problem

Now that we’ve understood the problem, let’s understand it programmatically. To traverse the whole grid, we use depth-first search (DFS). Let's discuss how we employ DFS to traverse the whole grid to find number of islands:

• If the grid is empty, return 0 (no islands).

• Initialize count to 0 (to count the number of islands).

• Iterate through each cell in the grid using nested loops.

• If the current cell is 1, initiate a DFS (graphdfs(self, grid, row, col)) and increment the count:

  • If the current cell is out of grid boundaries or not part of the island, return without further exploration (base case).

  • Mark the current cell as visited by changing “1” to “#.”

  • Recursively call DFS on adjacent cells (up, down, left, right) to explore the island:

    • Move down: graphdfs(grid, row+1, col)

    • Move up: graphdfs(grid, row-1, col)

    • Move right: dfgraphdfs(grid, row, col+1)

    • Move left: graphdfs(grid, row, col-1)

• After exploring all islands using DFS, return the total number of islands in the grid.

In the slides above, we found one island as we performed the first iteration only. We need to check each cell in the grid marked as 1. When it finds a 1, it begins exploring (through DFS) that area to find the whole island connected to it. After completing this exploration, it moves on to the next 1 in the grid to search for another island. This process repeats until it has checked every 1 cell, ensuring it finds and counts all the islands present in the whole grid.

Code for implementing Number of Islands solution

Let’s have a look at the code for the algorithm we just discussed:

Code explanation

Here’s the explanation of the code:

• Line 1: The numIslands class is defined with two methods: findIslands and graphdfs.

  • The findIslands method takes a 2D list grid_input as input and returns the number of islands in the grid.

  • The graphdfs method is a helper method that performs depth-first search (DFS) on the grid to find the islands.

• Lines 3–6: The function first checks if the input grid is empty. If it is empty, the function returns 0.

• Line 8: The findIslands method initializes a counter variable count_islands to 0 and iterates over each cell in the grid.

• Lines 15–25: If the cell value is 1, it means that a new island has been found. The graphdfs method is called to mark all the cells in the island as visited.

• Line 22: The count_islands variable is incremented by 1 for each new island found.

• Line 25: Finally, the findIslands method returns the total number of islands found in the grid.

Time complexity

The time complexity of this code is $O(m \times n)$ where $m$ is the number of rows in the grid, and$n$is the number of columns. This complexity arises due to the nested loops that iterate through each cell in the grid once.

Space complexity

The overall space complexity of this code is $O(m × n)$ due to the input matrix and the recursion stack during DFS, which means it depends on the maximum depth of recursion.

Coding problems similar to Number of Islands

There are several other coding problems that involve similar concepts of exploring grids, identifying connected components, and solving graph traversal challenges, providing excellent practice for sharpening your skills in this area. Here are a few problems that are similar to the Number of Islands problem:

1. Flood Fill: Given a grid, starting from a pixel, the goal is to change all connected pixels of the same color to a new color. This problem uses similar DFS/BFS techniques.

2. Pacific Atlantic Water Flow: You are given a grid where water can flow to either the Pacific or Atlantic ocean. The goal is to determine which cells can flow water to both oceans.

3. Max Area of Island: This problem requires finding the largest island in a 2D grid. By exploring connected land cells (1s) using DFS or BFS, the task is to calculate the maximum area of any island present in the grid.