Count Distinct Values in a Sorted Array When K Is Small
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# 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
```python
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
```text
Input: numbers = [1, 1, 1, 4, 4, 9, 9, 9, 9]
Output: 3
```
```text
Input: numbers = []
Output: 0
```
```text
Input: numbers = [5, 5, 5]
Output: 1
```
Overview: Count distinct values in a sorted array efficiently when the number of unique values is much smaller than the array length. The challenge tests adapting complexity to output diversity rather than raw length, meeting an O(k log n) target with constant auxiliary space, and handling empty or uniform arrays.
Read the full Meta Software Engineer interview experience this question came from
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:
```text
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:
```text
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:
```text
Input: numbers = []
Output: 0
```
Constraints
- 0 <= numbers.length <= 10^6
- -10^9 <= numbers[i] <= 10^9
- numbers is sorted in nondecreasing order (numbers[i] <= numbers[i + 1] for every valid i).
- The returned count is in the range 0 <= answer <= 10^6, so every value and every intermediate index fits comfortably in a 32-bit signed integer; int in Java and C++ is sufficient.
Examples
Input: ([],)
Expected Output: 0
Input: ([7],)
Expected Output: 1
Hints
- The array is sorted, so all copies of a value sit in one contiguous block. Counting distinct values is exactly counting blocks.
- 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.
- 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.