Count Distinct Values in a Sorted Array When K Is Small

Given an integer array sorted in nondecreasing order, return the number of distinct values.

Let n be the array length and k the number of distinct values. Design for the case where k is much smaller than n; a full linear scan is valid but will not meet the intended efficiency target. Aim for O(k log n) time and O(1) auxiliary space.

Function Signature

def count_distinct_sorted(numbers: list[int]) -> int:
    ...

Constraints

• 0 <= len(numbers) <= 1_000_000
• numbers is sorted in nondecreasing order.
• -1_000_000_000 <= numbers[i] <= 1_000_000_000.

Examples

Input: numbers = [1, 1, 1, 4, 4, 9, 9, 9, 9]
Output: 3

Input: numbers = []
Output: 0

Input: numbers = [5, 5, 5]
Output: 1

Distinct Value Count in a Sorted Array

You are given an integer array numbers that is already sorted in nondecreasing order. Return the number of distinct values it contains.

Let n be the length of the array and k the number of distinct values it holds. The interesting case is the one where k is much smaller than n: the array is a short list of values, each repeated many times. A full linear scan over all n elements is a correct solution, but it is not the intended one. Aim for O(k log n) time and O(1) auxiliary space, using the fact that every group of equal values occupies one contiguous block of the sorted array.

Output

Return a single integer: the count of distinct values in numbers. An empty array contains zero distinct values, so it returns 0. The answer is a single number, so there is no ordering or tie-breaking to resolve.

Examples

Example 1:

Input:  numbers = [1, 1, 1, 4, 4, 9, 9, 9, 9]
Output: 3

The array holds three blocks of equal values -- 1, 4, and 9 -- so there are three distinct values. Note that the answer counts blocks, not elements: the array has nine elements.

Example 2:

Input:  numbers = [-1000000000, -1000000000, 0, 1000000000]
Output: 3

The value -1000000000 appears twice but is counted once, giving the three distinct values -1000000000, 0, and 1000000000.

Example 3:

Input:  numbers = []
Output: 0

Hints

1. The array is sorted, so all copies of a value sit in one contiguous block. Counting distinct values is exactly counting blocks.
2. Walking element by element costs O(n) no matter how few blocks there are. If you can jump from the start of a block straight to the start of the next one, the total work becomes proportional to k instead.
3. To find where the current block ends without scanning it, probe at offsets 1, 2, 4, 8, ... from the block's start until you overshoot it, then binary search inside the last (at most doubled) window to pin down the exact boundary.

Approach

The array is sorted, so equal values are contiguous: the array is a sequence of k blocks, and the answer is simply the number of blocks. The whole problem is therefore "jump from the start of one block to the start of the next" as cheaply as possible.

The reference solution keeps an index i at the first element of the current block. It increments the counter once for that block, then locates the first index whose value differs from numbers[i] in two phases:

element still equals the current value, it doubles step. The loop stops the moment i + step runs off the end of the array or lands on a different value. After it stops, two facts hold: index i + step / 2 is still inside the block (it was the last offset that tested equal), and index i + step, if it exists, is already past the block.

2. Binary search. Those two facts bracket the boundary inside a window of size at most step / 2, so a standard binary search over [i + step / 2 + 1, min(i + step, n)) finds the first index whose value differs. That index is the start of the next block, and i jumps directly to it.

If the current block has length L, the gallop performs about log2(L) probes and the binary search about another log2(L), so each block costs O(log L) rather than O(L). Summed over all k blocks this is O(k log n) in the worst case (and O(k log(n / k)) by concavity), with only a handful of integer variables held alongside the input, hence O(1) auxiliary space.

Two edge cases fall out for free. An empty array never enters the outer loop and returns 0. A block that runs to the end of the array makes the gallop stop on the i + step < n bound, and clamping the search's upper end with min(i + step, n) lets the binary search settle on n, which terminates the outer loop.

Correctness does not depend on the values being small or nonnegative: only the == comparison and the sortedness precondition are used, so negative values and values at the +/-10^9 bounds behave identically. The largest quantity the algorithm ever forms is i + step, which stays below 3 * 10^6, so 32-bit integers are safe in Java and C++.

• Time complexity: O(k log n)
• Space complexity: O(1)