13.04.2023

946. Validate Stack Sequences

[946. Validate Stack Sequences](https://leetcode.com/problems/validate-stack-sequences/description/) medium

fun validateStackSequences(pushed: IntArray, popped: IntArray): Boolean =
with(Stack<Int>()) {
    var pop = 0
    pushed.forEach {
        push(it)
        while (isNotEmpty() && peek() == popped[pop]) {
            pop()
            pop++
        }
    }
    isEmpty()
}

[blog post](https://leetcode.com/problems/validate-stack-sequences/solutions/3411131/kotlin-stack/)

#### Telegram

https://t.me/leetcode_daily_unstoppable/179

#### Intuition

Do simulation using a Stack.

#### Approach

• use one iteration and a second pointer for `pop`

• empty the stack after inserting an element

#### Complexity

- Time complexity:

O(n)

- Space complexity:

O(n)