Skip to content

946. Validate Stack Sequences

Description

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.

Solutions

Solution 1: Stack Simulation

Thinking

Check whether \(\textit{popped}\) is a valid pop sequence for \(\textit{pushed}\). Values are unique, so push in given order and pop whenever the top matches the next needed pop. If every pop is consumed, the sequence is legal.

We iterate through the \(\textit{pushed}\) array. For the current element \(x\) being iterated, we push it into the stack \(\textit{stk}\). Then, we check if the top element of the stack is equal to the next element to be popped in the \(\textit{popped}\) array. If they are equal, we pop the top element from the stack and increment the index \(i\) of the next element to be popped in the \(\textit{popped}\) array. Finally, if all elements can be popped in the order specified by the \(\textit{popped}\) array, return \(\textit{true}\); otherwise, return \(\textit{false}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the \(\textit{pushed}\) array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stk = []
        i = 0
        for x in pushed:
            stk.append(x)
            while stk and stk[-1] == popped[i]:
                stk.pop()
                i += 1
        return i == len(popped)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stk = new ArrayDeque<>();
        int i = 0;
        for (int x : pushed) {
            stk.push(x);
            while (!stk.isEmpty() && stk.peek() == popped[i]) {
                stk.pop();
                ++i;
            }
        }
        return i == popped.length;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stk;
        int i = 0;
        for (int x : pushed) {
            stk.push(x);
            while (stk.size() && stk.top() == popped[i]) {
                stk.pop();
                ++i;
            }
        }
        return i == popped.size();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func validateStackSequences(pushed []int, popped []int) bool {
    stk := []int{}
    i := 0
    for _, x := range pushed {
        stk = append(stk, x)
        for len(stk) > 0 && stk[len(stk)-1] == popped[i] {
            stk = stk[:len(stk)-1]
            i++
        }
    }
    return i == len(popped)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function validateStackSequences(pushed: number[], popped: number[]): boolean {
    const stk: number[] = [];
    let i = 0;
    for (const x of pushed) {
        stk.push(x);
        while (stk.length && stk.at(-1)! === popped[i]) {
            stk.pop();
            i++;
        }
    }
    return i === popped.length;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn validate_stack_sequences(pushed: Vec<i32>, popped: Vec<i32>) -> bool {
        let mut stk: Vec<i32> = Vec::new();
        let mut i = 0;
        for &x in &pushed {
            stk.push(x);
            while !stk.is_empty() && *stk.last().unwrap() == popped[i] {
                stk.pop();
                i += 1;
            }
        }
        i == popped.len()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function (pushed, popped) {
    const stk = [];
    let i = 0;
    for (const x of pushed) {
        stk.push(x);
        while (stk.length && stk.at(-1) === popped[i]) {
            stk.pop();
            i++;
        }
    }
    return i === popped.length;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Solution {
    public bool ValidateStackSequences(int[] pushed, int[] popped) {
        Stack<int> stk = new Stack<int>();
        int i = 0;

        foreach (int x in pushed) {
            stk.Push(x);
            while (stk.Count > 0 && stk.Peek() == popped[i]) {
                stk.Pop();
                i++;
            }
        }

        return i == popped.Length;
    }
}

Comments