_946. Validate Stack Sequences.md

946. Validate Stack Sequences

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 12, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Stack, Simulation

Acceptance Rate : 69.72 %

---

Solutions

• m946.c
• m946.py

C

m946.c

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) {
    int stack[pushedSize];
    memset(stack, 0, sizeof(int) * pushedSize);
    int stackIndx = 0;

    int push = 0;
    int pop = 0;
    while (push < pushedSize || pop < poppedSize) {
        if (stackIndx != 0 && popped[pop] == stack[stackIndx - 1]) {
            stackIndx--;
            pop++;
        } else if (push < pushedSize) {
            stack[stackIndx] = pushed[push];
            push++;
            stackIndx++;
        } else {
            return false;
        }

    }

    return true;
}

Python

m946.py

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        vals = []
        
        push, pop = 0, 0
        while push < len(pushed) or pop < len(popped) :
            if vals and pop < len(popped) and popped[pop] == vals[-1] :
                pop += 1
                vals.pop()
            elif push < len(pushed) :
                vals.append(pushed[push])
                push += 1
            else : # no more to push and can't pop
                return False
        return True