medium Validate Stack Sequences

Problem Statement

Given two integer arrays, pushed and popped, each with unique values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack. Otherwise, return false.

Examples

Example 1

• Input: pushed = [1, 2, 3, 4, 6, 7], popped = [4, 6, 3, 2, 7, 1]
• Expected Output: true
• Explanation:
  • We can perform the following operations:
    • Push 1, push 2, push 3, push 4, pop 4, push 6, pop 6, pop 3, pop 2, push 7, pop 7, pop 1.

Example 2

• Input: pushed = [1, 2, 3, 4], popped = [4, 3, 2, 1]
• Expected Output: true
• Explanation:
  • We can perform the following operations:
    • Push 1, push 2, push 3, push 4, pop 4, pop 3, pop 2, pop 1.

Example 3

• Input: pushed = [1, 2, 3, 4, 5], popped = [4, 5, 3, 1, 2]
• Expected Output: false
• Explanation:
  • There's no way to pop 4, 5, 3, 1, 2 in that order with the given pushed sequence. However, 4, 5, 3, 2, 1 can be a valid sequence.

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

To solve this problem, we use a simulation approach where we emulate the stack operations based on the pushed and popped sequences. We use a stack to track the elements as they are pushed and popped. As we iterate through the pushed array, we push elements onto the stack and check if the top of the stack matches the current element in the popped array. If it does, we pop from the stack and move to the next element in the popped array. This approach ensures that we only perform valid stack operations and helps us verify if the given popped sequence can be achieved from the pushed sequence.

The simulation approach is effective because it directly mimics the stack operations and allows us to easily track the sequence of operations. It ensures that we only perform valid stack operations, and by maintaining a stack, we can quickly verify if the top of the stack matches the current element in the popped sequence.

Step-by-Step Algorithm

1. Initialize the Stack and Index:

   • Create a Stack<Integer> stack to simulate the push and pop operations.
   • Initialize an index i = 0 to keep track of the current position in the popped array.

2. Iterate Through the pushed Array:

   • For each num in pushed:
     • Push the current element to the stack to simulate the push operation.

3. Check and Perform Pop Operations:

   • While the stack is not empty and the top of the stack matches popped[i]:
     • This ensures we only pop elements when they match the expected sequence.
     • Pop from the stack:
       • Remove the top element from the stack to simulate the pop operation.
     • Increment i:
       • Move to the next element in the popped array to continue the validation process.

4. Return the Result:

   • Return stack.isEmpty():
     • If the stack is empty, it means all elements were matched and popped correctly according to the popped sequence, hence the sequences are valid. If not, the sequences are invalid.

Algorithm Walkthrough

Let's go through the algorithm step by step with pushed = [1, 2, 3, 4, 6, 7] and popped = [4, 6, 3, 2, 7, 1].

1. Initialization:

   • stack = []
   • i = 0

2. First iteration (num = 1):

   • Push Operation: Push 1 onto the stack.
     • stack = [1]
   • Pop Operation: The top of the stack (1) does not match popped[0] (4), so we do not pop.
   • stack = [1], i = 0

3. Second iteration (num = 2):

   • Push Operation: Push 2 onto the stack.
     • stack = [1, 2]
   • Pop Operation: The top of the stack (2) does not match popped[0] (4), so we do not pop.
   • stack = [1, 2], i = 0

4. Third iteration (num = 3):

   • Push Operation: Push 3 onto the stack.
     • stack = [1, 2, 3]
   • Pop Operation: The top of the stack (3) does not match popped[0] (4), so we do not pop.
   • stack = [1, 2, 3], i = 0

5. Fourth iteration (num = 4):

   • Push Operation: Push 4 onto the stack.
     • stack = [1, 2, 3, 4]
   • Pop Operation: The top of the stack (4) matches popped[0] (4), so pop 4 from the stack and increment i by 1.
     • stack = [1, 2, 3], i = 1

6. Fifth iteration (num = 6):

   • Push Operation: Push 6 onto the stack.
     • stack = [1, 2, 3, 6]
   • Pop Operation: The top of the stack (6) matches popped[1] (6), so pop 6 from the stack and increment i by 1.
     • stack = [1, 2, 3], i = 2
   • The top of the stack (3) matches popped[2] (3), so pop 3 from the stack and increment i by 1.
     • stack = [1, 2], i = 3
   • The top of the stack (2) matches popped[3] (2), so pop 2 from the stack and increment i by 1.
     • stack = [1], i = 4

7. Sixth iteration (num = 7):

   • Push Operation: Push 7 onto the stack.
     • stack = [1, 7]
   • Pop Operation: The top of the stack (7) matches popped[4] (7), so pop 7 from the stack and increment i by 1.
     • stack = [1], i = 5
   • The top of the stack (1) matches popped[5] (1), so pop 1 from the stack and increment i by 1.
     • stack = [], i = 6

8. Final Check:

   • The stack is empty, so return true.

Code

import java.util.Stack;

class Solution {

  public boolean validateStackSequences(int[] pushed, int[] popped) {
    Stack<Integer> stack = new Stack<>();
    int i = 0;

    for (int num : pushed) {
      stack.push(num); // push onto stack
      // When stack is empty and top elements matches the popped[i]
      while (!stack.isEmpty() && stack.peek() == popped[i]) {
        stack.pop(); // pop from stack
        i++;
      }
    }

    return stack.isEmpty();
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    int[] pushed1 = { 1, 2, 3, 4, 6, 7 };
    int[] popped1 = { 4, 6, 3, 2, 7, 1 };
    System.out.println(sol.validateStackSequences(pushed1, popped1)); // true

    int[] pushed2 = { 1, 2, 3, 4 };
    int[] popped2 = { 4, 3, 2, 1 };
    System.out.println(sol.validateStackSequences(pushed2, popped2)); // true

    int[] pushed3 = { 1, 2, 3, 4, 5 };
    int[] popped3 = { 4, 5, 3, 1, 2 };
    System.out.println(sol.validateStackSequences(pushed3, popped3)); // false
  }
}

Complexity Analysis

• Time Complexity: , where n is the number of elements in the pushed array. Each element is pushed and popped from the stack once.
• Space Complexity: , where n is the number of elements in the pushed array. This is due to the space used by the stack.

🎯 STRICT STANDOUT — Solution Validate Stack Sequences

0. Why this page exists

Family: Stack simulation

Solution page must lock the amortized O(n) argument and the false example where top mismatches the next required pop — that is the LIFO edge the algorithm detects.

1. Pattern + when-NOT (K12)

Pattern / template: Stack + index j into popped. Iterate x in pushed: push x; while stack and stack[-1]==popped[j]: pop; j+=1. Return j==n.

When-NOT: When-NOT sorting both arrays (ignores order constraints). When-NOT graph topo of arbitrary partial order — stack imposes a specific parenthesization, not general DAG.

2. Complexity derivation (K11)

Time Θ(n): ≤2n stack ops.
Space Θ(n) worst (strictly increasing then reverse pop needs all n).
Amortized: each element enters/leaves stack once.

3. Edge hand-run (K13)

Hand-run false: push 1,2,3,4; pop 4; push 5; pop 5; pop 3; need 1 but top=2 → false.
true reverse: pushed 1..n, popped n..1 → stack fills then drains.
Empty arrays: true (n=0) if allowed.

4. Interviewer follow-ups & drills

Q1. Prove no false negative
Model answer: Any valid schedule never needs to skip a legal pop; simulation mirrors unique forced choices.

Q2. Duplicates?
Model answer: With unique values match is unique; with dups same code still validates a concrete sequence.

Q3. Related problem?
Model answer: Asteroid collision / remove stars — same stack-collapse family.