Teaching Kids Programming – Greedy/Simulation Algorithm to Validate Stack Sequences

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

Example 1:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Constraints:
1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
All the elements of pushed are unique.
popped.length == pushed.length
popped is a permutation of pushed.

Greedy/Simulation Algorithm to Validate Stack Sequences

If current top of the stack is the next element to pop, we may just do it otherwise we will miss the chance as we would need to pop other elements before pop this:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        st = []
        i = 0
        for x in pushed:
            st.append(x)
            while st and i < len(popped) and st[-1] == popped[i]:
                i += 1
                st.pop()
        return len(st) == 0

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        st = []
        i = 0
        for x in pushed:
            st.append(x)
            while st and i < len(popped) and st[-1] == popped[i]:
                i += 1
                st.pop()
        return len(st) == 0

So, the idea is to use a stack, then we push each element as specified in the input, and whenever we see a match of top of the stack and next element to pop, we pop it (Greedy Algorithm). After all elements have been pushed to the stack, we check the stack status is empty then it is a valid stack sequence.

The time complexity is O(N) – the inner while loop at most executes N times.

–EOF (The Ultimate Computing & Technology Blog) —