Number of Islands (LeetCode # 200)

Challenge Statement

• Given an m x n 2D binary grid grid representing 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 grid edges are surrounded by water.
• This challenge corresponds to LeetCode #200.

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

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

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

Solution

Below is my solution and some test cases. The solution has a linear time complexity of O(n) and a linear space complexity O(n), where n is the number of cells in the grid.