Find >n/3 elements in sorted array

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).

Find Values Occurring More Than n/3 Times in a Sorted Array

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)

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.

Solution

The key observations: (a) in a sorted array, equal values are contiguous; (b) at most two values can exceed n/3 (three would sum to more than n elements); (c) any block longer than n/3 must cover one of the fixed sampling indices n/3 and 2n/3, so only those two positions can host a qualifying value. Counting each candidate with lower_bound/upper_bound gives O(log n) time and O(1) space. Use the integer test 3*count > n to express 'strictly more than n/3' without floating point, and deduplicate candidates for all-equal arrays.

Overview

Because the array is sorted, all copies of any given value form one contiguous block. We exploit this: any value that occupies more than n/3 of the array must cover at least one of a small, fixed set of sampling positions. We binary-search the count of each sampled value and keep only those whose count exceeds n/3.

(1) At most two values can occur more than n/3 times

Suppose three distinct values each occurred strictly more than n/3 times. Their occurrences are disjoint (distinct values), so the total number of elements would be:

count1 + count2 + count3 > n/3 + n/3 + n/3 = n

That exceeds the array length n, a contradiction. Hence at most two values can occur more than n/3 times.

(2) Choosing candidate positions

Use the two 0-indexed sampling positions:

p1 = n / 3        (integer division)
p2 = 2 * n / 3

These split [0, n) into three segments, each of length about n/3. A contiguous block longer than n/3 cannot fit strictly between two consecutive sampling points, so every value with count > n/3 must cover at least one of A[p1] or A[p2]. Therefore the only values that can qualify are A[p1] and A[p2] — we never need to inspect any other position.

(3) Confirming counts with binary search

For a candidate value v, its total count is:

count(v) = upper_bound(A, v) - lower_bound(A, v)

where lower_bound returns the first index >= v and upper_bound returns the first index > v. Each is an O(log n) binary search. Compute the count for each distinct candidate and report it only if count(v) > n/3. Deduplicate so a value sampled at both positions (e.g., a single value dominating the whole array) is reported once.

Reference implementation (Python)

from bisect import bisect_left, bisect_right

def values_more_than_n_over_3(A):
    n = len(A)
    if n == 0:
        return []
    res = []
    seen = set()
    threshold = n / 3.0  # strictly greater than n/3
    for p in (n // 3, (2 * n) // 3):
        v = A[p]
        if v in seen:
            continue
        seen.add(v)
        cnt = bisect_right(A, v) - bisect_left(A, v)
        if cnt > threshold:
            res.append(v)
    return res

Notes:

• Comparing against n / 3.0 (float) gives the exact "strictly more than n/3" semantics; equivalently use the integer test 3 * cnt > n, which avoids floating point entirely.
• The candidate set is fixed at two positions, so the loop runs O(1) times.

(4) Edge cases

• n == 0: return empty list (handled by the early guard).
• n == 1 or n == 2: n // 3 == 0 and 2*n // 3 is 0 or 1, both valid indices; a single element trivially has count 1 > n/3 for n < 3, so it is correctly reported.
• All-equal array: both sampling positions hold the same value; the seen set deduplicates, and the single value is reported once.
• Block straddling a boundary: a qualifying block always covers a sampling position by the argument in (2), so it is always discovered.
• No qualifying value: the binary-search counts fail the threshold and the result is empty.

Complexity

• Time: a constant number of binary searches, each O(log n) ⇒ O(log n) overall.
• Space: a constant-size candidate/result set ⇒ O(1) extra space (the output list holds at most two values).