Skip to content

Validate Stack Sequences

🌀 Stack Permutations: A Unified Editorial

Stack permutations involve determining if a specific output sequence can be generated from an input sequence using a single stack. This converts a simulation problem into a structural validation problem.

We will explore two main approaches:

  • Simulation (Greedy): The standard \(O(N)\) approach using a stack data structure to mimic the push/pop operations.

  • Forbidden Pattern (Property Check): The \(O(1)\) space approach (conceptually \(O(N^2)\) time) that validates the mathematical properties of the permutation without using auxiliary memory.

📝 Problem Statement

Problem: Validate Stack Sequences

You are given a target permutation target of length \(N\) containing distinct integers from \(0\) to \(N-1\). You have an initially empty stack. You also have a stream of numbers from \(0\) to \(N-1\) arriving in increasing order.

At any point, you can perform two operations: 1. Push: Push the next available number from the input stream onto the stack. 2. Pop: Pop the top element from the stack and print it to the output sequence.

Return true if the target permutation can be generated using a valid sequence of push and pop operations, otherwise return false.

Input Example: target = [0, 3, 4, 2, 1] Output Example: true

Simulation Approach

These solutions typically rely on the LIFO (Last In, First Out) property. We greedily push elements until we match the target, then pop immediately.

1. 🏗️ Standard Simulation (Difficulty: Easy)

Logic: We maintain a pointer to the source number (current_source) we are ready to push. For every number x in the target sequence:

  • Push Phase: While current_source \(\le\) x, we push current_source onto the stack and increment the source pointer.

  • Pop Phase: Check if the top of the stack matches x.

    • If Match: Pop from the stack.

    • If No Match: The sequence is invalid (we need x, but it is buried beneath other elements or not yet available).

Dry Run (Example: 0 3 4 2 1):

  • Target 0: Push 0. Top is 0. Pop 0. Stack: [].

  • Target 3: Push 1, 2, 3. Top is 3. Pop 3. Stack: [1, 2].

  • Target 4: Push 4. Top is 4. Pop 4. Stack: [1, 2].

  • Target 2: Top is 2. Pop 2. Stack: [1].

  • Target 1: Top is 1. Pop 1. Stack: [].

  • Result: True.

Implementation (C++):

Click to expand solution code 
bool validateStackSequence(vector<int>& target) {
    stack<int> s;
    int current_source = 0;

    for (int x : target) {
        // Keep pushing onto stack until the top is x
        while (current_source <= x) {
            s.push(current_source);
            current_source++;
        }

        // Check if the top is what we need
        if (!s.empty() && s.top() == x) {
            s.pop();
        } else {
            return false;
        }
    }
    return true;
}

Pattern Validation Approach

To solve this without a stack data structure (optimizing Space to \(O(1)\)), we must verify the mathematical property of stack-sortable permutations.

2. 📉 The "3-1-2" Pattern (Difficulty: Medium)

Problem: Validate the sequence using O(1) auxiliary space (modifying the input array is not allowed).

The Mathematical Rule: A sequence is a valid stack permutation if and only if it does not contain a "3-1-2" pattern. Mathematically, for any indices \(i < j < k\): If target[i] (the "3") is the largest of the three, then we cannot have target[k] > target[j].

Simplified Rule: For any number X in the sequence, all numbers to its right that are smaller than X must appear in descending order.

Visualizing the Violation: Imagine the target is 0 3 4 1 2. Look at 4. The numbers to its right that are smaller are 1 and 2. Since 1 < 2, they are in ascending order. This is a violation.

  • When 4 was popped, 1 and 2 were in the stack.

  • Since 1 is pushed before 2, 2 is above 1 in the stack.

  • Therefore, 2 must be popped before 1.

Algorithm (In-Place Check): Iterate through the array with pointer i. For each target[i]:

  1. Scan all target[j] where \(j > i\).

  2. Filter for numbers where target[j] < target[i].

  3. Ensure these smaller numbers are strictly decreasing. If we find a smaller number that is larger than the previous smaller number, return False.

Implementation (C++):

Click to expand solution code 
bool validateStackSequenceO1(vector<int>& target) {
    int n = target.size();

    for (int i = 0; i < n; ++i) {
        int current = target[i];
        int last_smaller_seen = -1;

        // Scan all numbers to the right of 'current'
        for (int j = i + 1; j < n; ++j) {

            // We only care about numbers smaller than 'current'
            if (target[j] < current) {

                // If we find an ascent (Low -> High) among smaller numbers:
                if (last_smaller_seen != -1 && target[j] > last_smaller_seen) {
                    return false; // 3-1-2 Pattern Detected
                }

                last_smaller_seen = target[j];
            }
        }
    }
    return true;
}

Answer: This approach reduces Space Complexity to \(O(1)\) at the cost of increasing Time Complexity to \(O(N^2)\).

Here are similar problems to practice stack validations: