Quick Overview

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.

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.

Overview: 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

  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.

Loading coding console...

Show the approach

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)