LeetCode 946 - Validate Stack Sequences

This problem asks whether two sequences of integers, pushed and popped, could represent valid operations on a stack.

leetcodemediumarraystacksimulation

LeetCode Problem 946

Difficulty: 🟡 Medium
Topics: Array, Stack, Simulation

Solution

Problem Understanding

This problem asks whether two sequences of integers, pushed and popped, could represent valid operations on a stack. The pushed array represents the order in which elements are pushed onto an initially empty stack, while the popped array represents the order in which elements are popped from the stack. The task is to determine if the popped sequence could occur given the pushed sequence, following standard stack behavior: Last-In-First-Out (LIFO).

The key constraints are that all values in pushed are distinct, popped is a permutation of pushed, and the length of both arrays is equal and can be up to 1000. This guarantees we do not have repeated values and that every pushed element must eventually be popped. Edge cases include sequences where the stack is popped immediately after pushing each element, sequences where all pushes happen before any pops, and mismatched sequences where the order of popping violates LIFO.

Approaches

A brute-force approach would try all possible sequences of push and pop operations on a stack to see if it can produce the popped sequence. While correct, this approach is exponential in time complexity because it explores all permutations of push/pop operations, which is infeasible for input sizes up to 1000.

The key observation for an optimal solution is that we can simulate the stack behavior directly. We iterate through pushed, pushing elements onto a simulated stack, and at each step, we check if the top of the stack matches the next element in popped. If it does, we pop from the stack. This continues until all elements are processed. This simulation guarantees correctness because it mimics exactly how a stack behaves and ensures that we do not violate LIFO order.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Explore all push/pop sequences; infeasible for n=1000
Optimal O(n) O(n) Simulate stack and validate popped order

Algorithm Walkthrough

  1. Initialize an empty stack and a pointer i to track the position in the popped array.
  2. Iterate through each element x in pushed. Push x onto the stack.
  3. After each push, check whether the top of the stack equals popped[i]. If it does, pop the top element from the stack and increment i.
  4. Repeat step 3 until the top of the stack no longer matches popped[i].
  5. After processing all elements in pushed, check if the stack is empty. If it is, the popped sequence is valid; otherwise, it is not.

Why it works: The algorithm works because it maintains the invariant that the stack always reflects the current pushed elements that have not yet been popped. By always popping elements that match the next value in popped, we ensure that the sequence is valid according to LIFO order. If at the end any elements remain in the stack, it means the popped sequence could not have been achieved.

Python Solution

from typing import List

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        i = 0  # pointer for popped
        
        for x in pushed:
            stack.append(x)  # push element onto stack
            while stack and stack[-1] == popped[i]:
                stack.pop()  # pop from stack if top matches popped
                i += 1
        
        return not stack  # valid if stack is empty

In this implementation, stack simulates the real stack. We push each element from pushed and then immediately pop any elements that match the current target in popped. The while loop ensures we pop consecutive matches without missing any. Finally, an empty stack confirms that all pops were valid.

Go Solution

func validateStackSequences(pushed []int, popped []int) bool {
    stack := []int{}
    i := 0 // pointer for popped
    
    for _, x := range pushed {
        stack = append(stack, x)
        for len(stack) > 0 && stack[len(stack)-1] == popped[i] {
            stack = stack[:len(stack)-1] // pop from stack
            i++
        }
    }
    
    return len(stack) == 0
}

The Go version uses a slice as a stack. append simulates push, and slicing stack[:len(stack)-1] simulates pop. All logic mirrors the Python solution. Go does not have None issues or overflow concerns here since the problem guarantees integers within range.

Worked Examples

Example 1: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

Step Stack i (popped index) Action
push 1 [1] 0 1 != 4, continue
push 2 [1,2] 0 2 != 4, continue
push 3 [1,2,3] 0 3 != 4, continue
push 4 [1,2,3,4] 0 4 == 4, pop 4, i=1
push 5 [1,2,3,5] 1 5 == 5, pop 5, i=2
[1,2,3] 2 3 == 3, pop 3, i=3
[1,2] 3 2 == 2, pop 2, i=4
[1] 4 1 == 1, pop 1, i=5

Stack is empty, return true.

Example 2: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

Step Stack i Action
push 1 [1] 0 1 != 4
push 2 [1,2] 0 2 != 4
push 3 [1,2,3] 0 3 != 4
push 4 [1,2,3,4] 0 4 == 4, pop, i=1
[1,2,3] 1 3 == 3, pop, i=2
push 5 [1,2,5] 2 5 == 5, pop, i=3
[1,2] 3 2 != 1, cannot pop 1 yet

Stack not empty and cannot continue, return false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is pushed and popped at most once
Space O(n) Stack stores at most n elements

The algorithm is linear because we iterate through pushed once and only pop each element once. Space usage is linear to store the stack.

Test Cases

# Basic examples
assert Solution().validateStackSequences([1,2,3,4,5], [4,5,3,2,1]) == True  # valid sequence
assert Solution().validateStackSequences([1,2,3,4,5], [4,3,5,1,2]) == False # invalid

# Edge cases
assert Solution().validateStackSequences([1], [1]) == True  # single element
assert Solution().validateStackSequences([1,2], [2,1]) == True  # reverse order
assert Solution().validateStackSequences([1,2], [1,2]) == True  # same order
assert Solution().validateStackSequences([1,2,3], [3,2,1]) == True  # all popped after push
assert Solution().validateStackSequences([1,2,3], [1,3,2]) == True  # intermittent pops

# Stress test
assert Solution().validateStackSequences(list(range(1000)), list(range(999, -1, -1))) == True  # large reversed
Test Why
Basic valid Confirms normal sequences work
Basic invalid Checks detection of impossible sequences
Single element Minimum input edge case
Reverse order Ensures correct LIFO handling
Large reversed Validates efficiency on max input size

Edge Cases

The first edge case is a single-element sequence. It is trivial but can fail if the implementation assumes multiple elements for popping. The algorithm correctly handles it because the while loop still executes for one element.

The second edge case is sequences where every element is popped immediately after pushing. A naive implementation may assume multiple pushes before pops. The simulation approach handles this naturally due to the while loop that pops matching elements immediately.

The third edge case is sequences that almost match but violate LIFO order, like [1,2,3] pushed and [2,1,3] popped. The stack simulation detects that the next required pop does not match the top of the stack and correctly returns false.