Skip to content

Latest commit

 

History

History

946

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 

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.

Companies:
Amazon, Microsoft, tiktok

Related Topics:
Array, Stack, Simulation

Solution 1.

// OJ: https://leetcode.com/problems/validate-stack-sequences/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int p = 0;
        for (int i : pushed) {
            s.push(i);
            while (s.size() && s.top() == popped[p]) {
                s.pop();
                ++p;
            }
        }
        return s.empty();
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/validate-stack-sequences/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1) extra space.
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int N = pushed.size(), i = 0, j = 0;
        for (int n : pushed) {
            pushed[i++] = n;
            while (i && pushed[i - 1] == popped[j]) --i, ++j;
        }
        return i == 0;
    }
};