946. Validate Stack Sequences

1. Description

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

2. Example

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.

3. Note

• 0 <= pushed.length == popped.length <= 1000
• 0 <= pushed[i], popped[i] < 1000
• pushed is a permutation of popped.
• pushed and popped have distinct values.

4. Solutions

Stack

n = i_pushed.size()
Time complexity: O(n)
Space complexity: O(n)

We just try to imitate the process of push and pop

At every turn, we push a value in i_pushed’s order, and try to pop as more values as possible as i_popped’s order
Then, if two sequences are valid, the stack will be empty

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution
{
public:
    // bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
    bool validateStackSequences(vector<int> &i_pushed, vector<int> &i_popped)
    {
        stack<int> store;
        for(int i = 0, j = 0; i < i_pushed.size(); i++)
        {
            store.push(i_pushed[i]);

            while(!store.empty() && store.top() == i_popped[j])
            {
                store.pop();
                j++;
            }
        }

        return store.empty();
    }
};