946. Validate Stack Sequences
Given two sequences
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.
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
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
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Explanation: 1 cannot be popped before 2.
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushedis a permutation of
poppedhave 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.
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
my_stack = 
for num in pushed:
while((my_stack) and (my_stack[-1] == popped)):
return False if my_stack else True
Since we are pushing into our stack based on push stack, the time complexity is O(N).
Since we are using a stack to validate our results, the space complexity s O(N)