Find >n/3 elements in sorted array

Q: Find >n/3 elements in sorted array

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.

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

Overview

Comments (0)