## Validate Stack Sequences

**Difficulty: **Medium

#### Understanding The Problem

**Problem Statement**

Given two sequences `pushed`

and `popped`

with distinct values, write a program to return `true`

if and only if this could have been the result of a sequence of `push`

and `pop`

operations on an initially empty stack.

**Problem Note**

- pushed is a permutation of popped.
- pushed and popped have distinct values.

**Example 1**

```
Input: pushed = [5, 10, 15, 20, 25], popped = [20, 25, 15, 10, 5]
Output: 1
Explanation: We might do the following sequence:
push(5), push(10), push(15), push(20), pop() -> 20,
push(25), pop()-> 25, pop()-> 15, pop()-> 10, pop()-> 5
```

**Example 2**

```
Input: pushed = [5, 10, 15, 20, 25], popped = [20, 15, 25, 5, 10]
Output: 0
Explanation: 5 cannot be popped before 10.
```

#### Solution

To validate the `pushed`

and `popped`

operation on an empty stack, we can follow a **Greedy** approach. A stack performs two operations **push** to the top of the stack and **pop** from the top of the stack.

The sequence will be valid if we can perform push and pop operation such that all the values stored in the `pushed`

and `popped`

array will be exhausted without interfering with the sequence.

**How can we use a stack to solve this problem?**

The simpler way to proceed is to use an empty stack and start pushing the elements of the `pushed`

array sequentially in the stack and comparing every top element of the stack with the front element of the `popped`

array.

If the top element of the stack is at the front of the `popped`

array then we can pop the element from the stack and increment the `popped`

array pointer by one, otherwise, we can push the front element of the `pushed`

array in the stack and increment the popped array pointer by one. If in this process, all the elements of the `popped`

array gets exhausted, then our sequence is valid.

Try this problem here.

**Solution Step**

- Create an empty stack and push the first element of
`pushed`

array - Place two pointers on the
`pushed`

and`popped`

array. - Compare the top element of the stack with the front element of
`popped`

array

- If both of them are the same, then we have to pop the top element of the stack and increment the
`popped`

array pointer by one - If both of them are not the same, then we have to push the front element of
`pushed`

array into the stack and increment the`pushed`

array pointer by one

4. Repeat step 2 to 3, until the stack becomes empty.

**Pseudo Code**

```
bool validateStackSequences(int[] pushed, int[] popped) {
Stack stack
int j = 0
for (int i = 0 to i < pushed.size()) {
stack.push(pushed[i])
while (stack is not empty and stack.top() is popped[j]) {
stack.pop()
j = j + 1
}
}
if(stack is empty)
return true
else
return false
}
```

**Complexity Analysis**

Time Complexity: O(n)

Space Complexity: O(n)**(How?)**

**Critical Ideas To Think**

- We have used while loop inside a for loop, then how come the time complexity is O(n)? Answer: If we follow the logic of pseudocode, we are visiting each element of
`pushed`

and`popped`

array only once. - What will be the case when the stack will not be empty at the end? Answer: When we have an invalid sequence, the stack will not be empty at the end. Try the above example 2 on this pseudocode.
- How this is a greedy approach? Read here to learn about greedy algorithms.
- What does the variable
`j`

represent in the pseudocode? - Can we solve this problem by using a queue, instead of a stack?
- Will this approach work if the
`pushed`

array contains repeated elements?

#### Suggested Problems To Solve

- Activity selection problem
- Huffman coding
- Water connection problem
- Graph coloring

*Please comment down below if you have a better insight in the above approach.*

**Happy Coding, Enjoy Algorithms!**