< Back




946. Validate Stack Sequences

We're given to lists, pushed and popped, and we're asked to verify if these operations could've been
conducted on a real stack - if the operations conform to true stack operations. It's helpful that
the elements in the pushed list are unique - the popped list is a permutation of the pushed list.

Given this, we just simulate stack operations with the pushed and popped stack, verifying that
number of pop operations coincides with the number of elements in the popped list. We maintain a
counter, i, that we use to count the number of pop operations as well as index into the popped list
so we can keep track of the next number we expect to pop.

We pop items off the list when the top of the pushed stack is equal to the current element we expect
to be popped.

The solution is as follows:


  class Solution:
      def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
          i = 0
          stack = []

          for push in pushed:
              stack.append(push)

              while stack and stack[-1] == popped[i]:
                  stack.pop()
                  i += 1

          return i == len(popped)


_ Time Complexity:

  O(n) - We inspect all elements in the pushed list once.

_ Space Complexity:

  O(n) - We maintain a stack to create the result.