## 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

1. Create an empty stack and push the first element of ``` pushed ``` array
2. Place two pointers on the ``` pushed ``` and ``` popped ``` array.
3. 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

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

Happy Coding, Enjoy Algorithms!