# Validate Stack Sequences — Day 85(Python)

Today’s question from Daily leetcode challenge — February edition. This question has been asked in Google interviews. Let us look into the problem statement.

946. Validate Stack Sequences

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.

Example 1:

`Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]Output: trueExplanation: 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: falseExplanation: 1 cannot be popped before 2.`

Constraints:

We have two input stack which contains few numbers. One of the stacks is the push, and the other is the popped. We need to validate both the push and pop stack.

We can use another stack, which will mimic the steps i.e. We will keep pushing numbers from the push stack until we reach the first element in the pop stack. Once we reach the topmost element in the pop stack, we will keep popping from our stack and the pop stack, until there is a mismatch. Whenever there is a mismatch, we will push the remaining elements from the push stack to our stack until the push stack’s topmost element is same as the pop stack’s topmost element. We keep repeating until the push is empty.

Once our push is empty, we need to check if there are any remaining elements in our stack. If there are remaining elements, it means that it is not a valid stack sequence hence return False.

Let us look into the code snippet.

`class StackSequenceValidator:    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:        my_stack = []        for num in pushed:            my_stack.append(num)            while((my_stack) and (my_stack[-1] == popped[0])):                my_stack.pop()                popped.pop(0)        return False if my_stack else True`

# Complexity analysis.

Time Complexity

Since we are pushing into our stack based on push stack, the time complexity is O(N).

Space Complexity

Since we are using a stack to validate our results, the space complexity s O(N)

## More from Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

## When is a site ready for test automation?

Get the Medium app