Validate Stack Sequences — Solution in Python, Java & C++
Validate Stack Sequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Validate Stack Sequences is a medium coding problem on arrays, simulation and stack, asked in Amazon, Google, Microsoft and Sprinklr interviews.
- Difficulty: Medium
- Topics: Arrays, Simulation, Stack
- Asked at: Amazon, Google, Microsoft, Sprinklr
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two integer arrays pushed and popped, each a permutation of the other with distinct values, return true if they could be the push and pop sequences of one initially empty stack.
Example 1
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Example 2
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.
Example 3
Input: pushed = [1], popped = [1]
Output: true
Constraints
1 <= pushed.length <= 30popped.length == pushed.lengthThe two arrays are permutations of each other with distinct values.
Hints for Validate Stack Sequences
Hint 1
Simulate: push the values in order, and after each push, pop greedily while the top matches the next value to pop.
Hint 2
The greedy pop is forced — if the top equals the next expected pop and you do not pop it now, you never can.
Hint 3
The sequences are valid exactly when the stack ends empty.
How to solve Validate Stack Sequences
Simulate: push in order and, after each push, pop greedily while the top matches the next expected pop. The sequences are valid iff the stack ends empty.
Approach
- For each
xinpushed, push it, then pop whiletop == popped[j], advancingj. - Return whether the stack is empty.
Why it works
If the top equals the next value to pop and you do not pop it now, it becomes buried and can never be popped in the right order, so the greedy pop is forced and the simulation is exact.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Values are distinct, so matching by value is unambiguous.
Reference solution
Python
def validateStackSequences(pushed, popped) -> bool:
stack = []
j = 0
for x in pushed:
stack.append(x)
while stack and j < len(popped) and stack[-1] == popped[j]:
stack.pop()
j += 1
return len(stack) == 0Java
public static boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new ArrayDeque<>();
int j = 0;
for (int x : pushed) {
stack.push(x);
while (!stack.isEmpty() && j < popped.length && stack.peek() == popped[j]) {
stack.pop();
j++;
}
}
return stack.isEmpty();
}C++
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
vector<int> stack;
int j = 0;
for (int x : pushed) {
stack.push_back(x);
while (!stack.empty() && j < (int) popped.size() && stack.back() == popped[j]) {
stack.pop_back();
j++;
}
}
return stack.empty();
}JavaScript
var validateStackSequences = function(pushed, popped) {
const stack = [];
let j = 0;
for (let i = 0; i < pushed.length; i++) {
stack.push(pushed[i]);
while (stack.length > 0 && j < popped.length && stack[stack.length - 1] === popped[j]) {
stack.pop();
j++;
}
}
return stack.length === 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure