🎯 JavaScript Stack & Queue — Top 25 Interview Questions

---

Q1 — Valid Parentheses

🧠 How to Approach This

Step 1 — Recognize the pattern: Opening → push; closing → must match stack top.

Step 2 — Brute force (what NOT to do): Count opens vs closes — fails for "([)]".

Step 3 — Optimal insight: Stack enforces LIFO matching order.

Step 4 — Algorithm:

1. Map closing → expected opening

2. Push opens; on close: top must match, else false

3. Stack must be empty at end

Step 5 — Edge cases: Only closings; interleaved {[()]}.

function isValid(s) {
  const stack = [];
  const map = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if ('([{'.includes(ch)) stack.push(ch);
    else {
      if (!stack.length || stack.at(-1) !== map[ch]) return false;
      stack.pop();
    }
  }
  return stack.length === 0;
}

Time: O(n) | Space: O(n)

---

Q2 — Min Stack

🧠 How to Approach This

Step 1 — Recognize the pattern: Track running minimum with each pushed value.

Step 2 — Brute force (what NOT to do): Scan stack for min — O(n) per call.

Step 3 — Optimal insight: Store [val, currentMin] pairs — O(1) all ops.

Step 4 — Algorithm:

1. Push: append [val, Math.min(val, top_min)]

2. Pop/top/getMin: index top pair

Step 5 — Edge cases: First push; duplicate min values.

class MinStack {
  constructor() { this.stack = []; }
  push(val) {
    const min = this.stack.length ? Math.min(val, this.stack.at(-1)[1]) : val;
    this.stack.push([val, min]);
  }
  pop()    { this.stack.pop(); }
  top()    { return this.stack.at(-1)[0]; }
  getMin() { return this.stack.at(-1)[1]; }
}

Time: O(1) all ops | Space: O(n)

---

Q3 — Evaluate Reverse Polish Notation

🧠 How to Approach This

Step 1 — Recognize the pattern: Operand → push; operator → pop two, compute, push result.

Step 2 — Brute force (what NOT to do): Build expression tree — overkill.

Step 3 — Optimal insight: Stack evaluates RPN left to right directly.

Step 4 — Algorithm:

1. For each token: if number → push; if operator → pop b, pop a, compute a OP b, push

2. Return stack[0]

Step 5 — Edge cases: Division truncates toward zero — use Math.trunc.

function evalRPN(tokens) {
  const stack = [];
  for (const t of tokens) {
    if ('+-*/'.includes(t)) {
      const b = stack.pop(), a = stack.pop();
      if (t === '+') stack.push(a + b);
      else if (t === '-') stack.push(a - b);
      else if (t === '*') stack.push(a * b);
      else stack.push(Math.trunc(a / b)); // truncate toward zero
    } else {
      stack.push(Number(t));
    }
  }
  return stack[0];
}

Time: O(n) | Space: O(n)

---

Q4 — Daily Temperatures

🧠 How to Approach This

Step 1 — Recognize the pattern: "Days until warmer" → monotonic decreasing stack.

Step 2 — Brute force (what NOT to do): Nested loops — O(n²).

Step 3 — Optimal insight: Stack of indices. When warmer found, result = i - popped_i.

Step 4 — Algorithm:

1. Stack of indices (decreasing temps)

2. Pop when top's temp < current; result[pop] = i - pop

3. Push i

Step 5 — Edge cases: No warmer day → stays 0.

function dailyTemperatures(temps) {
  const n = temps.length;
  const result = new Array(n).fill(0);
  const stack  = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && temps[stack.at(-1)] < temps[i]) {
      const idx = stack.pop();
      result[idx] = i - idx;
    }
    stack.push(i);
  }
  return result;
}

Time: O(n) | Space: O(n)

---

Q5 — Next Greater Element I

🧠 How to Approach This

Step 1 — Recognize the pattern: Precompute next-greater for nums2 → map; answer queries for nums1.

Step 2 — Brute force (what NOT to do): For each nums1 element scan nums2 — O(m·n).

Step 3 — Optimal insight: Monotonic stack on nums2, fill map. Then O(1) lookup per query.

Step 4 — Algorithm:

1. Build monotonic stack on nums2, fill map[val] = next_greater

2. For each num in nums1: answer = map.get(num) ?? -1

Step 5 — Edge cases: No greater element → -1.

function nextGreaterElement(nums1, nums2) {
  const map   = new Map();
  const stack = [];
  for (const num of nums2) {
    while (stack.length && stack.at(-1) < num) map.set(stack.pop(), num);
    stack.push(num);
  }
  return nums1.map(n => map.get(n) ?? -1);
}

Time: O(n + m) | Space: O(n)

---

Q6 — Next Greater Element II (Circular Array)

🧠 How to Approach This

Step 1 — Recognize the pattern: Circular → process array twice (0..2n-1), index % n.

Step 2 — Brute force (what NOT to do): Nested loop with modulo — O(n²).

Step 3 — Optimal insight: Single loop 0..2n-1. Only push on first pass.

Step 4 — Algorithm:

1. Monotonic decreasing stack of indices

2. Loop 0..2n-1; idx = i % n; resolve stack when nums[top] < nums[idx]

3. Push only when i < n

Step 5 — Edge cases: All same values → all -1.

function nextGreaterElements(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack  = [];
  for (let i = 0; i < 2 * n; i++) {
    const idx = i % n;
    while (stack.length && nums[stack.at(-1)] < nums[idx]) {
      result[stack.pop()] = nums[idx];
    }
    if (i < n) stack.push(idx);
  }
  return result;
}

Time: O(n) | Space: O(n)

---

Q7 — Largest Rectangle in Histogram

🧠 How to Approach This

Step 1 — Recognize the pattern: Monotonic increasing stack — pop when shorter bar arrives.

Step 2 — Brute force (what NOT to do): All bar pairs — O(n²).

Step 3 — Optimal insight: Each popped bar defines a rectangle; width = i - new_top - 1.

Step 4 — Algorithm:

1. Append sentinel 0, stack starts with [-1]

2. Pop when top's height > current; compute area

Step 5 — Edge cases: Sentinel forces all bars to be processed.

function largestRectangleArea(heights) {
  heights = [...heights, 0];
  const stack = [-1];
  let maxArea = 0;
  for (let i = 0; i < heights.length; i++) {
    while (stack.at(-1) !== -1 && heights[stack.at(-1)] > heights[i]) {
      const h = heights[stack.pop()];
      const w = i - stack.at(-1) - 1;
      maxArea = Math.max(maxArea, h * w);
    }
    stack.push(i);
  }
  return maxArea;
}

Time: O(n) | Space: O(n)

---

Q8 — Trapping Rain Water (Stack)

🧠 How to Approach This

Step 1 — Recognize the pattern: Stack-based horizontal layer water calculation.

Step 2 — Brute force (what NOT to do): For each bar find max left/right — O(n²).

Step 3 — Optimal insight: Decreasing stack. When taller bar arrives, pop and compute valley water.

Step 4 — Algorithm:

1. Monotonic decreasing stack of indices

2. When heights[i] > heights[top]: pop, compute water = (min(left, right) - bottom) × width

Step 5 — Edge cases: No valley (sorted) → 0.

function trap(height) {
  const stack = [];
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (stack.length && height[stack.at(-1)] < height[i]) {
      const bottom = stack.pop();
      if (!stack.length) break;
      const left = stack.at(-1);
      const h = Math.min(height[left], height[i]) - height[bottom];
      const w = i - left - 1;
      water += h * w;
    }
    stack.push(i);
  }
  return water;
}

Time: O(n) | Space: O(n)

---

Q9 — Implement Queue Using Two Stacks

🧠 How to Approach This

Step 1 — Recognize the pattern: Two LIFO stacks → FIFO queue via lazy transfer.

Step 2 — Brute force (what NOT to do): Transfer on every operation — O(n) each.

Step 3 — Optimal insight: Only transfer when outStack is empty — amortized O(1).

Step 4 — Algorithm:

1. push → inStack

2. pop/peek: if outStack empty, drain inStack

Step 5 — Edge cases: Multiple pops without pushes.

class MyQueue {
  constructor() { this.inStack = []; this.outStack = []; }
  push(x) { this.inStack.push(x); }
  pop()   { this._transfer(); return this.outStack.pop(); }
  peek()  { this._transfer(); return this.outStack.at(-1); }
  empty() { return !this.inStack.length && !this.outStack.length; }
  _transfer() {
    if (!this.outStack.length)
      while (this.inStack.length) this.outStack.push(this.inStack.pop());
  }
}

Time: O(1) amortized | Space: O(n)

---

Q10 — Implement Stack Using Two Queues

🧠 How to Approach This

Step 1 — Recognize the pattern: Two FIFO queues → LIFO by rotating elements.

Step 2 — Brute force (what NOT to do): Copy on every operation.

Step 3 — Optimal insight: Push to q2, drain q1 into q2, swap. Front of q1 is always the top.

Step 4 — Algorithm:

1. push: enqueue to q2, drain q1→q2, swap q1↔q2

2. pop/top: dequeue/peek front of q1

Step 5 — Edge cases: Single element; multiple pops.

class MyStack {
  constructor() { this.q1 = []; this.q2 = []; }
  push(x) {
    this.q2.push(x);
    while (this.q1.length) this.q2.push(this.q1.shift());
    [this.q1, this.q2] = [this.q2, this.q1];
  }
  pop()   { return this.q1.shift(); }
  top()   { return this.q1[0]; }
  empty() { return this.q1.length === 0; }
}

Time: O(n) push, O(1) pop | Space: O(n)

---

Q11 — Sliding Window Maximum (Deque)

🧠 How to Approach This

Step 1 — Recognize the pattern: Monotonic decreasing deque of indices.

Step 2 — Brute force (what NOT to do): Scan k elements per window — O(n·k).

Step 3 — Optimal insight: Front = current max. Remove expired from front; smaller from back.

Step 4 — Algorithm:

1. Remove expired from front (index < i - k + 1)

2. Remove smaller from back

3. Record result when i >= k-1

Step 5 — Edge cases: k = 1 (trivial); k > n.

function maxSlidingWindow(nums, k) {
  const deque = [], result = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && deque[0] < i - k + 1) deque.shift();
    while (deque.length && nums[deque.at(-1)] < nums[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

Time: O(n) | Space: O(k)

---

Q12 — Basic Calculator (+ - and Parentheses)

🧠 How to Approach This

Step 1 — Recognize the pattern: Stack saves (result, sign) on (; restores on ).

Step 2 — Brute force (what NOT to do): Expression tree — complex.

Step 3 — Optimal insight: Track result and sign; push/pop state on parentheses.

Step 4 — Algorithm:

1. result = 0, sign = 1

2. On (: push [result, sign]; reset

3. On ): combine with popped state

Step 5 — Edge cases: Multi-digit numbers; spaces.

function calculate(s) {
  const stack = [];
  let result = 0, sign = 1, num = 0;
  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + Number(ch);
    } else if (ch === '+' || ch === '-') {
      result += sign * num; num = 0;
      sign = ch === '+' ? 1 : -1;
    } else if (ch === '(') {
      stack.push(result, sign); result = 0; sign = 1;
    } else if (ch === ')') {
      result += sign * num; num = 0;
      result *= stack.pop();  // sign before paren
      result += stack.pop();  // result before paren
    }
  }
  return result + sign * num;
}

Time: O(n) | Space: O(n)

---

Q13 — Basic Calculator II (+ - * /)

🧠 How to Approach This

Step 1 — Recognize the pattern: Push +/- operands; apply */÷ immediately.

Step 2 — Brute force (what NOT to do): Two-pass for precedence levels.

Step 3 — Optimal insight: Stack for addition terms; * / modify stack top.

Step 4 — Algorithm:

1. Track num and lastSign

2. On operator/end: push or modify stack based on lastSign

Step 5 — Edge cases: Multi-digit numbers; trailing digit.

function calculateII(s) {
  const stack = [];
  let num = 0, sign = '+';
  s = s.trim();
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (ch >= '0' && ch <= '9') num = num * 10 + Number(ch);
    if ((ch < '0' || ch === ' ' ? ch !== ' ' : false) || i === s.length - 1) {
      // trigger: non-digit non-space, or last char
    }
    if (('+-*/'.includes(ch) && ch !== ' ') || i === s.length - 1) {
      if (sign === '+') stack.push(num);
      else if (sign === '-') stack.push(-num);
      else if (sign === '*') stack.push(stack.pop() * num);
      else stack.push(Math.trunc(stack.pop() / num));
      sign = ch; num = 0;
    }
  }
  return stack.reduce((a, b) => a + b, 0);
}

Time: O(n) | Space: O(n)

---

Q14 — Decode String

🧠 How to Approach This

Step 1 — Recognize the pattern: Nested encoding → stack saves state on [.

Step 2 — Brute force (what NOT to do): Recursion without stack — deep nesting risk.

Step 3 — Optimal insight: Push [currentStr, k] on [; on ] expand and prepend saved string.

Step 4 — Algorithm:

1. Build current string and number

2. On [: push state, reset

3. On ]: pop, expand cur × k, prepend saved

Step 5 — Edge cases: Multi-digit numbers; nested 3[a2[c]].

function decodeString(s) {
  const stack = [];
  let cur = '', k = 0;
  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      k = k * 10 + Number(ch);
    } else if (ch === '[') {
      stack.push([cur, k]); cur = ''; k = 0;
    } else if (ch === ']') {
      const [prev, times] = stack.pop();
      cur = prev + cur.repeat(times);
    } else {
      cur += ch;
    }
  }
  return cur;
}

Time: O(output length) | Space: O(n)

---

Q15 — Remove Duplicate Letters

🧠 How to Approach This

Step 1 — Recognize the pattern: Greedy + monotonic stack. Remove larger chars if they appear later.

Step 2 — Brute force (what NOT to do): All permutations — factorial.

Step 3 — Optimal insight: Track last occurrence. Pop stack top if larger and has future occurrence.

Step 4 — Algorithm:

1. Compute last occurrence index of each char

2. Monotonic increasing stack with "in-stack" Set

3. Pop when top > curr and top appears later

Step 5 — Edge cases: Duplicate chars; single occurrences.

function removeDuplicateLetters(s) {
  const last = {};
  for (let i = 0; i < s.length; i++) last[s[i]] = i;
  const stack = [], inStack = new Set();
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (inStack.has(ch)) continue;
    while (stack.length && stack.at(-1) > ch && last[stack.at(-1)] > i) {
      inStack.delete(stack.pop());
    }
    stack.push(ch); inStack.add(ch);
  }
  return stack.join('');
}

Time: O(n) | Space: O(1) (26 letters)

---

Q16 — Remove K Digits

🧠 How to Approach This

Step 1 — Recognize the pattern: Greedy — remove digit when smaller one follows (k times).

Step 2 — Brute force (what NOT to do): All combinations — O(n choose k).

Step 3 — Optimal insight: Monotonic increasing stack; pop when top > curr and k > 0.

Step 4 — Algorithm:

1. Increasing stack, pop when top > curr and k > 0

2. If k > 0, remove from end

3. Trim leading zeros

Step 5 — Edge cases: k = n (return "0"); leading zeros after removal.

function removeKdigits(num, k) {
  const stack = [];
  for (const d of num) {
    while (k > 0 && stack.length && stack.at(-1) > d) { stack.pop(); k--; }
    stack.push(d);
  }
  while (k-- > 0) stack.pop();
  const result = stack.join('').replace(/^0+/, '');
  return result || '0';
}

Time: O(n) | Space: O(n)

---

Q17 — Score of Parentheses

🧠 How to Approach This

Step 1 — Recognize the pattern: Stack-based scoring — () = 1, nested = 2 × inner.

Step 2 — Brute force (what NOT to do): Recursive counting — harder to track.

Step 3 — Optimal insight: Stack with 0 as layer marker; on ) merge or score.

Step 4 — Algorithm:

1. On (: push 0

2. On ): pop v; if 0 → push 1 (leaf), else push 2*v; add to new top

Step 5 — Edge cases: Adjacent ()() — summed at same level.

function scoreOfParentheses(s) {
  const stack = [0];
  for (const ch of s) {
    if (ch === '(') stack.push(0);
    else {
      const v = stack.pop();
      stack[stack.length - 1] += Math.max(2 * v, 1);
    }
  }
  return stack[0];
}

Time: O(n) | Space: O(n)

---

Q18 — Asteroid Collision

🧠 How to Approach This

Step 1 — Recognize the pattern: Collision only when positive (right) meets negative (left).

Step 2 — Brute force (what NOT to do): Simulate all pairs — O(n²).

Step 3 — Optimal insight: Stack. Positive → push. Negative → collide with positive tops.

Step 4 — Algorithm:

1. Positive or stack top is negative → push

2. If negative: while top > 0 and |neg| > top: pop

3. Equal → pop both; if negative wins → push it

Step 5 — Edge cases: All same direction; equal collision (both destroyed).

function asteroidCollision(asteroids) {
  const stack = [];
  for (const a of asteroids) {
    let alive = true;
    while (alive && a < 0 && stack.length && stack.at(-1) > 0) {
      if (stack.at(-1) < -a)     stack.pop();
      else if (stack.at(-1) === -a) { stack.pop(); alive = false; }
      else alive = false;
    }
    if (alive) stack.push(a);
  }
  return stack;
}

Time: O(n) | Space: O(n)

---

Q19 — Car Fleet

🧠 How to Approach This

Step 1 — Recognize the pattern: Sort descending by position; cars that don't catch up form new fleets.

Step 2 — Brute force (what NOT to do): Simulate time steps — imprecise.

Step 3 — Optimal insight: Time = (target - pos) / speed. If next car's time ≤ fleet top's time → same fleet.

Step 4 — Algorithm:

1. Sort by position descending

2. Compute arrival time; if time > stack top → new fleet (push), else merge

Step 5 — Edge cases: Single car; equal positions.

function carFleet(target, position, speed) {
  const cars = position.map((p, i) => [p, speed[i]]);
  cars.sort((a, b) => b[0] - a[0]);
  const stack = [];
  for (const [pos, spd] of cars) {
    const time = (target - pos) / spd;
    if (!stack.length || time > stack.at(-1)) stack.push(time);
  }
  return stack.length;
}

Time: O(n log n) | Space: O(n)

---

Q20 — Exclusive Time of Functions

🧠 How to Approach This

Step 1 — Recognize the pattern: Stack of running functions; compute elapsed on each log event.

Step 2 — Brute force (what NOT to do): Simulate per time unit.

Step 3 — Optimal insight: Track prevTime. On each event, attribute delta to current top.

Step 4 — Algorithm:

1. Stack of function IDs

2. start: add delta to top (if any), push id, update prev

3. end: add delta+1 to top, pop, prev = timestamp+1

Step 5 — Edge cases: Nested calls; single function.

function exclusiveTime(n, logs) {
  const result = new Array(n).fill(0);
  const stack  = [];
  let prev = 0;
  for (const log of logs) {
    const [id, type, time] = log.split(':');
    const t = Number(time);
    if (type === 'start') {
      if (stack.length) result[stack.at(-1)] += t - prev;
      stack.push(Number(id)); prev = t;
    } else {
      result[stack.pop()] += t - prev + 1;
      prev = t + 1;
    }
  }
  return result;
}

Time: O(n) | Space: O(n)

---

Q21 — Number of Visible People in Queue

🧠 How to Approach This

Step 1 — Recognize the pattern: Monotonic decreasing stack, right to left.

Step 2 — Brute force (what NOT to do): For each person scan right — O(n²).

Step 3 — Optimal insight: Process right-to-left. Stack holds heights decreasingly. Count popped (visible shorter) + 1 if stack still has taller.

Step 4 — Algorithm:

1. Traverse right to left

2. Count shorter people popped; add 1 if stack non-empty (taller blocker visible)

Step 5 — Edge cases: Strictly decreasing heights.

function canSeePersonsCount(heights) {
  const n = heights.length;
  const result = new Array(n).fill(0);
  const stack  = [];
  for (let i = n - 1; i >= 0; i--) {
    let count = 0;
    while (stack.length && stack.at(-1) < heights[i]) { stack.pop(); count++; }
    if (stack.length) count++;
    result[i] = count;
    stack.push(heights[i]);
  }
  return result;
}

Time: O(n) | Space: O(n)

---

Q22 — Design Circular Queue

🧠 How to Approach This

Step 1 — Recognize the pattern: Fixed-size ring buffer with head/tail pointer arithmetic.

Step 2 — Brute force (what NOT to do): Array shift/unshift — O(n).

Step 3 — Optimal insight: Circular index: (head + size) % capacity.

Step 4 — Algorithm:

1. Array of size k, head = 0, size = 0

2. Enqueue: write at (head+size)%k; dequeue: advance head

Step 5 — Edge cases: Full on enqueue, empty on dequeue.

class MyCircularQueue {
  constructor(k) { this.data = new Array(k); this.cap = k; this.head = 0; this.size = 0; }
  enQueue(val) {
    if (this.isFull()) return false;
    this.data[(this.head + this.size) % this.cap] = val; this.size++; return true;
  }
  deQueue() {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.cap; this.size--; return true;
  }
  Front() { return this.isEmpty() ? -1 : this.data[this.head]; }
  Rear()  { return this.isEmpty() ? -1 : this.data[(this.head + this.size - 1) % this.cap]; }
  isEmpty() { return this.size === 0; }
  isFull()  { return this.size === this.cap; }
}

Time: O(1) all ops | Space: O(k)

---

Q23 — Design Circular Deque

🧠 How to Approach This

Step 1 — Recognize the pattern: Ring buffer with front/back insert/delete.

Step 2 — Brute force (what NOT to do): Array unshift — O(n) front ops.

Step 3 — Optimal insight: insertFront: head = (head-1+cap)%cap.

Step 4 — Algorithm:

1. insertFront: move head back circularly

2. insertLast: write at (head+size)%cap

3. delete: adjust head or size

Step 5 — Edge cases: Full/empty checks before every op.

class MyCircularDeque {
  constructor(k) { this.data = new Array(k); this.cap = k; this.head = 0; this.size = 0; }
  insertFront(v) {
    if (this.isFull()) return false;
    this.head = (this.head - 1 + this.cap) % this.cap;
    this.data[this.head] = v; this.size++; return true;
  }
  insertLast(v) {
    if (this.isFull()) return false;
    this.data[(this.head + this.size) % this.cap] = v; this.size++; return true;
  }
  deleteFront() {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.cap; this.size--; return true;
  }
  deleteLast() {
    if (this.isEmpty()) return false;
    this.size--; return true;
  }
  getFront() { return this.isEmpty() ? -1 : this.data[this.head]; }
  getRear()  { return this.isEmpty() ? -1 : this.data[(this.head + this.size - 1) % this.cap]; }
  isEmpty()  { return this.size === 0; }
  isFull()   { return this.size === this.cap; }
}

Time: O(1) all ops | Space: O(k)

---

Q24 — Design Hit Counter

🧠 How to Approach This

Step 1 — Recognize the pattern: Sliding window of 300s — queue of timestamps.

Step 2 — Brute force (what NOT to do): Store all hits, filter on getHits — O(n) per call.

Step 3 — Optimal insight: Queue; on getHits remove entries older than timestamp - 299.

Step 4 — Algorithm:

1. hit: push timestamp

2. getHits(t): while front <= t-300: shift; return length

Step 5 — Edge cases: Multiple hits at same timestamp; empty window.

class HitCounter {
  constructor() { this.queue = []; }
  hit(timestamp)      { this.queue.push(timestamp); }
  getHits(timestamp)  {
    while (this.queue.length && this.queue[0] <= timestamp - 300) this.queue.shift();
    return this.queue.length;
  }
}

Time: O(n) worst per getHits, O(1) amortized | Space: O(n)

---

Q25 — Longest Valid Parentheses

🧠 How to Approach This

Step 1 — Recognize the pattern: Stack tracks unmatched indices; length = i - stack_top.

Step 2 — Brute force (what NOT to do): Check every substring — O(n²) or O(n³).

Step 3 — Optimal insight: Stack initialized with [-1]. ( → push index; ) → pop, compute length, or push new base.

Step 4 — Algorithm:

1. Stack = [-1] (base)

2. ( → push i; ) → pop; if empty push i as new base; else max = i - stack.top

Step 5 — Edge cases: All openings; all closings; alternating.

function longestValidParentheses(s) {
  const stack = [-1];
  let max = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i);
    } else {
      stack.pop();
      if (!stack.length) stack.push(i); // new base
      else max = Math.max(max, i - stack.at(-1));
    }
  }
  return max;
}

Time: O(n) | Space: O(n)