0801EasyTreeDepth-First SearchBinary Search TreeBinary Tree

Most Common Gauge Offset

Tracked in this browser only

Trains the technique from

LeetCode 501Find Mode in Binary Search Tree

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 calibration bench measures an integer offset, in tenths of a micron, for every gauge block it checks, and files each offset into an ordered tree. Repeats are kept, so the same offset can be filed many times over. The order rule is: for any filed offset, every offset in the branch to its left is less than or equal to it, and every offset in the branch to its right is greater than or equal to it.

The tree arrives as gauge, a level-order listing. Its first entry is the offset at the top of the tree. After that, the listing gives the left branch then the right branch of each offset already listed, in the order those offsets appear, writing null where a branch is empty. Slots below a null are never written down, and the trailing run of null entries is left off.

Work out how many times each distinct offset was filed. Return every offset whose count equals the highest count reached by any offset, listed in ascending order. Several offsets may be tied on the highest count, in which case all of them belong in the answer.

Examples

Example 1

Input: gauge = [4, 2, 7, 2, null, 7]
Output: [2, 7]

The tree holds the offsets 2, 2, 4, 7 and 7. Both 2 and 7 were filed twice while 4 was filed once, so the highest count is 2 and both offsets that reach it come back in ascending order.

Example 2

Input: gauge = [6, 6, 6, 6]
Output: [6]

All four filed offsets are 6, so 6 has a count of 4 and nothing else was filed at all.

Example 3

Input: gauge = [-3, -7, -3, -9, -5, -3]
Output: [-3]

The tree holds -9, -7, -5, -3, -3 and -3. The offset -3 was filed three times and every other offset once, so -3 is the only one at the highest count.

Constraints

The number of offsets filed in the tree is in the range [1, 10^4].
1 <= gauge.length <= 2 * 10^4
-10^5 <= gauge[i] <= 10^5
An entry of gauge that is null marks an empty branch rather than an offset.
gauge[0] is never null.

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 most_common_offsets(gauge: list[int | None]) -> list[int]:

Java

public int[] mostCommonOffsets(Integer[] gauge)

The intended approach

Time O(m) for a listing of m slots: one pass to wire the tables and one in-order walk in which every node is pushed and popped once.Space O(m) for the index tables, plus O(h) for the walk stack on a tree of height h and O(t) for the t tied offsets returned.

Wire the listing into left and right index tables with a queue sweep, then walk the tree in order using an explicit stack rather than recursion, so a tree that is one long strand cannot overflow anything. The order rule means the walk hands the offsets over from smallest to largest, so every repeat of one offset arrives in an unbroken block; keeping the length of the block in progress and the best block length seen so far is enough to grow the answer as the walk goes. Because the blocks arrive in increasing order of offset, the collected answer is already ascending.

Pythonentry point: most_common_offsets

def _decode(listing):
    """Compact level-order listing -> (values, left, right) index tables."""
    if not listing or listing[0] is None:
        return [], [], []
    left = [-1] * len(listing)
    right = [-1] * len(listing)
    queue = [0]
    head = 0
    slot = 1
    while head < len(queue) and slot < len(listing):
        here = queue[head]
        head += 1
        if slot < len(listing):
            if listing[slot] is not None:
                left[here] = slot
                queue.append(slot)
            slot += 1
        if slot < len(listing):
            if listing[slot] is not None:
                right[here] = slot
                queue.append(slot)
            slot += 1
    return list(listing), left, right


def _encode(values, left, right):
    """(values, left, right) index tables -> compact level-order listing."""
    if not values:
        return []
    out = [values[0]]
    order = [0]
    head = 0
    while head < len(order):
        here = order[head]
        head += 1
        for table in (left, right):
            kid = table[here]
            if kid == -1:
                out.append(None)
            else:
                out.append(values[kid])
                order.append(kid)
    while out and out[-1] is None:
        out.pop()
    return out

def most_common_offsets(gauge):
    values, left, right = _decode(gauge)
    # walk the tree in order with an explicit stack: an ordered tree hands the
    # offsets over sorted, so equal offsets arrive back to back and a running
    # count of the current block is enough
    stack = []
    here = 0 if values else -1
    best = 0
    run = 0
    prev = 0
    started = False
    out = []
    while stack or here != -1:
        while here != -1:
            stack.append(here)
            here = left[here]
        node = stack.pop()
        v = values[node]
        if started and v == prev:
            run += 1
        else:
            run = 1
        prev = v
        started = True
        if run > best:
            best = run
            out = [v]
        elif run == best:
            out.append(v)
        here = right[node]
    return out

The obvious version

Ignore the shape of the tree completely: the filed offsets are exactly the non-null entries of the listing, so tally them in a dictionary, find the highest count, and return the sorted keys that reach it.

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_most_common_offsets(gauge):
    tally = {}
    for v in gauge:
        if v is None:
            continue
        tally[v] = tally.get(v, 0) + 1
    top = max(tally.values())
    return sorted(v for v in tally if tally[v] == top)

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 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