Validate Stack Sequences — Day 85(Python)

Photo by Bekir Dönmez on Unsplash

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: 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:

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

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)