🤖
Data Structures and Algorithms
  • CS Theory And Problems
  • Big O
    • Big O Notation
  • Algorithms
    • Binary Search
    • Breadth First Search (BFS)
    • Depth First Search (DFS)
    • Dynamic Programming
    • Kadane's Algorithm
    • Kahn's Algorithm
    • Quickselect
    • Recursion
    • Sorting Algorithms
    • Sliding Window
  • Data Structures
    • Binary Heap
    • Graph
    • Linked List
    • Trees
  • Problems
    • LeetCode
      • 1. Two Sum
      • 3. Longest Substring Without Repeating Characters
      • 5. Longest Palindromic Substring
      • 11. Container With Most Water
      • 15. 3 Sum
      • 19. Remove Nth Node From End of List
      • 20. Valid Parentheses
      • 33. Search in Rotated Sorted Array
      • 49. Group Anagrams
      • 53. Maximum Subarray
      • 55. Jump Game
      • 56. Merge Intervals
      • 76. Minimum Window Substring
      • 98. Validate Binary Search Tree
      • 105. Construct Binary Tree from Preorder and Inorder Traversal
      • 121. Best Time to Buy and Sell Stock
      • 133. Clone Graph
      • 141. Linked List Cycle
      • 152. Maximum Product Subarray
      • 153. Find Minimum in Rotated Sorted Array
      • 200. Number of Islands
      • 206. Reverse Linked List
      • 207. Course Schedule
      • 217. Contains Duplicate
      • 226. Invert Binary Tree
      • 238. Product of Array Except Self
      • 242. Valid Anagram
      • 297. Serialize and Deserialize Binary Tree
      • 347. Top K Frequent Elements
      • 417. Pacific Atlantic Water Flow
      • 424. Longest Repeating Character Replacement
      • 435. Non-overlapping Intervals
      • 647. Palindromic Substrings
Powered by GitBook
On this page
  • Description
  • Observations
  • Examples
  • Solutions
  • Using a Set to keep track of visited vertices
  • Mutating the input matrix to mark visited vertices
  1. Problems
  2. LeetCode

200. Number of Islands

Previous153. Find Minimum in Rotated Sorted ArrayNext206. Reverse Linked List

Last updated 3 years ago

Description

See:

Note: both m and n must have a length of at least 1.

Observations

We need to find "islands" of 1s in a sea of 0s. If a 1 touches another 1 in the directions up, down, left or right then they are considered to form an island. Note that diagonally touching 1s are not considered to form an island.

Examples

Example 1

grid = [ ["0","0","1"], ["0","1","1"], ["0","1","1"] ]

grid = [
["0","0","1"],
["0","1","1"],
["0","1","1"], 
]

In this example there is 1 island. It is formed by the cells [0,2], [1,2], [1,1], [2,2], [2,1].

The connections can be diagrammed as:

Example 2

grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]

grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]

In this example there are 3 islands:

  • Island 1: [0,0], [0,1], [1,0] and [1,1]

  • Island 2: [2, 2]

  • Island 3: [3, 3] and [3, 4]

The connections are diagrammed as:

Solutions

I solved the problem using the DFS algorithm and using a Set to keep track of the visited vertices.

After submitting my answer I looked at some of the other solutions in the discussion. Another approach to marking the vertex as visited is to change to value of the vertex itself. So, change it from "1" to "X". Since we are only looking for "1"s an X will be ignored and we won't visit it. This approach saves space on storage as we don't need the Set to track the visited vertices. However, it does mutate the input array, which may not be acceptable.

Using a Set to keep track of visited vertices

My solution using DFS.

class Solution:
    def __dfs(self, grid: List[List[str]], m: int, n: int, visited: Set):
        if m < 0 or n < 0 or m >= len(grid) or n >= len(grid[m]) or grid[m][n] == "0" or (m, n) in visited:
            return
        visited.add((m, n))
        # In the standard DFS algorithm we usually have a for loop to iterate over the adjacent vertices list. Here, we
        # look in the surrounding cells instead. 
        self.__dfs(grid, m + 1, n, visited)
        self.__dfs(grid, m - 1, n, visited)
        self.__dfs(grid, m, n + 1, visited)
        self.__dfs(grid, m, n - 1, visited)

    def numIslands(self, grid: List[List[str]]) -> int:
        num = 0
        visited = set()
        for m in range(len(grid)):
            for n in range(len(grid[m])):
                if (m, n) not in visited and grid[m][n] == "1":
                    num += 1
                    self.__dfs(grid, m, n, visited)
        return num

Time complexity: O(V + E) where V is the number of vertices (here it is m * n), and E is the number of edges.

Space complexity: O(V), the visited vertices are stored in the Set.

Mutating the input matrix to mark visited vertices

I like this solution, if mutating the input grid is acceptable.

class Solution:
    def __dfs(self, grid, m, n, i, j):
        if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != "1":
            return
        grid[i][j] = "X"
        self.__dfs(grid, m, n, i - 1, j)
        self.__dfs(grid, m, n, i + 1, j)
        self.__dfs(grid, m, n, i, j + 1)
        self.__dfs(grid, m, n, i, j - 1)

    def numIslands(self, grid: List[List[str]]) -> int:
        num = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    num += 1
                    self.__dfs(grid, m, n, i, j)

        return num

Time Complexity: Same as above

Space Complexity: O(1), no additional space is needed.

This is a scenario.

Since this is a we can use either or to traverse the vertices to determine how many islands there are. This is a disconnected graph, so we will need to iterate through the entire matrix to find the various islands.

https://leetcode.com/problems/number-of-islands/
graph
DFS
BFS
disconnected graph