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
Solution
from typing import List
import bisect
def count_unique(nums: List[int]) -> int:
n = len(nums)
i = 0
distinct = 0
while i < n:
distinct += 1
val = nums[i]
# Jump to the first index greater than val (one past the last occurrence)
i = bisect.bisect_right(nums, val, i, n)
return distinct
Explanation
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).
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.