LC-0946 Medium LeetCode

946. Validate Stack Sequences

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 70% Topics: Array, Stack, Simulation

Reading material

Arrays & Hashing 12 min Stacks & Queues 11 min Simulation & Enumeration 9 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        """
        :type pushed: List[int]
        :type popped: List[int]
        :rtype: bool
        """
        i = 0
        s = []
        for v in pushed:
            s.append(v)
            while s and i < len(popped) and s[-1] == popped[i]:
                s.pop()
                i += 1
        return i == len(popped)

Solution from kamyu104/LeetCode-Solutions · MIT