We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Islands

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem can be solved using Depth-First Search (DFS) or Breadth-First Search (BFS) to explore each island.
  • Each time we find a '1' (land), we can perform a search to mark all adjacent lands as visited, thus counting that as one island.
  • The search can be conducted in four possible directions: up, down, left, and right.
  • We need to ensure that we handle grid boundaries to avoid index errors.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited once. Space Complexity: O(m * n) in the worst case for the recursion stack in DFS or O(min(m, n)) for BFS queue.

Solution

To solve the problem, we can use either Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the grid. We will iterate through each cell in the grid. When we find a '1', we will initiate a search to mark all connected '1's (parts of the island) as visited by changing them to '0's. This will ensure we do not count the same island multiple times. We will maintain a count of how many times we initiate a search, which will give us the total number of islands.

Code Solutions

def numIslands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    island_count = 0

    def dfs(r, c):
        # If we are out of bounds or at a water cell, return
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        # Mark the cell as visited
        grid[r][c] = '0'
        # Perform DFS in all four directions
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':  # Found an island
                island_count += 1
                dfs(r, c)  # Mark the whole island

    return island_count
← Back to All Questions