# Solution For Validate Stack Sequences

The Validate Stack Sequences problem on LeetCode asks us to determine if a given sequence of push and pop operations on a given stack is valid. In other words, we need to check if after all the operations, the stack is empty.

To solve this problem, we can use a stack and simulate the given sequence of operations on it. For each operation in the input sequences, we check if it is a push or pop operation and perform the corresponding action on the stack.

If it is a push operation, we simply push the element to the top of the stack. If it is a pop operation, we check if the top of the stack contains the element to be popped. If it does, we pop the top element of the stack. If it doesn’t, the sequence is invalid.

At the end, we check if the stack is empty. If it is, the sequence is valid, otherwise it is invalid.

Here is the detailed solution in Python:

“`
def validateStackSequences(push: List[int], pop: List[int]) -> bool:
stack = [] i = 0 # Index for push sequence

``````for x in pop:
while not stack or stack[-1] != x:
# Push elements from push sequence to stack
# until the top of the stack is the element to be popped
if i >= len(push):
# We have exhausted all the elements in push
return False
stack.append(push[i])
i += 1

# At this point, the top of the stack is the element to be popped.
# Pop it and move on to the next element in the pop sequence.
stack.pop()

# Check if the stack is empty at the end
return not stack
``````

“`

The time complexity of this solution is O(N), where N is the total number of elements in the input sequences. This is because we need to perform at most N operations (push or pop) on the stack, each of which takes constant time. The space complexity is also O(N) because we are using a stack to simulate the sequence of operations.

## Step by Step Implementation For Validate Stack Sequences

```class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
// create a stack to store pushed elements
Stack stack = new Stack<>();

// use two pointers to track elements in pushed and popped arrays
int i = 0;
int j = 0;

// while we haven't reached the end of either array
while (i < pushed.length && j < popped.length) {
// push elements from pushed array onto the stack
// until we find the element that is equal to the
// next element in the popped array
while (i < pushed.length && pushed[i] != popped[j]) {
stack.push(pushed[i]);
i++;
}

// if we found a match, increment both pointers
if (i < pushed.length && j < popped.length && pushed[i] == popped[j]) {
i++;
j++;
}
}

// while there are still elements in the pushed array
while (i < pushed.length) {
// push all remaining elements onto the stack
stack.push(pushed[i]);
i++;
}

// pointer to track position in popped array
int k = 0;

// while the stack is not empty
while (!stack.isEmpty()) {
// pop the top element from the stack
int elem = stack.pop();

// if the element does not match the next element
// in the popped array, then the arrays are not
// valid stack sequences
if (elem != popped[k]) {
return false;
}

// otherwise, increment the pointer in the popped array
k++;
}

// if we get to this point, then the arrays are valid
// stack sequences
return true;
}
}```
```class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack = []
j = 0
for i in range(len(pushed)):
stack.append(pushed[i])
while stack and stack[-1] == popped[j]:
stack.pop()
j += 1
return j == len(popped)```
```/**
* @param {number[]} pushed
* @param {number[]} popped
* @return {boolean}
*/
var validateStackSequences = function(pushed, popped) {
// create a stack to store pushed elements
let stack = [];

// index for iterating over pushed and popped arrays
let i = 0;
let j = 0;

// iterate over pushed array
while (i < pushed.length) {
// push element into stack
stack.push(pushed[i]);
// if top of stack is same as next element in popped array,
// pop from stack and increment popped array index
if (stack[stack.length - 1] === popped[j]) {
stack.pop();
j++;
}
// increment pushed array index
i++;
}

// return true if stack is empty, false otherwise
return stack.length === 0;
};```
```class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
stack s;
int j = 0;
for (int i = 0; i < pushed.size(); i++) {
s.push(pushed[i]);
while (!s.empty() && s.top() == popped[j]) {
s.pop();
j++;
}
}
return s.empty();
}
};```
```public class Solution {
public bool ValidateStackSequences(int[] pushed, int[] popped) {
// create a stack to store pushed elements
Stack stack = new Stack();

// index for popped array
int j = 0;

// iterate through pushed array
for(int i = 0; i < pushed.Length; i++) {
// push element to stack
stack.Push(pushed[i]);

// if top of stack equals next element in popped array,
// pop element off stack and increment popped array index
while(stack.Count > 0 && stack.Peek() == popped[j]) {
stack.Pop();
j++;
}
}

// return true if stack is empty, false otherwise
return stack.Count == 0;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]