200. Number of Islands#

Difficulty: Medium

Link to Problem: To see the Number of Islands problem on LeetCode, click here!

Given an m x n 2D binary grid grid which represents a 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.

Constraints:

  • m == grid.length

  • n == grid[i].length

  • 1 <= m, n <= 300

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

Probelm Explanation:#

The problem is about counting the number of islands in a 2D binary grid. In this grid, ‘1’ represents land, and ‘0’ represents water. An island is defined as a group of ‘1’ cells that are adjacent to each other either horizontally or vertically. It’s important to note that diagonal connections do not count. Additionally, it’s assumed that all four edges of the grid are surrounded by water, meaning the grid is finite and doesn’t “wrap around.”

The objective is to determine how many distinct islands exist in the grid. To clarify, an island consists of connected ‘1’ cells, and these connections can only occur horizontally or vertically. If there are no ‘1’ cells in the grid, the number of islands would be zero.

The problem often involves using graph traversal techniques like Depth-First Search (DFS) or Breadth-First Search (BFS) to identify and count these islands. You start at one ‘1’ cell and explore its adjacent cells to determine the extent of the island. Once you’ve visited all the ‘1’ cells in an island, you move on to the next unvisited ‘1’ cell and repeat the process until you’ve counted all the islands in the grid.

In essence, the problem asks you to analyze the grid to find groups of connected ‘1’ cells and count them as individual islands. The goal is to return the total count of islands in the given grid.

Solution:#

Here’s a Python function to implement this algorithm:

from typing import List

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

        m, n = len(grid), len(grid[0])  # Get the dimensions of the grid
        num_islands = 0  # Initialize the count of islands

        def dfs(row, col):
            if row < 0 or row >= m or col < 0 or col >= n or grid[row][col] == '0':
                return

            grid[row][col] = '0'  # Mark the current cell as visited by changing it to '0'
            directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # Define four possible directions to move

            for dr, dc in directions:
                # Explore adjacent cells
                dfs(row + dr, col + dc)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    num_islands += 1  # Increment the island count
                    dfs(i, j)  # Start a DFS from the current '1' cell to explore the entire island

        return num_islands

Explanation:#

The provided code defines a Python class called Solution with a method called numIslands. This class is designed to count the number of islands in a 2D binary grid.

The numIslands method takes a 2D grid as input, where ‘1’ represents land, and ‘0’ represents water. It uses a depth-first search (DFS) approach to identify and count islands. The key steps in the code include:

  1. Checking if the input grid is empty, and if so, returning 0 (indicating there are no islands).

  2. Determining the dimensions of the grid (number of rows and columns).

  3. Initializing a variable num_islands to keep track of the count of islands.

  4. Defining a nested function dfs to perform depth-first search. This function recursively explores adjacent land cells connected to the current cell and marks them as visited by changing ‘1’ to ‘0’.

  5. In the dfs function, it checks for boundary conditions and whether the current cell is ‘0’. If these conditions are met, it returns without further exploration.

  6. The dfs function explores neighboring cells in all four directions (up, down, left, right) using a loop.

  7. The main loop iterates through each cell of the grid. When a ‘1’ cell is encountered, it increments the num_islands count and starts a DFS from that cell to explore the entire island.

  8. Finally, the method returns the total count of islands found in the grid.

This code encapsulates the solution in a class, allowing you to create an instance of the Solution class and call the numIslands method on it to count the number of islands in a given grid.

Test cases:#

Here’s how you can use this solution:

grid1 = [
  ["1", "1", "1", "1", "0"],
  ["1", "1", "0", "1", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "0", "0", "0"]
]

solution = Solution()
result1 = solution.numIslands(grid1)
print("Example 1 Output:", result1)  # Expected output: 1

Example 1 Output: 1

grid2 = [
  ["1", "1", "0", "0", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "1", "0", "0"],
  ["0", "0", "0", "1", "1"]
]

result2 = solution.numIslands(grid2)
print("Example 2 Output:", result2)  # Expected output: 3

Example 2 Output: 3

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided code:

Time Complexity:

  • The code uses a depth-first search (DFS) to explore the grid and count the number of islands.

  • In the worst case, it visits every cell in the grid exactly once.

  • The DFS function explores neighboring cells in four directions (up, down, left, right), so it has a time complexity of \(O(4^{max(m, n)})\), where m is the number of rows and n is the number of columns.

  • Therefore, the overall time complexity of the code is O(m * n), where m is the number of rows, and n is the number of columns.

Space Complexity:

  • The space complexity is determined by the recursive calls and the depth of the DFS stack.

  • In the worst case, when the entire grid consists of ‘1’s, the depth of the DFS recursion can be as deep as max(m, n).

  • Therefore, the space complexity of the code is O(max(m, n)), representing the maximum depth of the DFS stack.

In practical terms, for reasonably sized grids, the time and space complexity is linear, and the code should perform well. However, it’s important to keep in mind that the worst-case time complexity is O(m * n), and the space complexity can be O(max(m, n)).

Challenging Exercises:#

  1. Identify Largest Island: In addition to counting the number of islands, modify the code to identify the largest island in the grid and return its size.

  2. Optimize for Space: Modify the solution to reduce its space complexity to O(1) without modifying the input grid. This is a more memory-efficient version of the problem.