Count uniques in sparse sorted array

Question

A sorted array contains many duplicates but only a very small number of distinct values. Design an algorithm that counts how many unique numbers are present using fewer than O(n) operations. Discuss optimizations such as divide-and-conquer or binary search techniques and analyze the complexity.

Count Unique Values in Sorted Array

Given a non-decreasing integer array nums, return the number of distinct values in nums. The intended solution should avoid scanning all elements when the number of distinct values k is small by using binary search to jump over blocks of equal values, achieving O(k log n) time.

Constraints

• 0 <= n <= 200000
• -10^9 <= nums[i] <= 10^9
• nums is sorted in non-decreasing order
• Aim for O(k log n) time where k is the number of distinct values
• Use O(1) extra space

Examples

Example 1

Input: nums = [1,1,1,2,2,5,5,5,5,10]
Output: 4

Explanation: Distinct values are 1, 2, 5, and 10.

Example 2

Input: nums = []
Output: 0

Explanation: Empty array has zero distinct values.

Hints

1. In a sorted array, equal values form contiguous blocks.
2. Use binary search (upper bound) to find the index after the last occurrence of the current value.
3. Jump to that index and repeat until you reach the end.
4. In Python, bisect_right can be used to find the upper bound.

Approach

Because the array is sorted, identical values appear contiguously. Start at index i=0 and count one distinct value. Use an upper-bound binary search to find the first index greater than nums[i], which is one past the last occurrence of that value. Jump i to that index and repeat. There are k jumps (one per distinct value), each performing a binary search in O(log n), yielding O(k log n) time and O(1) extra space.

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