Katkat
Back

Count Distinct Values in a Huge Sorted Array

LinkedInSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to optimize search operations in a sorted array by using binary search to skip redundant elements, achieving sub-linear time complexity relative to the total array size.

Problem Statement

Given a sorted array arr of size n (where n can be very large), write a function countDistinct(arr) that returns the total number of unique elements in the array. Since the array is huge, you should aim for a solution more efficient than a linear scan.

Constraints

  • n can be up to 10^9.
  • The array provides O(1) random access.
  • You should aim for a time complexity better than O(n).
  • Use O(1) auxiliary space.

Example

# Input
arr = [1, 1, 1, 2, 2, 5, 5, 5, 5, 8]
# Output: 4
# Explanation: The distinct elements are 1, 2, 5, and 8.

Implementation

Provide your implementation in the following function signature:

def countDistinct(arr):
    # Your code here

Edge Cases

  • Empty array: [] should return 0.
  • Array with all identical elements: [7, 7, 7] should return 1.
  • Array with all unique elements: [1, 2, 3] should return 3.

Hints

Hint 1

Instead of checking every index, can you find the index of the first occurrence of the next distinct element after the current one?

Hint 2

Consider using binary search to locate the 'upper bound' of the current value to jump directly to the start of the next distinct value range.

Hint 3

The total time complexity will be proportional to the number of distinct elements 'd' multiplied by the log of the array size 'n'.

Follow-up questions

  • What is the time complexity of your solution, and how does it compare to a linear scan when the number of distinct elements is small versus large?
  • How would your approach change if the array was not sorted, but you were allowed to use O(n) extra space?
  • If the array is distributed across multiple machines, how would you adapt your binary search strategy to minimize network communication?