LeetCode Entry

946. Validate Stack Sequences

13.04.2023 medium 2023 kotlin

use one iteration and a second pointer for pop

946. Validate Stack Sequences 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 substack

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)\)