Elements Occurring More Than n/3 Times in a Sorted Array
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a **sorted** (non-decreasing) integer array `nums` of length `n`, where `n >= 3`.
Return every distinct value that occurs **strictly more than `n / 3` times** in the array. Here `n / 3` is the exact (real-valued) one-third of the length, so a value qualifies only when its number of occurrences is greater than `n / 3` (for example, when `n = 5`, a value must appear at least 2 times, since `2 > 5/3 ≈ 1.667`; when `n = 7`, it must appear at least 3 times, since `3 > 7/3 ≈ 2.333`).
Return the qualifying values in **increasing order**. If no value qualifies, return an empty list.
### Input / Output
- Input: `nums`, a non-decreasing list of integers with `len(nums) >= 3`.
- Output: a list of the distinct values that occur strictly more than `n / 3` times, sorted in increasing order.
### Examples
```
Input: [1, 2, 3]
Output: []
Explanation: n = 3, threshold = 3/3 = 1. Each value occurs once, and 1 is not > 1.
Input: [1, 1, 2, 3, 4]
Output: [1]
Explanation: n = 5, threshold = 5/3 ≈ 1.667. Value 1 occurs 2 times (2 > 1.667).
Input: [1, 1, 2, 4, 4]
Output: [1, 4]
Explanation: n = 5, threshold ≈ 1.667. Both 1 and 4 occur 2 times.
Input: [1, 2, 3, 4, 5, 6, 7]
Output: []
Explanation: n = 7, threshold ≈ 2.333. No value occurs 3 or more times.
```
### Constraints
- `3 <= n <= 10^5`
- `nums` is sorted in non-decreasing order.
- Element values fit in a signed 32-bit integer.
- At most two distinct values can occur strictly more than `n / 3` times.
### Follow-up
The straightforward solution scans the array once in `O(n)` time. Improve this to run in **better than `O(n)` time** by exploiting the fact that the array is already sorted. (Hint: because the array is sorted, any value that occurs more than `n / 3` times forms a long contiguous run, so it must land on one of a small, fixed set of index positions; you can identify the candidate values directly and then count their occurrences with binary search.)
Quick Answer: This question evaluates a candidate's ability to design frequency-counting algorithms over sorted arrays, testing knowledge of majority-element patterns and their generalization to arbitrary thresholds. It probes whether a candidate can exploit array structure, such as sortedness, to move beyond a linear scan toward a more efficient approach using binary search. Such problems are common in coding interviews to assess algorithmic optimization and complexity analysis skills.
You are given a **sorted** (non-decreasing) integer array `nums` of length `n`, where `n >= 3`.
Return every distinct value that occurs **strictly more than `n / 3` times** in the array. Here `n / 3` is the exact (real-valued) one-third of the length, so a value qualifies only when its number of occurrences is greater than `n / 3` (for example, when `n = 5`, a value must appear at least 2 times, since `2 > 5/3 ≈ 1.667`; when `n = 7`, it must appear at least 3 times, since `3 > 7/3 ≈ 2.333`).
Return the qualifying values in **increasing order**. If no value qualifies, return an empty list.
### Input / Output
- Input: `nums`, a non-decreasing list of integers with `len(nums) >= 3`.
- Output: a list of the distinct values that occur strictly more than `n / 3` times, sorted in increasing order.
### Examples
```
Input: [1, 2, 3]
Output: []
Explanation: n = 3, threshold = 3/3 = 1. Each value occurs once, and 1 is not > 1.
Input: [1, 1, 2, 3, 4]
Output: [1]
Explanation: n = 5, threshold = 5/3 ≈ 1.667. Value 1 occurs 2 times (2 > 1.667).
Input: [1, 1, 2, 4, 4]
Output: [1, 4]
Explanation: n = 5, threshold ≈ 1.667. Both 1 and 4 occur 2 times.
Input: [1, 2, 3, 4, 5, 6, 7]
Output: []
Explanation: n = 7, threshold ≈ 2.333. No value occurs 3 or more times.
```
### Constraints
- `3 <= n <= 10^5`
- `nums` is sorted in non-decreasing order.
- Element values fit in a signed 32-bit integer.
- At most two distinct values can occur strictly more than `n / 3` times.
### Follow-up
The straightforward solution scans the array once in `O(n)` time. Improve this to run in **better than `O(n)` time** by exploiting the fact that the array is already sorted. Because the array is sorted, any value that occurs more than `n / 3` times forms a run longer than one third of the array, so it must cover index `n//3` or `2*n//3`. Read the two candidate values at those positions, then count each with binary search in `O(log n)`.
Constraints
- 3 <= n <= 10^5
- nums is sorted in non-decreasing order
- Element values fit in a signed 32-bit integer
- At most two distinct values can occur strictly more than n/3 times
Examples
Input: [1, 2, 3]
Expected Output: []
Explanation: n=3, threshold=1. Every value occurs once and 1 is not > 1.
Input: [1, 1, 2, 3, 4]
Expected Output: [1]
Explanation: n=5, threshold≈1.667. Only 1 occurs twice (2 > 1.667).
Input: [1, 1, 2, 4, 4]
Expected Output: [1, 4]
Explanation: n=5, threshold≈1.667. Both 1 and 4 occur twice; returned in increasing order.
Input: [1, 2, 3, 4, 5, 6, 7]
Expected Output: []
Explanation: n=7, threshold≈2.333. No value occurs 3 or more times.
Input: [5, 5, 5]
Expected Output: [5]
Explanation: Boundary n=3: 5 occurs 3 times and 3 > 1, so it qualifies.
Input: [-2, -2, -2, -1, -1, -1]
Expected Output: [-2, -1]
Explanation: n=6, threshold=2. Each of -2 and -1 occurs 3 times (3 > 2); negatives handled.
Input: [1, 1, 1, 1, 2, 2, 3]
Expected Output: [1]
Explanation: n=7, threshold≈2.333. 1 occurs 4 times (qualifies); 2 occurs only twice, exactly below the threshold.
Hints
- A value qualifies when its count c satisfies c > n/3. Avoid floating point: c > n/3 is equivalent to 3*c > n.
- Because the array is sorted, equal values form one contiguous run. A run longer than n/3 must contain index n//3 or index 2*n//3, so only nums[n//3] and nums[2*n//3] can be candidates.
- Deduplicate the (at most two) candidate values, count each occurrence with bisect_right - bisect_left, keep those with 3*count > n, and sort the survivors ascending.