Compute islands in a binary grid

You are given an m-by-n grid of characters where '1' represents land and '0' represents water. Count the number of connected land masses (islands) using 4-directional connectivity (up, down, left, right) and return that count. Also implement a variant that returns the sizes of all islands in descending order. Discuss and compare DFS, BFS, and Union-Find approaches, including their time and space complexities.

Number of Islands

You are given an m x n 2D grid grid of characters where '1' represents land and '0' represents water. An island is a group of '1's connected 4-directionally (up, down, left, right). You may assume all four edges of the grid are surrounded by water.

Return the number of islands.

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

This is a classic flood-fill / connected-components problem. Iterate over every cell; when you find an unvisited '1', increment your island counter and flood-fill (DFS, BFS, or Union-Find) to mark the entire connected component as visited so it is only counted once. DFS and BFS both run in O(m·n) time; Union-Find runs in O(m·n·α(m·n)) which is effectively linear.

Constraints

• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'
• The grid may be empty (treat as 0 islands)

Hints

1. Scan the grid cell by cell. The first time you hit an unvisited '1', you've discovered a new island.
2. From that cell, flood-fill (DFS or BFS) to all 4-directionally connected '1' cells and mark them visited so the same island is never re-counted.
3. Three standard approaches: DFS (recursive or stack), BFS (queue), or Union-Find. All are effectively O(m·n); Union-Find shines when edges/cells stream in dynamically.

Island Sizes in Descending Order

Building on the Number of Islands problem: given the same m x n grid of '1' (land) and '0' (water) characters with 4-directional connectivity, return a list of the sizes of every island, sorted in descending order. The size of an island is the number of land cells it contains.

Example:

Input: grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
Output: [4, 2, 1]

The 2x2 block has size 4, the horizontal pair has size 2, and the lone cell has size 1.

The approach mirrors counting islands: flood-fill each connected component, but instead of just incrementing a counter, count the cells in each component. Collect all sizes, then sort descending. This is the natural generalization the interviewer asked for as a follow-up.

Constraints

• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'
• The grid may be empty (return an empty list)
• Return sizes sorted in non-increasing order

Hints

1. This is the count-islands flood-fill, but track how many cells each component contains instead of just whether it exists.
2. Each time you discover a new unvisited '1', run a DFS/BFS and count every land cell you mark; append that count to a sizes list.
3. After collecting all sizes, sort the list in descending order before returning it.