Number of Islands

Problem Statement

Given a 2D grid grid where '1' represents land and '0' represents water, count and return the number of islands.

An island is formed by connecting adjacent lands horizontally or vertically and is surrounded by water. You may assume water is surrounding the grid (i.e., all the edges are water).

Constraints

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

Examples

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

Explanation: The input grid has exactly one island.

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

Explanation: The input grid has three islands.

Hints

• Approach 1: Depth-First Search (DFS)
• Approach 2: Union and Find (Union-Find)
• Approach 3: Breadth-First Search (BFS)