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

• 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!