Katkat
Back

Count Distinct Values in a Sorted Array When K Is Small

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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