https://leetcode.com/problems/validate-stack-sequences

Let us use iterate through pushed and popped and on each step we decide what we need to do. Consider example pushed = [1, 2, 3, 4, 5], popped = [4, 5, 3, 2, 1]. Let ind1 and ind2 be indexes in these lists.

  1. ind1 = 0 and ind2 = 0. Stack is empty so far, so all we can do is to push elements, so stack = [1] now, increment ind1.
  2. ind1 = 1 and ind2 = 0. We check if we can pop element from stack right now. The reason that we want to pop as soon as possible, that all elements in popped (and pushed) are different, so if we miss the moment of time when we need to pop, we never do it after. So we check condition stack and stack[-1] == popped[ind2] and if it is false, we pop element. It is not the case here, so we push element to stack and increment ind1, stack = [1, 2].
  3. ind1 = 2 and ind2 = 0, similar logic, increment ind1 and stack = [1, 2, 3].
  4. ind1 = 3 and ind2 = 0, similar logic, increment ind1 and stack = [1, 2, 3, 4].
  5. ind1 = 4 and ind2 = 0. Now, we have popped[ind2] = 4, which is equal to the top of our stack, so we pop it from stack and increment ind2, stack = [1, 2, 3].
  6. ind1 = 4 and ind2 = 1. We increment ind1 and stack = [1, 2, 3, 5].
  7. ind1 = 5 and ind2 = 1. Top of stack equal to popped[ind2], so we pop element and increment ind2, stack = [1, 2, 3]
  8. ind1 = 5 and ind2 = 2. Same logic, we increment ind2 and stack = [1, 2]
  9. ind1 = 5 and ind2 = 3. Same logic, we increment ind2 and stack = [1] 10.ind1 = 5 and ind2 = 4. Same logic, we increment ind2 and stack = [] 11.ind1 = 5 and ind2 = 5, so we do not go inside while statement.

Note also, that we need to ckeck condition ind1 < n, that is we can push element to stack. If not, then we can immedietly return False. In the end, if we reached it we return True.

Complexity: time complexity is O(n): we traverse each of given list at most once. In the process stack and grow up to O(n) as well, so space complexity is also O(n).

class Solution:
    def validateStackSequences(self, pushed, popped):
        ind1, ind2, n = 0, 0, len(pushed)
        stack = []
        while ind1 < n or ind2 < n:
            if stack and stack[-1] == popped[ind2]:
                stack.pop()
                ind2 += 1
            elif ind1 < n:
                stack.append(pushed[ind1])
                ind1 += 1
            else:
                return False
        
        return True

If you like the solution, you can upvote it on leetcode discussion section: Problem 0946