Show problems as
Classic problem #946MediumArrayStackSimulation

Validate Stack Sequences

Real-world version: Could the Tube Have Run That Way
Tracked in this browser only
Read Validate Stack Sequences on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def validate_stack_sequences(loaded: list[int], taken: list[int]) -> bool:
Java
public boolean validateStackSequences(int[] loaded, int[] taken)

More on the same topics