LeetCode: 200. Number of Islands

Summary

Given an m x n 2D binary grid grid, which represents 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 land cells horizontally or vertically. You may assume that all four edges of the grid are surrounded by water.

Approach

We use the Union-Find data structure to track connected components of land cells.

Each land cell "1" is treated as an independent island at the beginning. We do not need to count water cells because the maximum possible number of islands is the number of "1" cells.

We iterate through the grid and union adjacent land cells. If two land cells are connected, they belong to the same island, so the total island count decreases by one.

To simplify the implementation, we map each 2D coordinate (i, j) to a 1D index.

id = i * cols + j

This allows us to use a standard Union-Find structure with 1D arrays.

For each land cell, we only check the right and bottom neighbors. This avoids duplicate checks because the left and top neighbors will already have been processed.

Whenever two adjacent land cells are unioned successfully, the island count is decremented.

Union-Find optimizations:

Path compression in find
Union by size to keep tree shallow.

Time complexity is nearly linear:

O(M*N*alpha(M*N))

Where alpha is the inverse Ackermann function, which grows extremely slowly and can be tread as constant in practice. Here, alpha is the inverse Ackermann function, which grows extremely slowly and can be treated as a constant in practice.

Function

Initialization:

rows, cols: Grid dimensions
parent: array of size rows*cols
size: array of size rows*cols
count: number of land cells

Function find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x]

Function union(x, y): root_x = find(x) root_y = find(y)

if root_x == root_y: return 0 if size[root_x] < size[root_y]: parent[root_x] = root_y size[root_y] += size[root_x] else: parent[root_y] = root_x size[root_x] += size[root_y] return 1

Main logic: rows = len(grid) cols = len(grid[0])

parent = [i for i in range(rowscols)] size = [1] * (rowscols)

count initial land cells

for i in 0..rows-1: for j in 0..cols-1: if grid[i][j] == "1": count += 1

for i in 0..rows-1: for j in 0..cols-1: if grid[i][j] == "0": continue current = i * cols + j for (ni, nj) in [(i+1, j), (i, j+1)]: if ni < rows and nj < cols and grid[ni][nj] == "1": neighbor = ni*cols+nj count -= union(current, neighbor) return count

Complexity

Time Complexity: O(M*N*alpha(M*N)) Space Complexity: O(M*N)