Validate Stack Sequences LeetCode Solution

Problem Statement

Validate Stack Sequences LeetCode Solution – 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.

Explanation

We know that if an element has been popped.

All elements before it in the pop list must have been pushed after it.

lets use that as an invariant for our algorithm.

Given an element X in pushed, find its location in popped. Its location in popped tells us how many elements need to have been pushed before it. Lets denote that as N. we can now look at all elements in Pushed starting from X up to the Nth element after X, and the subset of elements in Popped before X (of size N). Recursively check those ranges together, but also the ranges that come after the Nth element in pushed, and after X in popped (together).

1. Iterate pushed array one by one.
2. for each iteration push the current element to the stack.
3. while the top of the stack is the same as popped array current element. remove a top element from the stack and increment j.
4. when the inner loop finishes it means we have removed all the possible elements from pushed array till the current element of the pushed stack.
5. once the outer loop finishes. it means the entire pushed array is exhausted and hence here stack must be empty if pushed and popped arrays are valid.

Code

Java Solution:

class Solution {
   public boolean validateStackSequences(int[] pushed, int[] popped) {
    Deque<Integer> stack = new LinkedList<>();
    int j = 0;
    for (int i = 0; i < pushed.length; i++) {
      stack.push(pushed[i]);
      while (!stack.isEmpty() && popped[j] == stack.peek()) {
        j++;
        stack.pop();
      }
    }
    return stack.isEmpty();
  }
}

C++ Solution:

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st; // Create a stack
        
        int j = 0; // Intialise one pointer pointing on popped array
        
        for(auto val : pushed){
            st.push(val); // insert the values in stack
            while(st.size() > 0 && st.top() == popped[j]){ // if st.peek() values equal to popped[j];
                st.pop(); // then pop out
                j++; // increment j
            }
        }
        return st.size() == 0; // check if stack is empty return true else false
    }
};

Complexity Analysis for Validate Stack Sequences LeetCode Solution:

• Time Complexity:- BigO(N)
• Space Complexity:- BigO(N)