Skip to main content

0946 - Validate Stack Sequences (Medium)

https://leetcode.com/problems/validate-stack-sequences/

Problem Statement​

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.

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.

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.

Approach 1: Simulation​

We use stack to simulate. For each item in pushedpushed, we push it to the stack. If the top element of the stack matches the target element in poppedpopped, we pop that and increase the pointer in poppedpopped. At the end, return true if the stack is empty, return false if not.

Written by @wingkwong
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        for (auto i = 0, j = 0; i < pushed.size(); i++) {
            // push each item
            s.push(pushed[i]);
            // greedily pop from the stack
            // increase the pointer in popped
            while (!s.empty() && s.top() == popped[j]) s.pop(), j++;
        }
        // if there is no element in the stack, return true
        // else false
        return s.empty();
    }
};