Quick Overview

This TikTok software-engineer screen asks you to return every value occurring strictly more than n/3 times in a sorted array, in O(log n) time and O(1) space. The solution proves at most two such values can exist, samples the fixed positions n/3 and 2n/3, and confirms each candidate's count with lower_bound/upper_bound binary searches. It tests frequency reasoning on sorted data, combinatorial bounds, and rigorous complexity and edge-case analysis.

Find >n/3 elements in sorted array

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Given a **sorted (non-decreasing)** integer array `A` of length `n`, return all distinct values that occur **strictly more than `n/3` times**. Design an algorithm that runs in **O(log n)** time and uses **O(1)** extra space. Answer the following: 1. Prove that there can be **at most two** such values. 2. Describe how to choose **candidate positions** and confirm each candidate's count using binary searches (e.g., `lower_bound` / `upper_bound`). 3. Provide a **correctness argument** and **time/space complexity** analysis. 4. Handle edge cases (e.g., `n < 3`, empty array, runs that straddle the boundary positions, all-equal arrays).

Quick Answer: This TikTok software-engineer screen asks you to return every value occurring strictly more than n/3 times in a sorted array, in O(log n) time and O(1) space. The solution proves at most two such values can exist, samples the fixed positions n/3 and 2n/3, and confirms each candidate's count with lower_bound/upper_bound binary searches. It tests frequency reasoning on sorted data, combinatorial bounds, and rigorous complexity and edge-case analysis.

Given a sorted (non-decreasing) integer array `A` of length `n`, return all distinct values that occur strictly more than `n/3` times. Return the qualifying values in the order they first appear in the array. Because the array is sorted, equal values form one contiguous block, and at most two distinct values can exceed the `n/3` threshold (three would sum to more than `n` elements). Aim for O(log n) time and O(1) extra space by sampling the two fixed positions `n/3` and `2*n/3`: any block longer than `n/3` must cover at least one of these positions. Confirm each candidate's count with binary search (`lower_bound` / `upper_bound`). Use the integer test `3 * count > n` to express "strictly more than n/3" without floating point, and deduplicate candidates so an all-equal array reports its value once. Examples: - A = [1, 2, 2, 2, 3] -> [2] (2 appears 3 times, 3 > 5/3) - A = [1, 1, 1, 2, 2, 2, 3] -> [1, 2] - A = [1, 2, 3, 4, 5, 6] -> [] - A = [5, 5, 5, 5, 5, 5] -> [5]

Constraints

  • 0 <= n <= 10^6
  • A is sorted in non-decreasing order
  • -10^9 <= A[i] <= 10^9
  • At most two distinct values can satisfy the condition
  • Target O(log n) time and O(1) extra space (output excluded)

Examples

Input: ([1, 2, 2, 2, 3],)

Expected Output: [2]

Explanation: n=5, threshold count>5/3. 2 appears 3 times (3>5/3), so [2].

Input: ([1, 1, 1, 2, 2, 2, 3],)

Expected Output: [1, 2]

Explanation: n=7. 1 and 2 each appear 3 times (3>7/3); 3 appears once. Both qualify.

Hints

  1. In a sorted array, all copies of a value are contiguous, so each value's count is upper_bound(v) - lower_bound(v).
  2. If three distinct values each exceeded n/3, their disjoint counts would sum to more than n elements -- impossible. So at most two qualify.
  3. Any contiguous block longer than n/3 cannot fit strictly between consecutive thirds, so it must cover A[n/3] or A[2n/3]. Only those two positions can host a qualifier.
  4. Use the integer test 3 * count > n instead of count > n/3 to avoid floating point, and deduplicate the two sampled values for all-equal arrays.

Loading coding console...