0803EasyTreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary Tree

Closest Pair of Shelf Clearances

Tracked in this browser only

Trains the technique from

LeetCode 783Minimum Distance Between BST Nodes

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 warehouse records the vertical clearance of every storage shelf, in millimetres, in a binary search tree keyed by the clearance: for any shelf in the tree, every clearance in the branch to its left is smaller and every clearance in the branch to its right is larger. No two shelves have the same clearance.

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

Two shelves are easy to mix up when their clearances are close together. Return the smallest difference in clearance between any two different shelves in the tree.

The tree always holds at least two shelves, so such a pair always exists.

Examples

Example 1

Input: clearances = [50, 10, null, null, 11]
Output: 1

The tree holds three shelves, of clearance 10, 11 and 50. The pair 10 and 11 sit 1 millimetre apart, and no pair sits closer than that.

Example 2

Input: clearances = [40, 3]
Output: 37

Only two shelves are recorded, so the single available pair is 3 and 40 and the answer is their difference.

Example 3

Input: clearances = [9, 7, null, 5, null, 3, null, 1]
Output: 2

Every shelf here hangs off the left branch of the one above it, giving clearances 9, 7, 5, 3 and 1. Several pairs sit 2 millimetres apart and none sits closer.

Constraints

The number of shelves in the tree is in the range [2, 100].
2 <= clearances.length <= 200
0 <= clearances[i] <= 10^5
An entry of clearances that is null marks an empty branch rather than a shelf.
clearances[0] is never null, and no clearance appears twice.

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

Java

public int closestClearanceGap(Integer[] clearances)

The intended approach

Time O(m) for a listing of m slots: one sweep to wire the tables and one ordered walk that touches each shelf once.Space O(m) for the index tables, plus O(h) for the stack on a tree of height h.

A queue sweep turns the listing into left and right index tables. Because the tree is ordered, the walk that descends every left link, takes the node, then steps once to the right delivers the clearances in ascending order, and in ascending order the smallest difference can only fall between two neighbours. So carry the previous clearance through that walk and keep the smallest step. The walk is driven from an explicit stack, so a hundred-shelf chain costs no interpreter recursion.

Pythonentry point: closest_clearance_gap

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 closest_clearance_gap(clearances):
    # Wire the listing into index tables, then run the ordered walk from an explicit
    # stack: descend every left link, take the node, descend once to the right. That
    # hands the clearances over in ascending order, so only each neighbouring pair in
    # that order can hold the smallest gap.
    # Time O(m) for a listing of m slots, space O(m) for the tables plus O(h) stack.
    values, left, right = _decode(clearances)
    best = None
    prev = None
    stack = []
    here = 0 if values else -1
    while stack or here != -1:
        while here != -1:
            stack.append(here)
            here = left[here]
        node = stack.pop()
        if prev is not None:
            gap = values[node] - prev
            if best is None or gap < best:
                best = gap
        prev = values[node]
        here = right[node]
    return best

The obvious version

Never build a tree: the shelves are exactly the non-null entries of the listing. Measure every unordered pair of them and keep the smallest absolute difference.

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_closest_clearance_gap(clearances):
    marks = [v for v in clearances if v is not None]
    best = None
    for i in range(len(marks)):
        for j in range(i + 1, len(marks)):
            gap = marks[i] - marks[j]
            if gap < 0:
                gap = -gap
            if best is None or gap < best:
                best = gap
    return best

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