946. Validate Stack Sequences

link

We can decrease space complexity here. (not optimized)

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

        stack = []

        dq = deque(popped)

        for p in pushed:
            stack.append(p)

            while stack and dq and dq[0] == stack[-1]:
                stack.pop()
                dq.popleft()

        return len(dq) == 0