0393MediumTreeDepth-First SearchBinary Search TreeBinary Tree

Repair the Swapped Labels

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 card index is filed as a search tree of distinct labels: for every card, every label in its left branch is smaller than the card's own and every label in its right branch is larger.

A clerk peeled the labels off exactly two cards and stuck each one on the other card. The shape of the index was not touched, only those two labels, and the index no longer files correctly.

The index arrives as shelf, a tier-by-tier listing. shelf[0] is the root card's label. The rest of the list is consumed two entries at a time, taking cards in the order they were listed: the next two entries are that card's left-branch and right-branch labels, and null means that branch is empty, so it contributes no entries of its own. Trailing nulls are omitted.

Swap the two labels back so the index files correctly again. Exactly one pair of labels can be exchanged to achieve this. Change the labels in place in shelf -- do not build a new listing and do not move any card -- and return shelf.

Examples

Example 1

Input: shelf = [20, 10, 30, null, 25, 15]
Output: [20, 10, 30, null, 15, 25]

The labels 25 and 15 trade places. Afterwards 15 sits in the right branch of 10 and below 20, and 25 sits in the left branch of 30 and above 20, so every branch holds the labels it should.

Example 2

Input: shelf = [2, 3, 1]
Output: [2, 1, 3]

The root 2 has 3 in its left branch and 1 in its right branch. Exchanging those two labels puts the smaller one on the left and the larger one on the right.

Example 3

Input: shelf = [8, 3, 5]
Output: [5, 3, 8]

The root's label 8 is larger than the 5 in its right branch. Exchanging them leaves 5 at the root, with 3 on its left and 8 on its right.

Example 4

Input: shelf = [1, 2]
Output: [2, 1]

The left branch holds 2 while the root holds 1, so the two labels trade places.

Constraints

The number of cards in the index is in the range [2, 1000].
-2^31 <= card label <= 2^31 - 1
All labels are distinct, and exactly two of them were exchanged.

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 recover_tree(shelf: list) -> list:

Java

public Integer[] recoverTree(Integer[] shelf)

The intended approach

Time O(n)Space O(n) for the rebuilt cards and the walk stack

Reading a correctly filed index from the leftmost card gives strictly increasing labels, so walk the index in filing order and look for a card whose label is smaller than the one before it. The first such drop identifies the earlier of the two mislabelled cards as the card before the drop; the later one is the card at the last drop found, which handles both the case where the two cards are neighbours in filing order and the case where they are far apart. Each card remembers which entry of `shelf` it came from, so the repair is two assignments into the given list. The walk runs off an explicit stack, so an index that is one long chain of 1000 cards is fine.

Pythonentry point: recover_tree

def _decode(shelf):
    if not shelf or shelf[0] is None:
        return None
    cards = [[shelf[0], None, None, 0]]
    order = [0]
    i = 1
    qi = 0
    while qi < len(order) and i < len(shelf):
        card = cards[order[qi]]
        qi += 1
        for slot in (1, 2):
            if i >= len(shelf):
                break
            label = shelf[i]
            pos = i
            i += 1
            if label is not None:
                cards.append([label, None, None, pos])
                card[slot] = len(cards) - 1
                order.append(len(cards) - 1)
    return cards


def recover_tree(shelf):
    # Time O(n) -- one rebuild pass and one in-order walk.
    # Space O(n) for the rebuilt cards and the walk stack.
    cards = _decode(shelf)
    if cards is None:
        return shelf
    first = None
    second = None
    prev = None
    stack = []
    cursor = 0
    while stack or cursor is not None:
        while cursor is not None:
            stack.append(cursor)
            cursor = cards[cursor][1]
        cursor = stack.pop()
        if prev is not None and cards[prev][0] > cards[cursor][0]:
            if first is None:
                first = prev
            second = cursor
        prev = cursor
        cursor = cards[cursor][2]
    if first is not None:
        a = cards[first][3]
        b = cards[second][3]
        shelf[a], shelf[b] = shelf[b], shelf[a]
    return shelf

The obvious version

Try exchanging every pair of labels in the listing and keep the first exchange whose index reads in increasing order from the leftmost card. Cubic in the number of cards, and it never reasons about where the fault is.

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 _decode2(shelf):
    if not shelf or shelf[0] is None:
        return None
    cards = [[shelf[0], None, None, 0]]
    order = [0]
    i = 1
    qi = 0
    while qi < len(order) and i < len(shelf):
        card = cards[order[qi]]
        qi += 1
        for slot in (1, 2):
            if i >= len(shelf):
                break
            label = shelf[i]
            pos = i
            i += 1
            if label is not None:
                cards.append([label, None, None, pos])
                card[slot] = len(cards) - 1
                order.append(len(cards) - 1)
    return cards


def _sorted_in_order(shelf):
    cards = _decode2(shelf)
    if cards is None:
        return True
    prev = None
    stack = []
    cursor = 0
    while stack or cursor is not None:
        while cursor is not None:
            stack.append(cursor)
            cursor = cards[cursor][1]
        cursor = stack.pop()
        if prev is not None and prev >= cards[cursor][0]:
            return False
        prev = cards[cursor][0]
        cursor = cards[cursor][2]
    return True


def bf_recover_tree(shelf):
    spots = [k for k, label in enumerate(shelf) if label is not None]
    for x in range(len(spots)):
        for y in range(x + 1, len(spots)):
            a = spots[x]
            b = spots[y]
            trial = list(shelf)
            trial[a], trial[b] = trial[b], trial[a]
            if _sorted_in_order(trial):
                shelf[a], shelf[b] = shelf[b], shelf[a]
                return shelf
    return shelf

How this problem was checked

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