Validate Stack Sequences

MediumStackstack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given two integer arrays pushed and popped of the same length. pushed has distinct values, and popped is a permutation of pushed. Starting from an empty stack, you must push the values of pushed in the given order, and you may pop the top of the stack at any moment (between pushes or after all pushes). Return true if some interleaving of pushes and pops removes the values in exactly the order given by popped, otherwise false. Aim for O(n) time.

Examples

Input: pushed = [1,2,3,4,5], popped = [3,2,5,4,1]
Output: true
Push 1, 2, 3 and pop 3, 2; push 4, 5 and pop 5, 4; finally pop 1.
Input: pushed = [1,2,3,4,5], popped = [3,1,2,5,4]
Output: false
After popping 3 the top of the stack is 2, so 1 cannot be popped next without first popping 2.

Constraints

  • 1 <= pushed.length <= 1000
  • 0 <= pushed[i] <= 1000
  • All values in `pushed` are distinct.
  • `popped.length == pushed.length` and `popped` is a permutation of `pushed`.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More stack problems