0150MediumTreeDepth-First SearchBinary Search TreeBinary Tree

Archive Index Order

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 records office hangs its drawers in a lookup tree. Every drawer is stamped with one signed shelf code, and a drawer may carry up to two drawers beneath it: one on its low hook and one on its high hook.

The office claims to file by a strict rule. Take any drawer in the tree. Every code in the branch hanging off that drawer's low hook must be smaller than the drawer's own code, and every code in the branch hanging off its high hook must be larger. A branch here means the drawer sitting on that hook together with every drawer hanging below it, at any depth. Because the comparisons are strict, no code can appear twice in a properly filed tree.

Because the harness passes plain JSON, the tree reaches you as the array drawers, read level by level from the top drawer downwards. The first entry is the top drawer's code. After that the entries arrive in pairs, giving the low-hook drawer and then the high-hook drawer of each drawer already listed, in that same level order. A hook carrying nothing is written null, and a null contributes no pair of its own. The array stops once nothing is left to describe, so null entries that would trail at the very end may be left off.

Return true when every drawer in the tree satisfies the filing rule, and false when at least one drawer does not.

Examples

Example 1

Input: drawers = [40, 25, 60, null, null, 55, 80]
Output: true

Below the top drawer the low branch holds only 25 and the high branch holds 55, 60 and 80, all above 40. Drawer 60 also splits its own hooks correctly at 55 and 80.

Example 2

Input: drawers = [40, 25, 60, null, null, 30, 80]
Output: false

Drawer 30 hangs on the low hook of 60, so it sits inside the high branch of 40, and every code in that branch has to exceed 40.

Example 3

Input: drawers = [12, 7, 12]
Output: false

The high hook repeats the top drawer's code. Codes on a high hook have to be strictly larger, so a tie breaks the rule.

Constraints

The number of drawers in the tree is in the range [1, 10^4].
-2^31 <= drawers[i] <= 2^31 - 1 for every entry that is not `null`.
A `null` entry marks a hook carrying nothing and contributes no pair of its own.

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 archive_index_order(drawers: list) -> bool:

Java

public boolean archiveIndexOrder(Integer[] drawers)

The intended approach

Time O(n)Space O(n)

A drawer cannot be judged against its own two hooks alone, because every drawer further up the tree also fences it in. Rebuild the drawers from the level-order array, then walk down from the top carrying an open range for each drawer: moving onto a low hook tightens the ceiling to the parent's code, and moving onto a high hook lifts the floor to the parent's code, while the limit inherited from further up travels along unchanged. A drawer whose code falls outside its range settles the answer immediately, so one traversal is enough.

Pythonentry point: archive_index_order

def archive_index_order(drawers):
    # Time: O(n) -- each drawer is rebuilt once and range-checked once.
    # Space: O(n) -- the rebuilt drawers plus the explicit traversal stack.
    if not drawers or drawers[0] is None:
        return True
    nodes = [{"code": drawers[0], "low": None, "high": None}]
    at = 0
    i = 1
    while at < len(nodes) and i < len(drawers):
        cur = nodes[at]
        at += 1
        for hook in ("low", "high"):
            if i >= len(drawers):
                break
            v = drawers[i]
            i += 1
            if v is not None:
                cur[hook] = {"code": v, "low": None, "high": None}
                nodes.append(cur[hook])
    stack = [(nodes[0], None, None)]
    while stack:
        cur, floor, ceiling = stack.pop()
        if floor is not None and cur["code"] <= floor:
            return False
        if ceiling is not None and cur["code"] >= ceiling:
            return False
        if cur["low"] is not None:
            stack.append((cur["low"], floor, cur["code"]))
        if cur["high"] is not None:
            stack.append((cur["high"], cur["code"], ceiling))
    return True

The obvious version

For every drawer in turn, gather the complete list of codes hanging off its low hook and off its high hook with a fresh recursive sweep, then test each gathered code against that drawer directly.

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_archive_index_order(drawers):
    if not drawers or drawers[0] is None:
        return True
    nodes = [[drawers[0], None, None]]
    at = 0
    i = 1
    while at < len(nodes) and i < len(drawers):
        cur = nodes[at]
        at += 1
        for slot in (1, 2):
            if i >= len(drawers):
                break
            v = drawers[i]
            i += 1
            if v is not None:
                cur[slot] = [v, None, None]
                nodes.append(cur[slot])

    def gather(node):
        if node is None:
            return []
        return [node[0]] + gather(node[1]) + gather(node[2])

    for node in nodes:
        for code in gather(node[1]):
            if code >= node[0]:
                return False
        for code in gather(node[2]):
            if code <= node[0]:
                return False
    return True

How this problem was checked

Reference solution executed against 20 test cases — 20 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