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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Validate Stack Sequences

Difficulty: Medium

Problem Description

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.

Key Insights

  • The stack operates in a Last In First Out (LIFO) manner, meaning the last element pushed onto the stack is the first to be popped off.
  • We need to simulate the push and pop operations while ensuring that the operations respect the order specified in the popped array.
  • If at any point we encounter a situation where the next value to be popped cannot be obtained from the top of the stack, we can conclude that the sequence is invalid.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a stack data structure to simulate the push and pop operations. The approach involves iterating through the pushed array to push elements onto the stack. For each element in the popped array, we check if it can be popped from the stack. If it cannot be popped (i.e., the stack is empty or the top of the stack does not match the current popped element), we continue pushing from the pushed array until we can either pop the required element or exhaust the pushed array. If we successfully pop all elements in the popped array in the correct order, we return true; otherwise, we return false.

Code Solutions

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

    for value in pushed:
        stack.append(value)  # Push the value onto the stack
        while stack and stack[-1] == popped[j]:  # Check if the top of the stack matches the next popped value
            stack.pop()  # Pop from the stack
            j += 1  # Move to the next value in the popped array

    return j == len(popped)  # Check if we popped all values in order
← Back to All Questions