Number Of Islands Leetcode Problem 200 [Python Solution]

What we face today is a fascinating graph-based challenge that is both educational and commonly asked in technical interviews, Number Of Islands.

Whether you are a beginner or an experienced coder, this problem will sharpen your algorithmic skills.

We will provide a Python solution, and don’t worry, we’ll cover every little detail you need to know.

Problem Overview

Question: Given an m x n 2D binary grid grid, which represents a map of ‘1’s (land) and ‘0’s (water), your task is to count and return the number of islands.

An island is defined as an area surrounded by water, formed by connecting adjacent lands horizontally or vertically.

It’s essential to note that diagonally adjacent lands do not count as part of the same island.

You can assume that all four edges of the grid are surrounded by water.

Let’s visualize this problem with an example.

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

In this case, we have a single island, as shown in the grid.

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

In this example, there are three islands, each represented by connected ‘1’s.

Understanding the Constraints

Before diving into the solution, let’s understand the constraints of this problem:

• m == grid.length: The number of rows in the grid.
• n == grid[i].length: The number of columns in each row.
• 1 <= m, n <= 300: The dimensions of the grid can vary, but they are limited within this range.
• grid[i][j] is either ‘0’ or ‘1’: Each cell in the grid can contain either ‘0’ (water) or ‘1’ (land).

Now that we have a clear understanding of the problem and its constraints, let’s explore the solutions.

Number of Islands LeetCode Problem Solution

1. Bruteforce Approach

A naive approach to solve this problem is to traverse the entire grid and for each ‘1’ encountered, perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to explore and mark all connected ‘1’s as visited.

We can count the number of DFS or BFS iterations, and that will give us the total number of islands.

Let’s implement a Python solution using Depth-First Search (DFS):

def numIslands(self, grid):
    if not grid or not grid[0]:
        return 0

    islands = 0
    visit = set()
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if (
            r not in range(rows)
            or c not in range(cols)
            or grid[r][c] == "0"
            or (r, c) in visit
        ):
            return

        visit.add((r, c))
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        for dr, dc in directions:
            dfs(r + dr, c + dc)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in visit:
                islands += 1
                dfs(r, c)
    return islands

This solution uses Depth-First Search to traverse the grid and counts the number of islands.

For each unvisited ‘1’, it initiates a DFS to mark all connected ‘1’s as visited.

2. Efficient Approach with Breadth-First Search (BFS)

While the brute force approach works, it can be optimized.

We can use a more efficient BFS approach to solve the problem.

BFS offers a level-based traversal, making it suitable for finding connected components efficiently.

Here’s the Python solution using BFS:

def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])
        visited = set()
        islands = 0

        def bfs(r, c):
            q = deque()
            visited.add((r, c))
            q.append((r, c))

            while q:
                row, col = q.popleft()
                directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]

                for dr, dc in directions:
                    r, c = row + dr, col + dc
                    if (
                        r in range(rows)
                        and c in range(cols)
                        and grid[r][c] == '1'
                        and (r, c) not in visited
                    ):
                        q.append((r, c))
                        visited.add((r, c))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visited:
                    bfs(r, c)
                    islands += 1

        return islands

This solution uses Breadth-First Search, which offers an efficient way to count the number of islands by exploring connected ‘1’s and marking them as visited.

Time and Space Complexity

Before we conclude, let’s analyze the time and space complexity of our efficient BFS solution:

Time Complexity: In the worst case, we visit each cell of the grid exactly once.

The time complexity is O(m * n), where ‘m’ is the number of rows, and ‘n’ is the number of columns.

Space Complexity: We use a set ‘visited’ to store visited cells.

In the worst case, we might need to store all cells in the set, so the space complexity is O(m * n) as well.

Reasoning Behind Our Approach

The reasoning behind our efficient BFS approach is as follows:

1. We initialize a queue to perform BFS, a set to keep track of visited cells, and a variable to count the number of islands.
2. We iterate through each cell in the grid and check if it’s a land (‘1’) and if it has not been visited.
3. If it’s an unvisited land, we initiate a BFS traversal from that cell to mark all connected lands as visited.

This helps avoid counting the same island multiple times.

4. We increment the island count whenever we start a new BFS traversal, indicating a new island.
5. We return the total number of islands counted.

Related Interview Questions By Company:

• Best Time To Buy And Sell Stock II LeetCode
• Maximum Length Of A Concatenated String With Unique Characters
• Find Unique Binary String LeetCode

Related Interview Questions By Difficulty:

• Clone Graph LeetCode
• Number Of Connected Components In An Undirected Graph LeetCode
• Check If Move Is Legal LeetCode

Related Interview Questions By Category:

• Alien Dictionary LeetCode
• Swim In Rising Water LeetCode
• Course Schedule II LeetCode

Conclusion

In this blog post, we tackled the Number Of Islands problem, a common challenge in coding interviews.

We provided both a brute force approach using Depth-First Search (DFS) and an efficient solution using Breadth-First Search (BFS).

We explained the problem, its constraints, and the reasoning behind our efficient approach.

This problem is not only educational but also a great way to practice graph traversal algorithms and data structures.

If you found this tutorial helpful, please consider leaving a like, subscribing, and sharing it with others who might benefit from it.

Feel free to ask questions, make suggestions, and share your thoughts in the comments.

Happy coding!

Question Link