Practice/Meta/Leetcode 200. Number of Islands

Leetcode 200. Number of Islands

CodingMust

Problem

You are given a 2D grid representing a map where each cell contains either "1" (land) or "0" (water). An island is defined as a group of adjacent land cells connected horizontally or vertically (not diagonally). The grid is completely surrounded by water on all edges.

Your task is to count the total number of distinct islands in the grid.

Requirements

1. Two land cells are considered part of the same island if they share an edge (4-directional connectivity)
2. Diagonal connections do not count as adjacent
3. You must count each separate island exactly once
4. The input grid will not be modified in the actual test environment (though you may modify it in your solution if needed)

Constraints

• 1 <= grid.length <= 300 (number of rows)
• 1 <= grid[0].length <= 300 (number of columns)
• grid[i][j] is either "1" or "0"
• Time complexity should be O(m × n) where m and n are the grid dimensions
• Space complexity should be O(m × n) in the worst case

Examples

Example 1:

Input: grid = [ ["1","1","0","0"], ["1","1","0","0"], ["0","0","1","0"], ["0","0","0","1"] ] Output: 3 Explanation: The grid contains three separate islands. The first island is the 2×2 block of land in the top-left corner. The second is a single cell at row 2, column 2. The third is a single cell at row 3, column 3.

Example 2:

Input: grid = [ ["1","0","1","0","1"], ["0","0","0","0","0"], ["1","0","1","0","1"] ] Output: 6 Explanation: Six isolated single-cell islands exist, arranged in a pattern with water separating each one.

Example 3:

Input: grid = [ ["1","1","1"], ["0","1","0"], ["1","1","1"] ] Output: 1 Explanation: All land cells are connected through the center cell, forming one large cross-shaped island.