Count uniques in sparse sorted array
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### 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.
Quick Answer: This question evaluates proficiency in algorithm design and complexity analysis, focusing on reasoning about how a sorted array with very few distinct values can be handled to count unique elements.
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
Hints
- In a sorted array, equal values form contiguous blocks.
- Use binary search (upper bound) to find the index after the last occurrence of the current value.
- Jump to that index and repeat until you reach the end.
- In Python, bisect_right can be used to find the upper bound.