Refiling the drawer cabinet

A hardware shop finds a part by walking down a cabinet, turning left for smaller numbers and right for larger. After a flood the drawers were refiled by somebody who checked each one against the drawer above it, which is not the rule.

The problem

Small parts live in a wall of drawers arranged as a branching index. Each drawer carries a stamped part number and hangs at most two drawers beneath it, one left and one right. The rule is stated over whole sides, not over neighbours: for any drawer, every number hanging anywhere on its left side is strictly smaller than its own, and every number on its right side is strictly larger. That is what makes the walk-down search work.

After the flood a temp refiled the wall, comparing each drawer only with the one it hangs from. Decide whether the cabinet as it stands obeys the rule at every drawer.

The cabinet arrives in compact level-order form — the top drawer, then each layer left to right, None where nothing hangs. A gap hangs nothing of its own, and trailing gaps are trimmed.

Input. cabinet — the cabinet in compact level-order form.

Output. True if the rule holds at every drawer, False otherwise.

Example.

cabinet = [50, 30, 70, None, 40, 60, 80]   ->  True

The left side of 50 holds 30 and 40, both smaller; the right side holds 70, 60 and 80, all larger, and those three are in order among themselves.

A second example, which the temp's method cannot catch:

cabinet = [50, 30, 70, None, 55, 60, 80]   ->  False

Drawer 55 hangs on the right of 30 and is larger than 30, so a parent check passes. But it sits on the left side of 50 while being larger than 50: a search for part 55 starts at 50, sees 55 is larger, turns right into the 70 side, and never reaches it. The part is in the cabinet and unfindable.

Constraints.

• 0 <= drawers <= 10^4
• 1 <= part number <= 10^9
• numbers may repeat, and a repeat is itself a breach of the rule
• the cabinet may be a single chain of drawers, 10^4 deep
• an empty cabinet obeys the rule

Hints

Approach

Brute force

For every drawer, walk its whole left side checking each number is smaller, then its whole right side checking each is larger. A drawer near the top scans nearly the entire cabinet, so the cost is O(n · h): about 10^8 comparisons for a 10^4-drawer chain, each number re-read once per drawer above it.

The insight

A drawer is not judged against the drawer above it but against the open range its whole ancestry leaves it: every left turn drops the ceiling, every right turn lifts the floor.

Each ancestor constrains a whole side, and a drawer lies on the side of every ancestor above it at once, so those constraints intersect into one interval — exactly what a search relies on. The interval carries down in a single pass: the drawer to the left inherits the same floor and this number as its ceiling, the drawer to the right inherits this number as its floor and the same ceiling. Testing a drawer against its own interval is O(1), so one visit per drawer settles the wall.

Algorithm

1. Rebuild the cabinet, queueing only real drawers so a gap claims no hanging slots.
2. Push the top drawer onto a stack with both bounds open.
3. Pop a drawer with its floor and ceiling. If its number is not strictly above the floor and strictly below the ceiling, answer False.
4. Push the left drawer with the same floor and this number as its ceiling, and the right drawer with this number as its floor and the same ceiling.
5. If the stack empties with no failure, answer True.

Complexity

Time O(n) — one interval test per drawer. Space O(h) for the stack: about 14 entries for a balanced cabinet of 10^4 drawers, 10^4 for a chain.

Solution

"""Refiling the drawer cabinet — carry an open range down instead of checking parents."""

from collections import deque


class Drawer:
    """One drawer: a stamped part number and the two drawers hung under it."""

    __slots__ = ("part", "left", "right")

    def __init__(self, part):
        self.part = part
        self.left = None
        self.right = None


def build(level_order):
    """Rebuild the cabinet from its compact level-order form."""
    if not level_order or level_order[0] is None:
        return None
    root = Drawer(level_order[0])
    queue = deque([root])
    i = 1
    while queue and i < len(level_order):
        # invariant: only real drawers are queued, so a gap never claims hanging slots
        node = queue.popleft()
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.left = Drawer(value)
                queue.append(node.left)
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.right = Drawer(value)
                queue.append(node.right)
    return root


def solve(cabinet):
    root = build(cabinet)
    if root is None:
        return True
    # None means the range is open on that side: no ancestor has closed it yet
    stack = [(root, None, None)]
    while stack:
        node, floor, ceiling = stack.pop()
        # invariant: every ancestor's rule about this drawer is folded into (floor, ceiling)
        if floor is not None and node.part <= floor:
            return False
        if ceiling is not None and node.part >= ceiling:
            return False
        if node.left is not None:
            stack.append((node.left, floor, node.part))    # a left turn drops the ceiling
        if node.right is not None:
            stack.append((node.right, node.part, ceiling))  # a right turn lifts the floor
    return True

TESTS = [
    (([50, 30, 70, None, 40, 60, 80],), True),
    (([50, 30, 70, None, 55, 60, 80],), False),
    (([20, 20],), False),
    (([40, 20, 60, 10, 45],), False),
    (([40, 20, None, 10, None, 5],), True),
    (([],), True),
    (([1000000000],), True),
]

Pitfalls

• Checking each drawer only against the one it hangs from. That is the temp's method, and it answers True for [50, 30, 70, None, 55, 60, 80], where 55 is misfiled against a drawer two levels above the one it breaks.
• Allowing equality. The rule is strict on both sides, so [20, 20] is False; <= accepts it, and the shop then finds only one of the two drawers.
• Starting with numeric bounds instead of open ones. Seeding the floor with -10**9 and the ceiling with 10**9 when part numbers run to 10^9 rejects a legal cabinet: [1000000000] answers False. Use a sentinel meaning "no bound yet".
• Recursing. The interval version reads well as a recursion, but the 10^4-drawer chain the constraints allow passes Python's default recursion limit of 1000 and raises RecursionError before it can answer.

Variants

• The pasted slips — the same check run as a walk: read an ordered cabinet left to right and the numbers must increase strictly.
• The BST invariant — the rule stated over subtrees, and what it buys at height 20 against height a million.