Number of Islands

Problem Statement

Given a 2D grid consisting of

s and s, where represents land and represents water, write an algorithm to count the number of distinct islands in the grid.

An island is defined as a group of connected land cells. Land cells are considered connected if they share a boundary with another land cell. Two land cells are not considered to be part of the same island if they are separated by water cells.

Rules and Constraints

• The input grid will not contain any
  null
  or empty rows.
• The grid will only contain
  1
  s (representing land) and
  0
  s (representing water).
• The grid is guaranteed to be a rectangular matrix (i.e., all rows have the same number of columns).
• The number of islands in the grid may be zero.
• The time complexity of your algorithm should be O(M * N), where M is the number of rows in the grid and N is the number of columns in the grid.
• The space complexity of your algorithm should be O(M * N), which may be used to store the visited cells during the traversal.

Additional Notes

• You may modify the input grid in any way you want while solving the problem.
• It is acceptable to use any traversal or data structure technique to solve this problem.

Example

Input: {"input_data":[1,2,3]} Output: [1,2,3]