Validate Stack Sequences

Problem Statement

This task revolves around simulating stack operations with two given integer arrays, pushed and popped. Both arrays consist of distinct integers. The challenge is to determine if the sequence represented by the popped array could result from a series of push and pop operations on an initially empty stack, using the order specified in the pushed array. If the sequence can be validly achieved through stack operations, the function should return true, otherwise false.

Examples

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.

Approach and Intuition

The solution to this problem relies on understanding the nature of stack operations—specifically, Last In First Out (LIFO). We can simulate the stack process and validate if the popped sequence is feasible based on the pushed sequence.

Observations:

• Since the elements are unique and popped is a permutation of pushed, every element should appear once in both arrays.
• The key to the solution is to replicate the push and pop sequence and see if we can match the popped array.

Key Steps:

1. Initialize an empty stack.
2. Traverse through each element in the pushed array:
   • Push elements from pushed onto the stack.
   • After each push operation, check if the top element matches the next needed pop (the current element in popped). If it does, pop it from the stack. Continue this check in a loop (since consecutive pops might be in order) until the stack's top doesn't match popped or the stack is empty.
3. If after processing all elements, the stack is empty, then return true, signaling that it's possible to achieve the popped sequence. If not, return false.

Example Analysis:

Using Example 1 from the problem statement:

• pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
• Simulate operations:
  • Push [1,2,3,4]. When 4 is on top of the stack, and 4 is next in popped, pop it. Continue with similar operations for all elements.
  • Result: Stack operations match the popped sequence, so return true.

In Example 2, however:

• pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
• The sequence 1, 2 is problematic. As 1 is pushed before 2, 2 should be popped before 1, making this sequence unachievable by standard stack operations. Thus, the result is false.

Through accurately replicating the push and pop operations and constantly comparing with the popped sequence, the function can verify the feasibility of popped being a valid stack sequence derived from pushed.

Solutions

class Solution {
    public boolean isValidSequence(int[] pushed, int[] popped) {
        int len = pushed.length;
        Stack<Integer> tempStack = new Stack<>();
    
        int counter = 0;
        for (int value : pushed) {
            tempStack.push(value);
            while (!tempStack.isEmpty() && counter < len && tempStack.peek() == popped[counter]) {
                tempStack.pop();
                counter++;
            }
        }
    
        return counter == len;
    }
}