LeetCode: Validate Stack Sequences Solution

Approach

Push value to stack

Along with that, keep pop stack if its top is equal to the first element of the popped array (also shift the popped array in that case)

Implementation

1function Stack() {
2  const stack = []
3
4  this.push = function (el) {
5    stack.push(el)
6  }
7
8  this.pop = function () {
9    return stack.pop()
10  }
11
12  this.peek = function () {
13    return stack[stack.length - 1]
14  }
15
16  this.isEmpty = function () {
17    return stack.length === 0
18  }
19}
20
21/**
22 * @param {number[]} pushed
23 * @param {number[]} popped
24 * @return {boolean}
25 */
26var validateStackSequences = function (pushed, popped) {
27  const N = pushed.length
28  const stack = new Stack()
29  let i = 0
30  let j = 0
31  while (i < N) {
32    stack.push(pushed[i++])
33    while (stack.peek() === popped[j] && j < N) {
34      stack.pop()
35      j++
36    }
37  }
38
39  return stack.isEmpty()
40}