0217EasyArrayDivide and ConquerTreeBinary Search TreeBinary Tree

Balanced Marker Index

Tracked in this browser only

Trains the technique from

LeetCode 108Convert Sorted Array to 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 survey line carries pegs at known offsets from its datum, given as markers in strictly increasing order. An offset is signed: pegs behind the datum are negative.

Build a two-branch lookup tree over the pegs so that:

every peg sits at exactly one node and every node carries exactly one peg;
at any node, every peg in its left branch is below that node's own peg and every peg in its right branch is above it;
the tree is depth balanced, meaning that at every node the depths of its two branches differ by at most one.

More than one tree can meet those three rules, so build the single tree pinned down by this rule: the peg at a node is the middle peg of the stretch of markers that node covers, and when that stretch holds an even number of pegs, take the lower of its two middle pegs.

Return the tree as a listing read off one depth at a time, left to right. Slot 0 holds the top node. Each node that appears in the listing claims the next two free slots for its branches, the left branch first and the right branch second. A slot holding null carries no node and claims no slots of its own. Leave off any null slots at the end of the listing.

Examples

Example 1

Input: markers = [-6, 1, 4, 9]
Output: [1, -6, 4, null, null, null, 9]

The stretch of four pegs has 1 and 4 in the middle, so the top node takes the lower one, 1. Its left branch covers -6 alone and its right branch covers 4 and 9, where 4 is the lower of that pair's middles and 9 sits above it. Both branches of the top node are one deep and two deep, within the allowed gap.

Example 2

Input: markers = [2, 5, 7, 11, 14, 20, 23]
Output: [11, 5, 20, 2, 7, 14, 23]

Seven pegs give 11 as the middle peg, then 5 and 20 as the middles of the two halves, and the remaining four pegs fill the third depth. Every peg to the left of a node is below it and every peg to the right is above it.

Example 3

Input: markers = [8]
Output: [8]

One peg means one node with no branches, and the two empty slots after it fall at the end of the listing, so they are left off.

Constraints

1 <= markers.length <= 10^4
-10^4 <= markers[i] <= 10^4
markers is given in strictly increasing order

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

Java

public Integer[] balancedMarkerIndex(int[] markers)

The intended approach

Time O(n)Space O(n)

Because `markers` is already in order, the peg that a node must carry is fixed by the stretch it covers: take that stretch's middle peg, hand the pegs below it to the left branch and the pegs above it to the right branch, and repeat. The stretches are held on an explicit stack of (low, high) index pairs so nothing is copied and the interpreter's recursion limit is never involved, with each node recording the index of its two branch pegs. A second walk reads the finished tree depth by depth from a queue to produce the listing, dropping the empty slots that fall at the end.

Pythonentry point: balanced_marker_index

def balanced_marker_index(markers):
    n = len(markers)
    left = [-1] * n
    right = [-1] * n
    root = -1
    pending = [(0, n - 1, -1, 0)]
    while pending:
        lo, hi, parent, side = pending.pop()
        if lo > hi:
            continue
        mid = (lo + hi) // 2
        if parent < 0:
            root = mid
        elif side == 0:
            left[parent] = mid
        else:
            right[parent] = mid
        pending.append((lo, mid - 1, mid, 0))
        pending.append((mid + 1, hi, mid, 1))
    listing = []
    queue = [root]
    head = 0
    while head < len(queue):
        node = queue[head]
        head += 1
        if node < 0:
            listing.append(None)
            continue
        listing.append(markers[node])
        queue.append(left[node])
        queue.append(right[node])
    while listing and listing[-1] is None:
        listing.pop()
    return listing

The obvious version

Build real nodes by slicing the peg list around its middle entry and recursing on the two slices, then read the finished nodes off depth by depth. The slicing makes it O(n log n) and it allocates every subtree outright.

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_balanced_marker_index(markers):
    def build(vals):
        if not vals:
            return None
        mid = (len(vals) - 1) // 2
        return {"val": vals[mid], "l": build(vals[:mid]), "r": build(vals[mid + 1:])}

    root = build(list(markers))
    out = []
    queue = [root]
    head = 0
    while head < len(queue):
        node = queue[head]
        head += 1
        if node is None:
            out.append(None)
            continue
        out.append(node["val"])
        queue.append(node["l"])
        queue.append(node["r"])
    while out and out[-1] is None:
        out.pop()
    return out

How this problem was checked

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