LeetCode #200: Number of Islands

LeetCode Solutions

https://leetcode.com/problems/number-of-islands/description/

Number of Islands is a classic graph theory problem in which we are given a 2D grid with 1s representing land and 0s representing water. We have to find the number of distinct islands present in the grid. An island is considered as a group of adjacent land (horizontally or vertically) surrounded by water.

We can solve this problem using Depth First Search (DFS) algorithm. We traverse the grid and whenever we encounter a land, we recursively destroy the island by marking all its adjacent lands as a different value so that we don’t consider the same land again. While destroying the island, we count the number of islands found.

Steps:

  1. Initialize two variables to keep track of the row and column lengths of the grid.
  2. Define a helper function called destroyIsland which takes in the row and column indices of the land we want to destroy.
  3. In the helper function, set the value of the current land to “2” to avoid infinite loops.
  4. Check all 4-dimensionally adjacent locations and if they are part of the island, recursively call the destroyIsland function.
  5. Initialize a variable ans to 0.
  6. Loop through each row and column of the grid.
  7. If we encounter a land (i.e., the element equals “1”), call the destroyIsland function and increment the ans variable.
  8. Return the final count of ans as the number of islands.

Here is the solution in Python3:

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        def destroyIsland(r, c):
            grid[r][c] = "2"
            for (row, col) in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
                if 0 <= row < m and 0 <= col < n and grid[row][col] == "1":
                    destroyIsland(row, col)
        ans = 0
        for i, row in enumerate(grid):
            for j, element in enumerate(row):
                if element == "1":
                    destroyIsland(i, j)
                    ans += 1
        return ans

Time Complexity

The time complexity of this solution is O(m x n) where m is the number of rows and n is the number of columns in the grid. This is because we traverse the entire grid exactly once.

Space Complexity

The space complexity of this solution is O(m x n) because we modify the input grid in-place and use DFS recursion stack of size m x n at the worst case, when the entire grid is filled with land.