946. Validate Stack Sequences #

Problem #

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

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.

Note:

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed is a permutation of popped.
4. pushed and popped have distinct values.

Problem Summary #

Given 2 arrays: one array represents the push order, and the other array represents the pop order. After operating according to this order, can the stack ultimately be emptied?

Solution Approach #

This problem is also a stack-operation problem. First push elements onto the stack in the order of the pushed array, then look for the stack top element in popped in sequence. If it is found, pop it, until the popped array has been traversed. Ultimately, if the popped array has been fully traversed, it means the entire stack has been emptied.

Code #

package leetcode

func validateStackSequences(pushed []int, popped []int) bool {
	stack, j, N := []int{}, 0, len(pushed)
	for _, x := range pushed {
		stack = append(stack, x)
		for len(stack) != 0 && j < N && stack[len(stack)-1] == popped[j] {
			stack = stack[0 : len(stack)-1]
			j++
		}
	}
	return j == N
}