Majority Element II
Real-world version: Frequent Ledger AdjustmentsThe statement here is our own: the same inputs, outputs and technique.
A stockroom keeps a ledger of manual corrections. entries[i] is the signed size of the i-th correction, negative when stock was written off and positive when stock was added back.
An auditor wants the correction sizes that dominate the ledger: every value that appears strictly more than n / 3 times, where n is the number of entries and the division is truncated toward zero. In other words, a value qualifies when its number of occurrences is greater than floor(n / 3).
Return the qualifying values sorted in ascending order. Return an empty list when no value qualifies. Solve it in O(n) time using only O(1) extra space beyond the list you return.
Examples
Example 1
- Input
- entries = [4, -1, 4, -1, 4, 2]
- Output
- [4]
There are 6 entries, so a value needs more than floor(6 / 3) = 2 occurrences. The value 4 appears 3 times and qualifies; -1 appears twice and 2 appears once, so neither does.
Example 2
- Input
- entries = [7, 7, 3, 3]
- Output
- [3, 7]
With 4 entries a value needs more than floor(4 / 3) = 1 occurrence. Both 7 and 3 appear twice, and the answer lists them in ascending order.
Example 3
- Input
- entries = [0, 0, 0, 1, 2, 3, 4, 5, 6]
- Output
- []
With 9 entries a value needs more than floor(9 / 3) = 3 occurrences. The value 0 appears exactly 3 times, which is not strictly more than 3, and every other value appears once.
Example 4
- Input
- entries = [-6]
- Output
- [-6]
One entry means a value needs more than floor(1 / 3) = 0 occurrences, and -6 appears once.
Constraints
- 1 <= entries.length <= 5 * 10^4
- -10^9 <= entries[i] <= 10^9
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def frequent_adjustments(entries: list[int]) -> list[int]:public List<Integer> frequentAdjustments(int[] entries)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 13 test cases: 13 passed
- Passed: 4 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's