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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Validate Stack Sequences and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →