Find >n/3 elements in sorted array

Q: Find >n/3 elements in sorted array

This is a Coding & Algorithms interview question from TikTok for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

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(

extra space. Answer the following: (
Prove there can be at most two such values. (
Describe how to choose candidate positions and confirm counts using binary searches (e.g., lower_bound/upper_bound). (
Provide correctness and complexity analysis.

Find >n/3 elements in sorted array

Comments (0)