We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Validate Stack Sequences

Number: 983

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, Yahoo, LinkedIn

Problem Description

Given two arrays, pushed and popped, determine if the popped array could be the result of a series of push and pop operations on an initially empty stack. Every element in pushed is unique, and popped is a permutation of pushed.

Key Insights

  • Use a stack to simulate the push and pop operations.
  • Iterate over the pushed array, pushing each element to the stack.
  • After each push, check if the top of the stack equals the current element in the popped array. If so, perform pop operations.
  • Continue this process until either all elements are processed or a mismatch occurs.
  • The simulation confirms the validity of the popped sequence if the stack is empty at the end.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements, as each element is pushed and popped at most once. Space Complexity: O(n) for the auxiliary stack used during the simulation.

Solution

We simulate the process using a stack:

  1. Initialize an empty stack and an index pointer for the popped array.
  2. Traverse the pushed sequence, pushing each element onto the stack.
  3. After each push, while the stack is not empty and the element on top of the stack equals the current element in popped (indicated by the index pointer), pop from the stack and increment the pointer.
  4. If all operations complete and the stack is empty, the sequence is valid; otherwise, it is not. The key trick is continuously comparing the top of the stack with the next element in popped and performing pop operations as long as they match.

Code Solutions

# Function to validate stack sequences using simulation with a stack.
def validateStackSequences(pushed, popped):
    # Initialize an empty stack.
    stack = []
    # Initialize pointer for popped array.
    popped_index = 0
    
    # Iterate through each element in the pushed array.
    for num in pushed:
        stack.append(num)  # Push the current element onto the stack.
        # Check if the current stack top matches the expected popped element.
        while stack and stack[-1] == popped[popped_index]:
            stack.pop()      # Pop the element from the stack.
            popped_index += 1  # Move to the next element in the popped sequence.
    
    # If the stack is empty, the sequence is valid.
    return not stack

# Example Usage
pushed = [1,2,3,4,5]
popped = [4,5,3,2,1]
print(validateStackSequences(pushed, popped))  # Expected output: True
← Back to All Questions