Scale Engineer

Validate Stack Sequences

Med
#0900Time: O(N), where N is the length of the `pushed` and `popped` arrays. Each element is pushed and popped at most once.Space: O(N), as in the worst-case scenario (e.g., `pushed = [1,2,3]`, `popped = [3,2,1]`), the stack can hold all N elements.1 company
Data structures
ArrayStack
Companies
Apollo.io

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the entire push and pop process using an explicit stack data structure. We iterate through the pushed array, pushing each element onto our stack. After each push, we check if the top of the stack matches the next expected element in the popped array. If it does, we pop from the stack and advance our pointer in the popped array. We repeat this check until the stack is empty or the top doesn't match. Finally, if the entire popped sequence was valid, our stack should be empty at the end.

Algorithm

  • Initialize an empty stack st.
  • Initialize an index j = 0 for the popped array.
  • Iterate through each element x in the pushed array:
    • Push x onto the stack st.
    • While the stack st is not empty and its top element st.peek() is equal to popped[j]:
      • Pop from the stack st.
      • Increment j.
  • After the loop, if the stack st is empty, it means we have successfully simulated the sequence. Return true, otherwise return false.

Walkthrough

We use a java.util.Stack to mimic the operations. We also use a pointer, j, to keep track of our current position in the popped array. The logic directly follows the process of pushing elements from the pushed array and popping them whenever they match the sequence in the popped array. If at the end of this process the stack is empty, it means every pushed element was correctly popped, validating the sequence.

import java.util.Stack; class Solution {    public boolean validateStackSequences(int[] pushed, int[] popped) {        Stack<Integer> stack = new Stack<>();        int j = 0; // pointer for popped array        for (int x : pushed) {            stack.push(x);            while (!stack.isEmpty() && j < popped.length && stack.peek() == popped[j]) {                stack.pop();                j++;            }        }        return stack.isEmpty();    }}

Complexity

Time

O(N), where N is the length of the `pushed` and `popped` arrays. Each element is pushed and popped at most once.

Space

O(N), as in the worst-case scenario (e.g., `pushed = [1,2,3]`, `popped = [3,2,1]`), the stack can hold all N elements.

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Does not modify the input arrays.

Cons

  • Requires extra space proportional to the input size.

Solutions

public class Solution {    public bool ValidateStackSequences(int[] pushed, int[] popped) {        Stack < int > stk = new Stack < int > ();        int j = 0;        foreach(int x in pushed) {            stk.Push(x);            while (stk.Count != 0 && stk.Peek() == popped[j]) {                stk.Pop();                ++j;            }        }        return stk.Count == 0;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem