Skip to main content

946. Validate Stack Sequences

medium

Given a push order and a pop order, decide if both could have come from operations on a single stack. A short, sharp simulation that tests stack intuition directly.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

Constraints

  • 1 <= pushed.length <= 1000
  • 0 <= pushed[i] <= 1000
  • All the elements of pushed are unique.
  • popped.length == pushed.length
  • popped is a permutation of pushed.

Examples

Example 1

Input
pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output
true

Explanation: We might do the following sequence: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1.

Example 2

Input
pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output
false

Explanation: 1 cannot be popped before 2.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Simulate. Walk through pushed and a pointer j into popped.

Hint 2

After each push, greedily pop while the stack top matches popped[j], advancing j.

Hint 3

At the end, if j reached popped.length (or equivalently the stack is empty), the sequence is valid.

Hint 4

Why greedy is safe: if the top equals popped[j], delaying the pop gains nothing — every later operation would still need this element gone first.

Solution approach

Reveal approach

Single-pass simulation. Maintain a stack and a pointer j = 0 into popped. For each x in pushed: push x. Then while the stack is non-empty and stack.top() == popped[j], pop and j++. After processing every push, return true iff j == popped.length (equivalently, the stack is empty). The greedy pop is correct because the next pop in the sequence has to happen at *some* point, and delaying it only adds more elements on top — which would block it. O(n) time and O(n) space. Each element is pushed and popped at most once.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • simulation
  • array

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

More Stacks practice problems

See all Stacks problems →