Find >n/3 elements in sorted array
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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 there can be at most two such values.
(
2) Describe how to choose candidate positions and confirm counts using binary searches (e.g., lower_bound/upper_bound).
(
3) Provide correctness and complexity analysis.
Quick Answer: This question evaluates understanding of frequency analysis in sorted arrays, combinatorial bounds on repeated elements, and algorithmic complexity constraints such as O(log n) time and O(1) extra space.