{x}
blog image

Validate Stack Sequences

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.

 

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

 

Constraints:

  • 1 <= pushed.length <= 1000
  • 0 <= pushed[i] <= 1000
  • All the elements of pushed are unique.
  • popped.length == pushed.length
  • popped is a permutation of pushed.

Solution Explanation: Validate Stack Sequences

This problem asks whether two arrays, pushed and popped, represent a valid sequence of push and pop operations on a stack. The core idea is to simulate the stack operations using a stack data structure.

Algorithm:

  1. Initialization: Create an empty stack stk. Initialize an index i to 0, pointing to the beginning of the popped array. This index tracks which element of popped we expect to encounter next.

  2. Iteration: Iterate through the pushed array. For each element x in pushed:

    • Push x onto the stack stk.
    • Pop while possible: While the stack is not empty and the top element of the stack matches popped[i], pop the top element from the stack and increment i. This simulates popping elements from the stack as long as they match the expected sequence in popped.

  3. Validation: After iterating through pushed, if i equals the length of popped, it means we successfully popped all the elements in the correct order. Therefore, return true. Otherwise, return false.

Time Complexity: O(N) - We iterate through the pushed array once, and the popping operation in the while loop takes at most O(N) time in the worst-case scenario (where all pushes are followed by pops). However, each element is pushed and popped at most once, resulting in a linear time complexity.

Space Complexity: O(N) - In the worst case, the stack stk can hold all elements of pushed if no pops happen before the end of the iteration.

Code Examples:

The provided code solutions in multiple languages effectively implement this algorithm. They all follow the same structure:

  1. Initialize a stack (using appropriate data structures in each language).
  2. Iterate through pushed, pushing each element onto the stack.
  3. Inside the main loop, use a while loop to simulate popping as long as the top of the stack matches the next expected element in popped.
  4. Finally, check if i (the index into popped) has reached the end of popped to determine validity.

Example Walkthrough (Python):

Let's trace Example 1 (pushed = [1,2,3,4,5], popped = [4,5,3,2,1]):

  1. stk is empty, i is 0.
  2. Push 1: stk = [1].
  3. Push 2: stk = [1, 2].
  4. Push 3: stk = [1, 2, 3].
  5. Push 4: stk = [1, 2, 3, 4]. The while loop executes: stk.top() (4) == popped[i] (4), so pop 4, stk = [1, 2, 3], i = 1.
  6. Push 5: stk = [1, 2, 3, 5]. The while loop executes: stk.top() (5) == popped[i] (5), so pop 5, stk = [1, 2, 3], i = 2.
  7. ...and so on. The loop continues until i reaches 5 (the length of popped), indicating a valid sequence.

The other language examples follow the same logic using their respective stack implementations. The key is the efficient simulation of push and pop operations based on the input arrays.