Problem of The Day: Validate Stack Sequences

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        i = j = 0
        N = len(pushed)
        while i < N and j < N:
            if not stack or stack[-1] != popped[j]:
                stack.append(pushed[i])
                i += 1
                continue
            else:
                stack.pop()
                j += 1

        while j < N:
            if stack[-1] != popped[j]:
                return False
            stack.pop()
            j += 1
        return not stack

Editorial

Approach 1: Greedy

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        j = 0
        stack = []
        for x in pushed:
            stack.append(x)
            while stack and j < len(popped) and stack[-1] == popped[j]:
                stack.pop()
                j += 1

        return j == len(popped)