946 Validate Stack Sequences

Link:  validate stack sequences

Thought

Its pretty straight forward, just stimulate a stack and push/pop as the sequence shows. 

Code

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        """
        :type pushed: List[int]
        :type popped: List[int]
        :rtype: bool
        """
        stack = []
        visited = set()
        N = len(popped)
        j = 0
        for i in pushed:
            stack.append(i)
            while stack and stack[-1] == popped[j] and j < N:
                stack.pop()
                j += 1
        if stack:
            return False
        return True

Runtime

Time: O(n)

Space: O(n)