Stack - Validate Stack Sequences

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.

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

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.

Solution 1 - Using stack

In this approach, we are going to use a Stack to push element from pushed array, and when the elements from popped started matching, then pop eleemnts from the stack.

Let's look at an example with pushed = [1, 2, 3, 4, 5] and popped = [4, 5, 3, 2, 1]

example 1 with pushed = [1, 2, 3, 4, 5] and popped = [4, 5, 3, 2, 1]

Implementation steps:

First, we will create a variable pushedStack a Stack that we will use to store pushed array elements, and another variable popIndex that we will use as a pointer to point at popped array.
Next, loop through pushed array and push the elements into the stack, also using a while loop, check if the top of the stack element and the element at popIndex from popped array are same, if they are same keep popping up the elements from stack.
Given that, both pushed and popped arrays have same elements and they are of same length, by the end of above step, if sequence is valid, then the pushedStack will be empty, since we have popped all elements.
Finally, check if the stack is empty, if it is empty return true, otherwise return false.

import java.util.Stack; public class ValidateStackSequences { static boolean validateStackSequences(int[] pushed, int[] popped) { Stack<Integer> stackPushed = new Stack<>(); int popIndex = 0; for(int pushElement: pushed) { // 2, 1, 0 --- 1, 2, 0 ==> true stackPushed.push(pushElement); while(!stackPushed.isEmpty() && popIndex<popped.length && stackPushed.peek() == popped[popIndex]) { stackPushed.pop(); popIndex++; } } return stackPushed.isEmpty(); } public static void main(String[] args) { System.out.println(validateStackSequences(new int[]{1,2,3}, new int[]{3,2,1})); System.out.println(validateStackSequences(new int[]{1,2,3,4,5}, new int[]{4,5,3,2,1})); System.out.println(validateStackSequences(new int[]{1,2,3,4,5}, new int[]{4,3,5,1,2})); System.out.println(validateStackSequences(new int[]{2,1,0}, new int[]{1,2,0})); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input array pushed.
Space complexity: O(n).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: