Validating Stack Sequences in Go: A Simple Microsoft Interview Solution

Basic stack operations in Go

stack := []int{}
stack = append(stack, 1) // push 1
stack = append(stack, 2) // push 2
val := stack[len(stack)-1]
stack = stack[:len(stack)-1] // pop
val := stack[len(stack)-1]
stack = stack[:len(stack)-1] // pop

We push each element from the pushed array onto a temporary stack sk. After each push we repeatedly compare the top of sk with the current element of popped (pointed to by index j). If they are equal we pop the top element and advance j. The inner for loop continues until the stack is empty or the top no longer matches the next popped element.

The process guarantees that elements are removed from the simulated stack exactly in the order required by popped. When the outer loop finishes, the algorithm returns true if and only if all elements of popped have been matched (i.e., j == len(popped)), indicating that the given sequences are a valid push‑pop pair.

Implementation

func validateStackSequences(pushed []int, popped []int) bool {
    j := 0
    sk := []int{}
    for _, v := range pushed {
        sk = append(sk, v)
        for len(sk) > 0 && sk[len(sk)-1] == popped[j] {
            j++
            sk = sk[:len(sk)-1]
        }
    }
    return j == len(popped)
}

Key takeaways

Understand how Go slices can be used as a stack.

Each push is followed by a loop that pops while the stack top matches the next required pop element.

The algorithm runs in O(n) time and O(n) extra space.