Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5

Input:
pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output:
 false
Explanation: 1 cannot be popped before 2.

Solution

Method 1 - Using Stack

The idea is to simulate the push and pop operations using a stack. We iterate through the pushed array and perform push operations. For each pushed value, we check if it matches the current value in popped. If it matches, we perform a pop operation and move to the next value in the popped array. This process continues until we have processed all elements in both arrays.

Here is the approach:

  1. Use a stack to simulate the push and pop operations.
  2. Iterate over the pushed array and push elements onto the stack.
  3. After each push, check if the top of the stack matches the current value in popped.
  4. If it matches, pop the stack and move to the next value in popped.
  5. Repeat the process until all elements in pushed are processed.
  6. Finally, check if the stack is empty. If the stack is empty, the sequences are valid; otherwise, they are not.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n = pushed.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int j = 0; // pointer for popped array

        for (int x : pushed) {
            stack.push(x);
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        
        return stack.isEmpty();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack: List[int] = []
        j: int = 0  # pointer for popped array

        for x in pushed:
            stack.append(x)
            while stack and stack[-1] == popped[j]:
                stack.pop()
                j += 1
        
        return not stack

Complexity

  • ⏰ Time complexity:  O(n) where n is the length of the pushed array, as each element is pushed and popped at most once.
  • 🧺 Space complexity: O(n) for storing elements in the stack.