Count connected delivery zones

Given an m x n grid representing a service area, each cell is either 'Z' (deliverable zone) or '#' (blocked). Two 'Z' cells belong to the same zone if they are 4-directionally adjacent. Implement countZones(grid: List[List[char]]) -> int that returns the number of connected zones. Follow-up: return the sizes of all zones in descending order. Analyze time and space complexity, and then optimize for minimal extra space.

Count connected delivery zones

You are given an m x n grid representing a service area. Each cell is either 'Z' (a deliverable zone) or '#' (blocked). Two 'Z' cells belong to the same zone if they are 4-directionally adjacent (up, down, left, right).

Implement countZones(grid) that returns the number of connected zones (connected components of 'Z' cells).

This is the classic "Number of Islands" problem framed as a delivery service area. To minimize extra space, flip each visited 'Z' to '#' in place instead of using a separate visited set.

Example:

grid = [['Z','Z','#','#','#'],
        ['Z','Z','#','#','#'],
        ['#','#','Z','#','#'],
        ['#','#','#','Z','Z']]
countZones(grid) -> 3

There are three zones: the 2x2 block in the top-left, the single cell in the middle, and the pair in the bottom-right.

Constraints

• 1 <= m, n; the grid may be empty (return 0).
• Each cell is either 'Z' or '#'.
• Connectivity is 4-directional only (no diagonals).
• The input grid may be mutated in place by the reference solution.

Hints

1. This is 'Number of Islands' with 'Z' as land and '#' as water.
2. Scan every cell; when you hit an unvisited 'Z', increment the count and flood-fill the whole component.
3. Instead of a visited set, overwrite each visited 'Z' with '#' to use O(1) extra marking space — that is the minimal-space optimization the follow-up asks for.

Delivery zone sizes in descending order

Follow-up to 'Count connected delivery zones'. Given the same m x n grid of 'Z' (deliverable zone) and '#' (blocked) cells, implement zoneSizes(grid) that returns a list of the sizes of all connected zones (4-directionally connected components of 'Z' cells), sorted in descending order.

Example:

grid = [['Z','Z','#','#','#'],
        ['Z','Z','#','#','#'],
        ['#','#','Z','#','#'],
        ['#','#','#','Z','Z']]
zoneSizes(grid) -> [4, 2, 1]

The top-left block has 4 cells, the bottom-right pair has 2, and the middle cell has 1.

Constraints

• 1 <= m, n; the grid may be empty (return []).
• Each cell is either 'Z' or '#'.
• Connectivity is 4-directional only (no diagonals).
• The result must be sorted in descending order by size.
• The input grid may be mutated in place by the reference solution.

Hints

1. Reuse the flood-fill from countZones, but count the cells in each component instead of just incrementing a component counter.
2. Collect each component's size as you finish flooding it.
3. Sort the collected sizes in descending order before returning.