1104MediumArrayStackSimulation

Could the Tube Have Run That Way

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 loading tube stacks crates one on top of another, and only the crate on top can be lifted out.

loaded gives the order the crates are put in and taken gives the order they come out. Every crate goes in once and comes out once, and the two lists name the same crates.

Pushes and lifts may be mixed in any way. Return true when some mixture of them produces both of those orders exactly, and false when none can.

Examples

Example 1

Input: loaded = [1, 2, 3], taken = [3, 2, 1]
Output: true

Push all three crates and then lift them off, top first.

Example 2

Input: loaded = [1, 2, 3, 4], taken = [1, 4, 2, 3]
Output: false

Crate 1 can be lifted straight away, leaving the tube empty. Reaching crate 4 next means pushing 2 and then 3 on top of it, so 3 has to come off before 2, while the list asks for 2 first.

Example 3

Input: loaded = [5, 4, 3, 2, 1], taken = [1, 2, 3, 4, 5]
Output: true

Push every crate first. They then come off in exactly the reverse order, which is what the list asks for.

Constraints

1 <= loaded.length <= 1000
0 <= loaded[i] <= 1000
no two crates in loaded are the same
taken.length == loaded.length
taken names the same crates as loaded

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 validate_stack_sequences(loaded: list[int], taken: list[int]) -> bool:

Java

public boolean validateStackSequences(int[] loaded, int[] taken)

The intended approach

Time O(n) over the crates.Space O(n) for the tube.

Never guess. At any moment, if the crate on top of the tube is the one the taken list wants next, lifting it is safe: leaving it in place buries it deeper under whatever is pushed on afterwards, so it could only come out later than the list asks. And if the top is not the crate wanted next, no lift is possible at all, so the only move left is to push the next crate in. That turns the whole question into a single walk. Push the crates in order, and after each push lift as many crates as the taken list will accept, comparing the top of the tube against the next crate wanted. Nothing is ever undone. When the pushes run out, whatever is still in the tube can no longer move, so the orders match exactly when every crate has been lifted. Each crate is pushed once and lifted at most once.

Pythonentry point: validate_stack_sequences

def validate_stack_sequences(loaded, taken):
    tube = []
    at = 0
    for crate in loaded:
        tube.append(crate)
        while tube and at < len(taken) and tube[-1] == taken[at]:
            tube.pop()
            at += 1
    return at == len(taken)

The obvious version

Search over the choices instead of committing to any. From a state given by how many crates have been pushed and what the tube holds, try pushing the next crate and try lifting the top when it matches the crate wanted next, and report success if any line of play empties the tube after every push. States already shown hopeless are remembered so they are not walked twice.

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_validate_stack_sequences(loaded, taken):
    n = len(loaded)
    dead = set()

    def walk(pushed, tube):
        out = pushed - len(tube)
        if out == n:
            return True
        key = (pushed, tube)
        if key in dead:
            return False
        dead.add(key)
        if pushed < n and walk(pushed + 1, tube + (loaded[pushed],)):
            return True
        if tube and tube[-1] == taken[out] and walk(pushed, tube[:-1]):
            return True
        return False

    return walk(0, ())

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