Menu

Number of Islands (LeetCode # 200)

Coding Challenges, Medium
Share

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.