Validate Stack Sequences

January 26, 2024

Problem Statement #

Given two sequences 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, otherwise false.

Example:

1. Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output: True Explanation: We can push 1, 2, 3, 4, and 5 and then pop them in the order [4,5,3,2,1].

Solution Approach #

The solution involves simulating the push and pop operations on a stack.

Algorithm Steps #

1. Initialize an empty stack and a pointer for the popped sequence.
2. Iterate through each element in the pushed sequence: a. Push the element onto the stack. b. While the stack is not empty and the top of the stack equals the current element at the popped pointer, pop from the stack and move the pointer.
3. After the iteration, if the stack is empty, return true; otherwise, return false.

Code (Python) #

def validateStackSequences(pushed, popped):
    stack = []
    pop_index = 0

    for num in pushed:
        stack.append(num)
        while stack and stack[-1] == popped[pop_index]:
            stack.pop()
            pop_index += 1

    return not stack

# Test the function
print(validateStackSequences([1,2,3,4,5], [4,5,3,2,1]))  # Output: True

Time Complexity #

O(n), where n is the number of elements in pushed and popped. Each element is processed once.

Space Complexity #

O(n), for the stack used in the simulation.