Problem Description

You are given two integer arrays pushed and popped, where each array contains distinct values. These arrays represent a potential sequence of push and pop operations on a stack.

The pushed array represents the order in which elements were pushed onto a stack, and the popped array represents the order in which elements were popped from the stack.

Your task is to determine if the popped sequence is a valid result that could have been obtained by performing push and pop operations on an initially empty stack using the elements from pushed in the given order.

You need to return true if it's possible to achieve the popped sequence through valid stack operations, or false if it's impossible.

For example:

• If pushed = [1, 2, 3, 4, 5] and popped = [4, 5, 3, 2, 1], this is valid because:
  • Push 1, 2, 3, 4 → Pop 4
  • Push 5 → Pop 5
  • Pop 3, 2, 1

The key constraint is that you must push elements in the exact order given by pushed, but you can choose when to pop elements as long as you follow stack rules (last-in-first-out).

Intuition

To validate if a sequence of pops is possible, we need to simulate the actual stack operations. The key insight is that we must push elements in the exact order given by pushed, but we have flexibility in when we pop elements.

Think about how a stack works: when we push elements, they stack on top of each other. When we pop, we can only remove the top element. So at any point during the pushing process, we can check if the current top of the stack matches the next element we need to pop according to popped.

The strategy is straightforward:

• Push elements from pushed one by one onto a stack
• After each push, check if we can perform any pops that match the required order in popped
• Keep popping as long as the top of the stack matches the next required element in popped

For example, if we need to pop 4 next (according to popped), we keep pushing elements until 4 is at the top of the stack. Once it's there, we pop it and move to the next element in popped.

The process naturally handles all valid sequences because:

1. If an element needs to be popped early, it will be popped as soon as it reaches the top
2. If an element needs to be popped later, it will wait in the stack until all elements above it are popped first

If we successfully pop all elements in the order specified by popped, then the sequence is valid. We can verify this by checking if our pointer tracking the position in popped has reached the end of that array.

Learn more about Stack patterns.

Solution Approach

We implement the solution using stack simulation with a greedy popping strategy. Here's how the algorithm works:

1. Initialize data structures:

   • Create an empty stack stk to simulate the stack operations
   • Use a pointer i = 0 to track the current position in the popped array

2. Process each element in pushed:

   • For each element x in the pushed array:
     • Push x onto the stack with stk.append(x)
     • After pushing, immediately check if we can perform any valid pops

3. Greedy popping logic:

   • While the stack is not empty AND the top element equals popped[i]:
     • Pop the top element from the stack with stk.pop()
     • Increment the pointer i to move to the next element in popped
   • This greedy approach ensures we pop elements as soon as they match the required order

4. Validation:

   • After processing all elements in pushed, check if i == len(popped)
   • If i equals the length of popped, it means we successfully popped all elements in the required order, so return true
   • Otherwise, return false

The algorithm has a time complexity of O(n) where n is the length of the arrays, since each element is pushed and popped at most once. The space complexity is O(n) for the stack in the worst case when all elements are pushed before any pop occurs.

The key insight is that the greedy popping strategy is both necessary and sufficient - we must pop an element as soon as it appears at the top and matches the next required element in popped, otherwise we might miss the opportunity to pop it in the correct order later.

Example Walkthrough

Let's walk through a small example with pushed = [1, 2, 3, 4, 5] and popped = [4, 5, 3, 2, 1].

Initial State:

• Stack: []
• Pointer i = 0 (pointing to popped[0] = 4)

Step 1: Push 1

• Stack: [1]
• Check if top (1) equals popped[0] (4)? No, so don't pop
• i remains 0

Step 2: Push 2

• Stack: [1, 2]
• Check if top (2) equals popped[0] (4)? No, so don't pop
• i remains 0

Step 3: Push 3

• Stack: [1, 2, 3]
• Check if top (3) equals popped[0] (4)? No, so don't pop
• i remains 0

Step 4: Push 4

• Stack: [1, 2, 3, 4]
• Check if top (4) equals popped[0] (4)? Yes! Pop 4
• Stack: [1, 2, 3], i = 1 (now pointing to popped[1] = 5)
• Check if top (3) equals popped[1] (5)? No, stop popping

Step 5: Push 5

• Stack: [1, 2, 3, 5]
• Check if top (5) equals popped[1] (5)? Yes! Pop 5
• Stack: [1, 2, 3], i = 2 (now pointing to popped[2] = 3)
• Check if top (3) equals popped[2] (3)? Yes! Pop 3
• Stack: [1, 2], i = 3 (now pointing to popped[3] = 2)
• Check if top (2) equals popped[3] (2)? Yes! Pop 2
• Stack: [1], i = 4 (now pointing to popped[4] = 1)
• Check if top (1) equals popped[4] (1)? Yes! Pop 1
• Stack: [], i = 5

Final Check:

• i = 5 which equals len(popped) = 5
• Return true - the sequence is valid!

The key observation is that after pushing 4, we immediately pop it because it matches what we need. Then after pushing 5, we enter a chain of pops (5→3→2→1) as each exposed top element matches the next required element in the popped sequence.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the pushed array.

The algorithm iterates through each element in the pushed array exactly once using the outer for loop. Although there's a while loop inside, each element can only be pushed onto the stack once and popped from the stack once. Therefore, the total number of operations across the entire execution is at most 2n (each element is pushed once and popped at most once), which simplifies to O(n).

Space Complexity: O(n), where n is the length of the pushed array.

The space complexity is determined by the auxiliary stack stk used in the algorithm. In the worst-case scenario, all elements from the pushed array could be on the stack simultaneously before any popping occurs. This happens when the popped sequence requires all elements to be pushed first before any can be popped (for example, when popped is the reverse of pushed). Therefore, the maximum space required is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Check Stack Non-Empty Condition

A critical pitfall is accessing stack[-1] without first verifying the stack is non-empty. While the provided solution correctly includes stack and in the while condition, developers often forget this check when implementing the solution from scratch.

Incorrect Implementation:

# WRONG - May cause IndexError
while stack[-1] == popped[pop_index]:
    stack.pop()
    pop_index += 1

Correct Implementation:

# CORRECT - Checks stack is non-empty first
while stack and stack[-1] == popped[pop_index]:
    stack.pop()
    pop_index += 1

2. Index Out of Bounds for popped Array

Another common mistake is not checking if pop_index is within bounds before accessing popped[pop_index]. This can cause an IndexError when all elements have been successfully popped.

Incorrect Implementation:

# WRONG - May access popped[pop_index] when pop_index == len(popped)
while stack and stack[-1] == popped[pop_index]:
    stack.pop()
    pop_index += 1

Correct Implementation:

# CORRECT - Add boundary check for pop_index
while stack and pop_index < len(popped) and stack[-1] == popped[pop_index]:
    stack.pop()
    pop_index += 1

3. Using Wrong Validation Logic

Some developers mistakenly check if the stack is empty instead of checking if all elements in popped have been processed.

Incorrect Implementation:

# WRONG - Stack being empty doesn't guarantee all pops were successful
return len(stack) == 0

Correct Implementation:

# CORRECT - Verifies all elements in popped were matched
return pop_index == len(popped)

4. Not Understanding the Greedy Nature is Mandatory

A conceptual pitfall is thinking we have flexibility in when to pop elements. The greedy approach (popping immediately when possible) is not just an optimization—it's mandatory for correctness. Delaying a pop when it's possible will make it impossible to achieve certain valid sequences.

Example demonstrating why greedy is necessary:

• pushed = [1, 2], popped = [2, 1]
• If we don't pop 2 immediately after pushing it, we'd have stack [1, 2] after all pushes
• We'd then be forced to pop in order [2, 1], which matches our target
• But consider pushed = [1, 2, 3], popped = [2, 3, 1]
• If we don't pop 2 after pushing it, we get stack [1, 2, 3]
• Now we can't achieve the required pop order since 3 must come before 2