946. Validate Stack Sequences

/**

 * 946. Validate Stack Sequences

 * Given two sequences pushed and popped with distinct values, 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.

 * 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

 */

See the solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/ValidateStackSequences.java

This is a rather simple question but is good practice for working with stack behavior and hence I have included it here.

The algorithm is:

  • Iterate through the elements in pushed array
  • If the element at top of stack matches the value in the popped array pop that element off of the stack
  • Otherwise add that element to stack
  • While push stack is not empty and its top matches the index of the popped array, continue popping elements from stack while incrementing the index of the popped array
  • If popped array index reaches the size of the popped array length then the stack sequences are valid, otherwise not.

Here is the code:

public boolean validateStackSequences(int[] pushed, int[] popped) {
    Stack<Integer> stack = new Stack<>();
    int popIndex = 0;
    for (int i =0; i < pushed.length; ) {
        if (!stack.isEmpty() && popped[popIndex] == stack.peek()) {
            stack.pop();
            popIndex++;
        } else {
            stack.push(pushed[i++]);
        }
    }
    while (!stack.isEmpty() && stack.peek() == popped[popIndex]) {
        stack.pop(); popIndex++;
    }
    return popIndex == popped.length;
}