Validate Stack Sequences

Leetcode 946. Validate Stack Sequences

Problem

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.

Constraints:

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• All the elements of pushed are unique.
• popped.length == pushed.length
• popped is a permutation of pushed.

Source : Leetcode 946. Validate Stack Sequences

Solution

We need to validate a sequence of push and pop in a stack. The push sequence is given and also the pop sequence. Now, the question is which one should be popped after one or more push, right?

One straight forward solution could be to do permutations of push and pop sequences. For example, we can push the first element of pushed array (see below image of pushed and popped arrays) and then try to pop that element from stack and put that in a separate array. Or we can push the second element instead and pop.

This will give us a solution but will take a lot of computational effort.

What if we push an element from pushed array and see if that element is the first element of the popped array? If that is, we can move towards the second element (of popped array), pop the stack and push the next element of pushed array? If we continue this process and reach at the last of popped array, we can tell that the push and pop sequences are valid, right?

This way, we do not need to generate permutations of pushed and popped elements!

Let’s see how this will work in action. Below image is the initial state of our problem. We have taken an empty stack (named test_stack) to keep our pushed elements.

At the beginning, we will push the first element from pushed array. An index j will point to the first element of the popped array. After pushing the first element (from pushed), we will check if that element is the current element (pointed by j) of popped array or not. If it is, we will pop this element from our test_stack and move j forward. If not, we will continue pushing the next element to our test_stack.

(When we say push, we mean we push from pushed array to our test_stack)

Okay, so we pushed 1 to our stack and found that 1 is not the current element of popped.

In other words, popped[j] != test_stack.top(). So we will continue pushing.

Next, we will push 2 to stack.

Still, popped[j] != test_stack.top(). So we will continue pushing.

Next, we will push 3 to stack.

Still, popped[j] != test_stack.top(). So we will continue pushing.

Next, we will push 4 to stack.

Wait! Now, popped[j] == test_stack.top() (4 == 4)!

So, we will do two things now. We will pop 4 from our stack and move j forward and continue to check even after popping 4 from stack and moving j forward, if the current top element of our stack (3) is equal to the element pointed by j (5) or not. If not, we will start again to push the next element.

Now, we push the next element (5) to stack.

Now, again the top element of our stack is same as the current element of popped array. So, we will pop the top element from our stack and move j forward.

After moving j forward, it is pointing to 3 and the current top element of stack is also 3!

So, we pop it and move j forward.

After moving j forward, it is pointing to 2 and the current top element of stack is also 2!

So, we pop it and move j forward.

After moving j forward, it is pointing to 1 and the current top element of stack is also 1!

So, we pop it and move j forward.

At this point, j has finished its traversal to the entire popped array and j has now a value equal to the length of the popped array. This means, the pop sequence can be generated with the push sequence. In other words, the pushed and popped sequence is valid!

If you face difficulty understanding the explanation, please check the images again and think deep. If you still have difficulty, please write to us in the comment box which part was hard to fathom. We will reply you and will improve our explanation.

Code

C++

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        
        stack<int> test_stack; // a temporary stack to check validity of push pop sequence
        int j = 0;
        
        for(int i = 0; i < pushed.size(); i++)
        {
            test_stack.push(pushed[i]);
            
            while(!test_stack.empty() && j < popped.size())
            {
                if(test_stack.top() != popped[j])
                    break;
                else{
                    test_stack.pop(); //top element of test_stack is the cuurent element which was popped
                                      //so, we pop from test_stack
                    j++;              //and we move to the next element in popped array
                }
            }
        }
        if(j == popped.size())
            return true;
        return false;
    }
};

Time and Space Complexity

We need to go through both the arrays ones. So, we have an O(N) time complexity.

We also need an extra stack to save pushed elements temporarily. Which means, we have an O(N) space complexity.

Here N is the length of pushed or popped array. Both has the same length, right?

Conclusion

This is a problem in a difficulty range of between Easy and Medium (our opinion). But still, we might not have done a good job explaining the solution. If you find hard time understanding, please write a note to us in the comment box. We will definitely try to improve and will reply you!

Till our next post, Happy coding! 😀

Bonus – System Design!

ByteByteGo is by far the best system design resource found on the internet. They are growing like crazy!

We suggest you checkout their course if you really want to dive deep in system design and want to have a better interview.

Here is the link: ByteByteGo!

Disclaimer: this is a genuine suggestion, but we have some benefits too! We get commission if you buy their course. However, there are other courses online which we do not promote. Because we promote only things that are the best in our opinion and those we really feel like helpful for our audience.