Quick Overview

Count distinct values in a huge sorted random-access array without examining every element. Jump across equal-value runs with binary search to target O(d log n) time and O(1) auxiliary space when distinct values are sparse.

Count Distinct Values in a Huge Sorted Array

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement `count_distinct_sorted(values)` for a very large ascending array that supports random access. Equal values appear in contiguous runs. Let `d` be the number of distinct values, and assume `d` is much smaller than the array length `n`. Return the number of distinct values without examining every array element. An empty array has zero distinct values. Target `O(d log n)` time and `O(1)` auxiliary space. ```hint Jump over an entire run Once you know the value at the start of a run, binary-search for the first later index holding a different value. ``` ```hint Count transitions, not elements Increment the result once per run, then continue from the first position after that run. ``` ### Discussion Extensions - Contrast the run-jumping method with a divide-and-conquer method that stops when both ends of a subarray are equal. - Explain why a divide-and-conquer implementation can still degrade to linear work when every value is distinct.

Quick Answer: Count distinct values in a huge sorted random-access array without examining every element. Jump across equal-value runs with binary search to target O(d log n) time and O(1) auxiliary space when distinct values are sparse.

Implement count_distinct_sorted(values) for an ascending random-access integer array. Equal values occupy contiguous runs. Return the number of distinct values, using binary search to jump past each run instead of examining every element. An empty array returns zero.

Constraints

  • 0 <= values.length <= 50.
  • values is sorted in nondecreasing order.
  • Each value is an integer from -3,000,000,000 through 3,000,000,000.
  • The input supports random access and must not be modified.

Examples

Input: ([],)

Expected Output: 0

Explanation: The empty array has no distinct values.

Input: ([5],)

Expected Output: 1

Explanation: A singleton forms one run.

Hints

  1. Once a run's first value is known, binary-search for the first later index that holds a different value.
  2. Increment the answer once per run, then continue from the first index after that run.

Loading coding console...