0310MediumArrayHash TableSortingCountingBoyer–Moore Majority Vote Algorithm

Frequent Ledger Adjustments

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def frequent_adjustments(entries: list[int]) -> list[int]:

Java

public List<Integer> frequentAdjustments(int[] entries)

The intended approach

Time O(n)Space O(1) beyond the returned list, which holds at most two values

At most two values can each occupy more than a third of the ledger, so carry two candidate slots with their own tallies. An entry matching a candidate bumps that tally, an entry arriving while a slot is empty claims the slot, and anything else cancels one unit from both tallies. Cancelling can only ever discard a value that was outnumbered, so any true qualifier ends up in a slot. A second pass counts the surviving candidates for real and keeps the ones above the threshold, then the answer is sorted.

Pythonentry point: frequent_adjustments

def frequent_adjustments(entries):
    # O(n) time: one voting pass, then one counting pass per surviving candidate.
    # O(1) space beyond the returned list, which holds at most two values.
    cand1 = None
    cand2 = None
    count1 = 0
    count2 = 0
    for v in entries:
        if cand1 is not None and v == cand1:
            count1 += 1
        elif cand2 is not None and v == cand2:
            count2 += 1
        elif count1 == 0:
            cand1 = v
            count1 = 1
        elif count2 == 0:
            cand2 = v
            count2 = 1
        else:
            count1 -= 1
            count2 -= 1
            if count1 == 0:
                cand1 = None
            if count2 == 0:
                cand2 = None
    need = len(entries) // 3
    out = []
    for cand in (cand1, cand2):
        if cand is None:
            continue
        hits = 0
        for v in entries:
            if v == cand:
                hits += 1
        if hits > need:
            out.append(cand)
    out.sort()
    return out

The obvious version

Tally every distinct value in a dictionary, then keep the values whose tally clears the threshold.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_frequent_adjustments(entries):
    tally = {}
    for v in entries:
        tally[v] = tally.get(v, 0) + 1
    need = len(entries) // 3
    return sorted(v for v, c in tally.items() if c > need)

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in