# Validate Stack Sequences LeetCode Solution

Difficulty : Medium tiktokViews 94

## Problem Statement

Validate Stack Sequences LeetCode Solution – 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.```

## Explanation

We know that if an element has been popped.

All elements before it in the pop list must have been pushed after it.

lets use that as an invariant for our algorithm.

Given an element X in pushed, find its location in popped. Its location in popped tells us how many elements need to have been pushed before it. Lets denote that as N. we can now look at all elements in Pushed starting from X up to the Nth element after X, and the subset of elements in Popped before X (of size N). Recursively check those ranges together, but also the ranges that come after the Nth element in pushed, and after X in popped (together).

1. Iterate pushed array one by one.
2. for each iteration push the current element to the stack.
3. while the top of the stack is the same as popped array current element. remove a top element from the stack and increment j.
4. when the inner loop finishes it means we have removed all the possible elements from pushed array till the current element of the pushed stack.
5. once the outer loop finishes. it means the entire pushed array is exhausted and hence here stack must be empty if pushed and popped arrays are valid. ## Code

### Java Solution:

```class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
int j = 0;
for (int i = 0; i < pushed.length; i++) {
stack.push(pushed[i]);
while (!stack.isEmpty() && popped[j] == stack.peek()) {
j++;
stack.pop();
}
}
return stack.isEmpty();
}
}```

### C++ Solution:

```class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> st; // Create a stack

int j = 0; // Intialise one pointer pointing on popped array

for(auto val : pushed){
st.push(val); // insert the values in stack
while(st.size() > 0 && st.top() == popped[j]){ // if st.peek() values equal to popped[j];
st.pop(); // then pop out
j++; // increment j
}
}
return st.size() == 0; // check if stack is empty return true else false
}
};```

Translate »