SyntaxPilot
Courses/JavaScript Coding Questions/Lesson 27
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript Coding Questions · Lesson 27 of 30

Stack and queue questions

min stackqueue with two stacksnext greater element

These are the notes for JavaScript Coding Questions, episode 27, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Last episode we built linked lists. Today: stacks and queues, built on plain arrays. Three questions interviewers love: a min stack that tells you its smallest value instantly, a queue built from two stacks, and the next greater element, where a stack turns a slow O(n²) solution into a fast O(n) one. On the way we meet a hidden cost: shift() is O(n).

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was run with Node.js 24 (node main.js), the SyntaxPilot compiler's JavaScript command, and every output below is real. Some programs measure time with console.time("label") and console.timeEnd("label"), which print how long the code between them took. Timings differ on every machine and every run: we show what we got, and only the size of the difference (seconds against milliseconds) matters.

First: stack and queue in one minute

A pile of plates: you put a plate on top, and you take one from the top. The last plate in is the first plate out. That's a stack.

A ticket counter line: you join at the back, and the person at the front leaves first. The first person in is the first person out. That's a queue.

  • Stack = LIFO, "last in, first out". Adding is push, removing is pop, looking at the top without removing is peek.
  • Queue = FIFO, "first in, first out". Adding at the back is enqueue, removing from the front is dequeue.
  • In JavaScript, both are usually a plain array. push(x) adds to the end, pop() removes from the end: together they make a stack. shift() removes from the front: push + shift make a queue.
  • arr.at(-1) reads the last item (the top of a stack). A negative index in at counts from the end; arr[-1] does not work (it's undefined).
const plates = [];
plates.push("red");
plates.push("blue");
plates.push("green");
console.log("stack:", plates, "top:", plates.at(-1));
console.log("pop:", plates.pop(), "left:", plates);

const line = [];
line.push("Asha");
line.push("Ravi");
line.push("Neha");
console.log("queue:", line, "front:", line[0]);
console.log("shift:", line.shift(), "left:", line);

const empty = [];
console.log(empty.pop(), empty.shift(), empty.at(-1), empty.length);
stack: [ 'red', 'blue', 'green' ] top: green
pop: green left: [ 'red', 'blue' ]
queue: [ 'Asha', 'Ravi', 'Neha' ] front: Asha
shift: Asha left: [ 'Ravi', 'Neha' ]
undefined undefined undefined 0

The stack gives back green, the last one in. The queue gives back Asha, the first one in. On an empty array, pop, shift and at(-1) don't throw an error: they return undefined. Remember that; it decides what our classes return when they are empty.

Why shift() is O(n): measure it

An array keeps its items in numbered places: 0, 1, 2… pop() removes the last place; nothing else moves. But shift() removes place 0, so every other item moves one place forward (place 1 becomes 0, place 2 becomes 1…), like everyone in the ticket line stepping forward. With n items, that's n moves: O(n) per shift (Big-O describes how the work grows as the input grows). Emptying the array with shift costs about n + (n - 1) + … + 1 ≈ n² / 2 moves: O(n²) in total.

for (const n of [50000, 100000, 200000]) {
  const a = Array.from({ length: n }, (_, i) => i);
  console.time(`${n} shifts`);
  while (a.length) a.shift();
  console.timeEnd(`${n} shifts`);

  const b = Array.from({ length: n }, (_, i) => i);
  console.time(`${n} pops`);
  while (b.length) b.pop();
  console.timeEnd(`${n} pops`);
}

What we got (your numbers will differ):

50000 shifts: 205.548ms
50000 pops: 0.841ms
100000 shifts: 849.271ms
100000 pops: 0.127ms
200000 shifts: 3.412s
200000 pops: 0.329ms
  • Array.from({ length: n }, (_, i) => i) makes [0, 1, 2, …, n - 1].
  • Doubling n makes the shifts take about four times as long (205 ms → 849 ms → 3.4 s): that's the n² pattern. The pops stay under a millisecond or two.
  • JavaScript engines sometimes have shortcuts that make shift cheap on small arrays, so a tiny test can fool you. Measure with big inputs.

shift() is fine for a small queue. In a hot loop over a big one, it's the trap, and Q2 shows a way around it.

Q1: Min stack

Problem. Design a stack with push(x), pop() and getMin(), all three in O(1) (constant time: the same small amount of work no matter how many items there are). No searching the whole stack.

Think out loud. - Real life: a shopkeeper stacks shirts on the counter, each with a price tag. Customers keep asking: "what's the cheapest one in the pile?" - Push 50, 30, 70, 10: the min is 10. Pop the 10: now the min is 30. - Edge cases: popping the minimum itself, and an empty stack.

Attempt: one min variable

Keep one variable, min, starting at Infinity (a special number bigger than every other number, so the first price is always smaller). On push, if the new price is smaller, update min.

class MinStack {
  constructor() { this.items = []; this.min = Infinity; }
  push(x) {
    this.items.push(x);
    if (x < this.min) this.min = x;
  }
  pop() { return this.items.pop(); }
  getMin() { return this.min; }
}
const shirts = new MinStack();
shirts.push(50); shirts.push(30); shirts.push(70); shirts.push(10);
console.log("min:", shirts.getMin());
shirts.pop();
console.log("after popping 10, min:", shirts.getMin());
min: 10
after popping 10, min: 10

Min 10: correct. But after popping 10, the min is still 10. The 10-rupee shirt is gone, and the answer is stale (out of date). Why? One variable remembers only the current minimum, not the one before it. When that shirt leaves, we don't know what the minimum was underneath. We'd have to search the whole pile again, which is O(n).

Fix: a second stack of minimums

The shopkeeper sticks a note on every shirt: "the cheapest price from this shirt down". The note on a new shirt is the smaller of its own price and the note on the shirt below. The top note is always the answer, and when a shirt leaves, its note leaves with it, so the note underneath is right again. In code, the notes are a second array, mins, that grows and shrinks together with items.

class MinStack {
  constructor() { this.items = []; this.mins = []; }
  push(x) {
    this.items.push(x);
    const m = this.mins.length ? this.mins.at(-1) : Infinity;
    this.mins.push(Math.min(x, m));
  }
  pop() { this.mins.pop(); return this.items.pop(); }
  getMin() { return this.mins.at(-1); }
}
const shirts = new MinStack();
shirts.push(50); shirts.push(30); shirts.push(70); shirts.push(10);
console.log("min:", shirts.getMin());
shirts.pop();
console.log("after popping 10, min:", shirts.getMin());
shirts.pop(); shirts.pop();
console.log("after two more pops, min:", shirts.getMin());
shirts.pop();
console.log("empty:", shirts.getMin());
min: 10
after popping 10, min: 30
after two more pops, min: 50
empty: undefined
  • this.mins.length ? this.mins.at(-1) : Infinity: if mins has items (a length of 0 counts as false), take its top; otherwise Infinity. (cond ? a : b is the ternary operator: "if cond, a, else b".)
  • Math.min(x, m) returns the smaller of the two.
  • 10, then 30 after popping 10, then 50, and undefined for an empty stack, because at(-1) of an empty array is undefined.

Here are both stacks after every step:

const items = [];
const mins = [];
for (const price of [50, 30, 70, 10]) {
  items.push(price);
  const m = mins.length ? mins.at(-1) : Infinity;
  mins.push(Math.min(price, m));
  console.log(`push ${price}:`.padEnd(9), "items", items, "mins", mins);
}
while (items.length) {
  const gone = items.pop();
  mins.pop();
  console.log(`pop ${gone}:`.padEnd(9), "items", items, "mins", mins, "min:", mins.at(-1));
}
push 50:  items [ 50 ] mins [ 50 ]
push 30:  items [ 50, 30 ] mins [ 50, 30 ]
push 70:  items [ 50, 30, 70 ] mins [ 50, 30, 30 ]
push 10:  items [ 50, 30, 70, 10 ] mins [ 50, 30, 30, 10 ]
pop 10:   items [ 50, 30, 70 ] mins [ 50, 30, 30 ] min: 30
pop 70:   items [ 50, 30 ] mins [ 50, 30 ] min: 30
pop 30:   items [ 50 ] mins [ 50 ] min: 50
pop 50:   items [] mins [] min: undefined

(padEnd(9) adds spaces until the label is 9 characters long, so the columns line up.) Notice 70's note says 30: 70 is not the cheapest, so it copies the note below it.

Complexity: push, pop and getMin each do a fixed amount of work: O(1) time. The price is memory: a second stack of n notes, so O(n) extra space.

Q2: A queue using two stacks

Problem. Build a queue with enqueue(x) and dequeue(), but you may only use two stacks, with push and pop (no shift, no reading by index). First in must be first out: enqueue Asha, Ravi, Neha, then dequeue gives Asha, then Ravi.

Think out loud. - Real life: an office with an IN tray and an OUT tray for letters. - Pouring one stack into another flips the order: the item at the bottom ends up on top. So the oldest item (at the bottom of the first stack) becomes the top of the second. - Edge cases: new people joining between dequeues, dequeuing from an empty queue, and 20,000 items.

Attempt: pour everything over and back on every dequeue

enqueue pushes onto inbox. To dequeue: pour everything from inbox into outbox (now the oldest is on top), pop it, then pour everything back.

class Queue {
  constructor() { this.inbox = []; this.outbox = []; }
  enqueue(x) { this.inbox.push(x); }
  dequeue() {
    while (this.inbox.length) this.outbox.push(this.inbox.pop());
    const front = this.outbox.pop();
    while (this.outbox.length) this.inbox.push(this.outbox.pop());
    return front;
  }
}
const counter = new Queue();
counter.enqueue("Asha"); counter.enqueue("Ravi"); counter.enqueue("Neha");
console.log(counter.dequeue(), counter.dequeue());
const big = new Queue();
for (let i = 0; i < 20000; i++) big.enqueue(i);
console.time("20,000 dequeues");
for (let i = 0; i < 20000; i++) big.dequeue();
console.timeEnd("20,000 dequeues");

What we got (the time will differ on your machine):

Asha Ravi
20,000 dequeues: 2.646s

Asha, then Ravi: correct. But 20,000 dequeues took seconds. Why? Every single dequeue moves every item twice, over and back. With n items, each dequeue is O(n), so n dequeues is O(n²): about 20,000 × 20,000 = 400 million moves. The pouring back is the waste.

Fix: refill the outbox only when it's empty

In the office, new letters go on the IN tray. When the OUT tray is empty, the clerk turns the whole IN pile over onto it, so the oldest letter is on top. The clerk takes letters from the OUT tray, and never flips anything back. New letters keep going on the IN tray meanwhile; they wait until the OUT tray runs out.

class Queue {
  constructor() { this.inbox = []; this.outbox = []; }
  enqueue(x) { this.inbox.push(x); }
  dequeue() {
    if (this.outbox.length === 0)
      while (this.inbox.length) this.outbox.push(this.inbox.pop());
    return this.outbox.pop();
  }
}
const counter = new Queue();
counter.enqueue("Asha"); counter.enqueue("Ravi"); counter.enqueue("Neha");
console.log(counter.dequeue(), counter.dequeue());
counter.enqueue("Kabir");
console.log(counter.dequeue(), counter.dequeue(), counter.dequeue());
const big = new Queue();
for (let i = 0; i < 20000; i++) big.enqueue(i);
console.time("20,000 dequeues");
for (let i = 0; i < 20000; i++) big.dequeue();
console.timeEnd("20,000 dequeues");
Asha Ravi
Neha Kabir undefined
20,000 dequeues: 6.96ms
  • Asha, Ravi. Then Neha before Kabir, because Neha came first, even though Kabir joined while Neha was already in the outbox.
  • Then undefined: the queue is empty, and pop() of an empty array is undefined.
  • 20,000 dequeues in a few milliseconds instead of seconds.

Here is what the two trays hold after every step:

const inbox = [];
const outbox = [];
const show = (label) => console.log(label.padEnd(18), "inbox", inbox, "outbox", outbox);
function enqueue(x) {
  inbox.push(x);
  show(`enqueue ${x}`);
}
function dequeue() {
  if (outbox.length === 0) {
    while (inbox.length) outbox.push(inbox.pop());
    show("  (flip)");
  }
  const front = outbox.pop();
  show(`dequeue → ${front}`);
  return front;
}
enqueue("Asha"); enqueue("Ravi"); enqueue("Neha");
dequeue();
enqueue("Kabir");
dequeue(); dequeue(); dequeue();
enqueue Asha       inbox [ 'Asha' ] outbox []
enqueue Ravi       inbox [ 'Asha', 'Ravi' ] outbox []
enqueue Neha       inbox [ 'Asha', 'Ravi', 'Neha' ] outbox []
  (flip)           inbox [] outbox [ 'Neha', 'Ravi', 'Asha' ]
dequeue → Asha     inbox [] outbox [ 'Neha', 'Ravi' ]
enqueue Kabir      inbox [ 'Kabir' ] outbox [ 'Neha', 'Ravi' ]
dequeue → Ravi     inbox [ 'Kabir' ] outbox [ 'Neha' ]
dequeue → Neha     inbox [ 'Kabir' ] outbox []
  (flip)           inbox [] outbox [ 'Kabir' ]
dequeue → Kabir    inbox [] outbox []

(Arrays print with the top of the stack on the right.) Only two flips for four people, and Kabir waits in the inbox until Ravi and Neha are gone.

Amortised O(1): count the moves

One dequeue can be slow: the one that flips the pile. But look at a single item's whole life: pushed onto the inbox once, popped from the inbox once, pushed onto the outbox once, popped from the outbox once. Four cheap steps, never more, because nothing is flipped back. So n items cost about 4n steps in total, and the average per operation is O(1), even though one operation now and then is O(n). That's called amortised O(1) ("amortised" = the cost spread out over many operations, like paying for a monthly train pass instead of each ticket).

We count how many items each flip moves:

class Queue {
  constructor() { this.inbox = []; this.outbox = []; this.moves = 0; }
  enqueue(x) { this.inbox.push(x); }
  dequeue() {
    if (this.outbox.length === 0)
      while (this.inbox.length) { this.outbox.push(this.inbox.pop()); this.moves++; }
    return this.outbox.pop();
  }
}
const q = new Queue();
for (let i = 1; i <= 8; i++) q.enqueue(i);
const costs = [];
for (let i = 0; i < 8; i++) {
  const before = q.moves;
  q.dequeue();
  costs.push(q.moves - before);
}
console.log("items moved by each dequeue:", costs);

for (const n of [10000, 100000, 1000000]) {
  const big = new Queue();
  for (let i = 0; i < n; i++) {
    big.enqueue(i);
    if (i % 3 === 0) big.dequeue();
  }
  while (big.dequeue() !== undefined);
  console.log(`${n} items: ${big.moves} moves, ${(big.moves / n).toFixed(2)} per item`);
}
items moved by each dequeue: [
  8, 0, 0, 0,
  0, 0, 0, 0
]
10000 items: 10000 moves, 1.00 per item
100000 items: 100000 moves, 1.00 per item
1000000 items: 1000000 moves, 1.00 per item
  • The first dequeue moves all 8 items; the next seven move nothing. Spread over 8 dequeues, that's 1 move each.
  • With enqueues and dequeues mixed (i % 3 === 0 dequeues on every third item), it's still exactly 1 move per item, for 10,000 or a million items. (toFixed(2) prints a number with 2 decimals.)
  • while (big.dequeue() !== undefined); empties the queue: the loop body is empty, all the work is in the condition.

Complexity: amortised O(1) per enqueue and dequeue (worst case O(n) for one dequeue). Space O(n).

Q3: Next greater element

Problem. For each day's temperature, find the first later day that is warmer. If there is none, -1. [31, 28, 33, 30, 29, 35] → [33, 33, 35, 35, 35, -1].

Think out loud. - Real life: "when does it get warmer than today?" - 31: the next warmer is 33. 28: also 33. 35: nothing warmer after it, so -1. - Edge cases: equal temperatures don't count as warmer; an empty list; and 100,000 days that keep getting cooler.

Attempt: nested loops

For each day i, look at every later day j and stop at the first warmer one.

function nextGreater(temps) {
  const out = [];
  for (let i = 0; i < temps.length; i++) {
    let found = -1;
    for (let j = i + 1; j < temps.length; j++)
      if (temps[j] > temps[i]) { found = temps[j]; break; }
    out.push(found);
  }
  return out;
}
console.log(nextGreater([31, 28, 33, 30, 29, 35]));
const cooling = Array.from({ length: 100000 }, (_, i) => 100000 - i);
console.time("100,000 days");
nextGreater(cooling);
console.timeEnd("100,000 days");

What we got (timings vary):

[ 33, 33, 35, 35, 35, -1 ]
100,000 days: 4.499s

The small answer is right. But 100,000 cooling days (100000, 99999, …, 1) took seconds. Why? When the days keep getting cooler, there is never a warmer day, so break never happens and every day scans every later day: about n² / 2 = 5 billion comparisons. Worst case O(n²).

Fix: a stack of days still waiting (monotonic stack)

Think of a waiting list of days that don't have their answer yet. 1. Day 0, 31°, goes on the list. 2. 28° is colder, so it can't answer anyone. It waits too, on top. The list always goes from warmer at the bottom to colder at the top. 3. 33° arrives. It's warmer than the top, 28, so it answers 28 and removes it. Still warmer than 31: answers that too. Then 33 waits. 4. Every day joins the list once and leaves at most once. No day is scanned again and again.

A stack whose items are always in order (here: getting colder from bottom to top) is called a monotonic stack ("monotonic" = only going one way).

function nextGreater(temps) {
  const out = new Array(temps.length).fill(-1);
  const stack = []; // indexes still waiting for a warmer day
  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[i] > temps[stack.at(-1)])
      out[stack.pop()] = temps[i];
    stack.push(i);
  }
  return out;
}
console.log(nextGreater([31, 28, 33, 30, 29, 35]));
console.log(nextGreater([5, 5, 5]), nextGreater([]));
const cooling = Array.from({ length: 100000 }, (_, i) => 100000 - i);
console.time("100,000 days");
nextGreater(cooling);
console.timeEnd("100,000 days");
[ 33, 33, 35, 35, 35, -1 ]
[ -1, -1, -1 ] []
100,000 days: 5.338ms
  • new Array(n).fill(-1) makes an array of n -1s: every day starts with "no warmer day"; days that never leave the stack keep it.
  • The stack holds indexes (day numbers), not temperatures: when a day is answered, we need to know where to write the answer (out[stack.pop()] = …). temps[stack.at(-1)] is the temperature of the day on top.
  • Equal fives give -1s, because of the strict >: 5 is not greater than 5. An empty list gives [].
  • The 100,000 cooling days: milliseconds, not seconds. Every day just waits on the stack.

Here is the waiting list, day by day:

const temps = [31, 28, 33, 30, 29, 35];
const out = new Array(temps.length).fill(-1);
const stack = [];
for (let i = 0; i < temps.length; i++) {
  while (stack.length && temps[i] > temps[stack.at(-1)]) {
    const j = stack.pop();
    out[j] = temps[i];
    console.log(`  day ${i} (${temps[i]}) answers day ${j} (${temps[j]})`);
  }
  stack.push(i);
  console.log(`day ${i} (${temps[i]}) waits. stack of temps:`, stack.map((k) => temps[k]));
}
console.log(out);
day 0 (31) waits. stack of temps: [ 31 ]
day 1 (28) waits. stack of temps: [ 31, 28 ]
  day 2 (33) answers day 1 (28)
  day 2 (33) answers day 0 (31)
day 2 (33) waits. stack of temps: [ 33 ]
day 3 (30) waits. stack of temps: [ 33, 30 ]
day 4 (29) waits. stack of temps: [ 33, 30, 29 ]
  day 5 (35) answers day 4 (29)
  day 5 (35) answers day 3 (30)
  day 5 (35) answers day 2 (33)
day 5 (35) waits. stack of temps: [ 35 ]
[ 33, 33, 35, 35, 35, -1 ]

The stack of temperatures is always colder towards the top: [33, 30, 29]. Day 5 answers three days at once, and they are never looked at again.

Complexity: the while loop looks nested, but each index is pushed once and popped at most once, so all the while steps together are at most n. Total time O(n); space O(n) for the stack (when the days keep getting cooler, all of them wait).

Going further

A queue with a head index (no shift)

Instead of moving everyone forward, keep a head index: the place of the person at the front. Dequeue reads items[head] and adds 1 to head. Nobody moves. To stop the array from growing forever, when more than half of it is used-up front part, copy the rest once (slice) and reset head to 0: that occasional copy is amortised O(1), like the two-stack flip.

class HeadQueue {
  constructor() { this.items = []; this.head = 0; }
  enqueue(x) { this.items.push(x); }
  dequeue() {
    if (this.head === this.items.length) return undefined;
    const front = this.items[this.head];
    this.items[this.head] = undefined; // let the old value be freed
    this.head++;
    if (this.head > 1000 && this.head * 2 > this.items.length) {
      this.items = this.items.slice(this.head); // drop the used front part
      this.head = 0;
    }
    return front;
  }
  peek() { return this.items[this.head]; }
  get size() { return this.items.length - this.head; }
}
const counter = new HeadQueue();
counter.enqueue("Asha"); counter.enqueue("Ravi"); counter.enqueue("Neha");
console.log(counter.dequeue(), counter.peek(), counter.size);
console.log(counter.dequeue(), counter.dequeue(), counter.dequeue(), counter.size);

const big = new HeadQueue();
for (let i = 0; i < 200000; i++) big.enqueue(i);
console.time("200,000 dequeues, head index");
for (let i = 0; i < 200000; i++) big.dequeue();
console.timeEnd("200,000 dequeues, head index");

const arr = Array.from({ length: 200000 }, (_, i) => i);
console.time("200,000 shifts");
for (let i = 0; i < 200000; i++) arr.shift();
console.timeEnd("200,000 shifts");

What we got (timings vary):

Asha Ravi 2
Ravi Neha undefined 0
200,000 dequeues, head index: 5.401ms
200,000 shifts: 3.427s
  • get size() is a getter: you read it like a property (counter.size, no brackets), but it runs code.
  • peek() looks at the front without removing it. After dequeuing Asha, Ravi is at the front and 2 people are left.
  • Same 200,000 items: milliseconds with a head index, seconds with shift. In an interview, "use a head index" or "two stacks" are both good answers to "make a fast queue in JavaScript".

Max stack

The same idea as min stack, with Math.max and -Infinity (smaller than every number). Real life: an auction where bids can be withdrawn, newest first; "what's the highest bid still standing?"

class MaxStack {
  constructor() { this.items = []; this.maxes = []; }
  push(x) {
    this.items.push(x);
    const m = this.maxes.length ? this.maxes.at(-1) : -Infinity;
    this.maxes.push(Math.max(x, m));
  }
  pop() { this.maxes.pop(); return this.items.pop(); }
  peek() { return this.items.at(-1); }
  getMax() { return this.maxes.at(-1); }
}
const bids = new MaxStack();
for (const b of [200, 500, 300, 500, 100]) bids.push(b);
console.log("max:", bids.getMax());
bids.pop(); bids.pop();
console.log("after 2 pops:", bids.getMax(), "top:", bids.peek());
bids.pop();
console.log("after popping the first 500:", bids.getMax());
bids.pop(); bids.pop();
console.log("empty:", bids.getMax(), bids.pop());
max: 500
after 2 pops: 500 top: 300
after popping the first 500: 500
empty: undefined undefined

After popping 100, 500 and 300, why is the max still 500? Because the stack is now [200, 500]: the first 500 is still there. Duplicates are no problem, because every item has its own note. This is a good test case to try on any min/max stack.

Valid parentheses (recap)

The most famous stack question. Every opening bracket goes on the stack; every closing bracket must match the last unmatched opening one (LIFO). At the end, the stack must be empty.

function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") stack.push(ch);
    else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}
for (const s of ["(a[b]{c})", "([)]", "((", "())", "", "if (x) { y[0]; }"])
  console.log(JSON.stringify(s).padEnd(20), isValid(s));
"(a[b]{c})"          true
"([)]"               false
"(("                 false
"())"                false
""                   true
"if (x) { y[0]; }"   true
  • ch in pairs is true if ch is one of the object's keys (a closing bracket). Other characters are ignored.
  • "([)]": ) arrives while [ is on top: wrong order, false.
  • "((": nothing wrong on the way, but two brackets are still open at the end: false.
  • "())": the last ) pops an empty stack, which gives undefined, not "(": false.
  • O(n) time, O(n) space.

Next greater in a circular array

In a circular array, after the last item you wrap around to the first. Real life: temperatures for each day of the week, and the week repeats. Trick: loop twice (k from 0 to 2n - 1) and use i = k % n (the remainder) to wrap around. Push indexes only in the first round, so each day is answered at most once.

function nextGreaterCircular(nums) {
  const n = nums.length;
  const out = new Array(n).fill(-1);
  const stack = [];
  for (let k = 0; k < 2 * n; k++) {
    const i = k % n;
    while (stack.length && nums[i] > nums[stack.at(-1)]) out[stack.pop()] = nums[i];
    if (k < n) stack.push(i);
  }
  return out;
}
console.log(nextGreaterCircular([31, 28, 33, 30, 29, 35]));
console.log(nextGreaterCircular([35, 29, 30, 31]));
console.log(nextGreaterCircular([5, 5, 5]), nextGreaterCircular([]));
[ 33, 33, 35, 35, 35, -1 ]
[ -1, 30, 31, 35 ]
[ -1, -1, -1 ] []

In [35, 29, 30, 31], the last day, 31, wraps around and finds 35. The maximum (35) still has nothing greater anywhere: -1. Still O(n): 2n steps.

Previous smaller element

The mirror question: for each price, the nearest earlier price that is smaller (-1 if none). Real life: "when did I last see it cheaper?" This time we pop everything that is not smaller (>=); whatever is left on top is the answer. The stack holds values getting bigger towards the top.

function previousSmaller(prices) {
  const out = [];
  const stack = []; // values, smallest at the bottom
  for (const p of prices) {
    while (stack.length && stack.at(-1) >= p) stack.pop();
    out.push(stack.length ? stack.at(-1) : -1);
    stack.push(p);
  }
  return out;
}
console.log(previousSmaller([40, 25, 30, 10, 35, 30]));
console.log(previousSmaller([1, 2, 3, 4]));
console.log(previousSmaller([4, 3, 2, 1]));
console.log(previousSmaller([7, 7, 7]));
[ -1, -1, 25, -1, 10, 10 ]
[ -1, 1, 2, 3 ]
[ -1, -1, -1, -1 ]
[ -1, -1, -1 ]

Here the answer comes from what stays on the stack, not from what is popped, and we can store values because each answer is written right away at the current position. Monotonic stacks always come in these four flavours: next or previous, greater or smaller. O(n).

Complexity summary

Solution Time Extra space
push / pop on an array O(1) none
shift() on an array O(n) per call; O(n²) to empty the array none
Min stack, one min variable O(1), but wrong after popping the minimum O(1)
Min stack (or max stack) with a second stack O(1) for push, pop, getMin O(n)
Queue from two stacks, pour back every time O(n) per dequeue; O(n²) for n dequeues O(n)
Queue from two stacks, refill only when empty amortised O(1); one dequeue can be O(n) O(n)
Queue with a head index amortised O(1) (with the occasional slice) O(n)
Next greater, nested loops O(n²) worst case (cooling days) O(n) for the answer
Next greater, monotonic stack O(n): each index pushed once, popped at most once O(n)
Next greater, circular O(n): 2n steps O(n)
Previous smaller O(n) O(n)
Valid parentheses O(n) O(n)
daysToWait (your turn) O(n) O(n)

Amortised O(1) means: some single operations are expensive, but they are rare enough that the total over n operations is O(n), so the average per operation is O(1). In the two-stack queue, each item is moved from inbox to outbox only once in its life. In the monotonic stack, the same reasoning gives O(n) overall: one push and at most one pop per index.

Common mistakes (and the exact outputs)

Mistake Code What you see Why Fix
One min variable if (x < this.min) this.min = x after popping 10, min: 10 it forgets the earlier minimums a second stack of mins
Forgetting to pop mins pop() { return this.items.pop(); } after popping 10, min: 10 the two stacks get out of step this.mins.pop() in pop()
Math.min over an empty list Math.min(...[]) Infinity no numbers, so the "starting value" comes back check the length, or use at(-1) on mins
arr[-1] for the top values[-1] undefined [] doesn't count from the end values.at(-1) or values[values.length - 1]
Pouring back after every dequeue while (this.outbox.length) this.inbox.push(...) 20,000 dequeues: 2.646s (on our machine) O(n) per dequeue refill only when outbox is empty
shift() in a hot loop while (a.length) a.shift() on 200,000 items 200000 shifts: 3.412s (on our machine) every item moves forward: O(n) two stacks, or a head index
Nested loops for next greater for i … for j … 100,000 days: 4.499s (on our machine) O(n²) when nothing is greater a monotonic stack: O(n)
>= instead of > temps[i] >= temps[stack.at(-1)] on [5, 5, 5] [ 5, 5, -1 ] equal is not greater temps[i] > temps[stack.at(-1)]
Values instead of indexes on the stack out.push(t) when popping [ 30, 35, 35, 35 ] for [33, 28, 30, 29, 35] answers come out in pop order, and the -1 is lost push indexes, write out[stack.pop()]

The last trap, for real. The right answer for [33, 28, 30, 29, 35] is [35, 30, 35, 35, -1]:

function nextGreaterValues(temps) {
  const out = [];
  const stack = []; // temperatures, not indexes
  for (const t of temps) {
    while (stack.length && t > stack.at(-1)) {
      stack.pop();
      out.push(t);
    }
    stack.push(t);
  }
  return out;
}
console.log(nextGreaterValues([33, 28, 30, 29, 35]));
[ 30, 35, 35, 35 ]

Four answers for five days, and day 0's answer (35) comes last, because day 0 was popped last. With values only, we can't tell which day an answer belongs to.

And the mins and at traps, for real:

class MinStack {
  constructor() { this.items = []; this.mins = []; }
  push(x) {
    this.items.push(x);
    const m = this.mins.length ? this.mins.at(-1) : Infinity;
    this.mins.push(Math.min(x, m));
  }
  pop() { return this.items.pop(); } // forgot this.mins.pop()
  getMin() { return this.mins.at(-1); }
}
const s = new MinStack();
s.push(50); s.push(30); s.push(70); s.push(10);
s.pop();
console.log("after popping 10, min:", s.getMin());

console.log(Math.min(...[]), [].at(-1), [][[].length - 1]);
const values = [3, 1, 2];
console.log(values.at(-1), values[values.length - 1], values[-1]);
after popping 10, min: 10
Infinity undefined undefined
2 2 undefined
  • Forgetting this.mins.pop() gives the same stale 10 as the one-variable version.
  • Math.min() with no numbers is Infinity. That's why MinStack starts from Infinity: it's the "no minimum yet" value.
  • values.at(-1) and values[values.length - 1] are both 2; values[-1] is undefined.

Mini project: undo and redo in a text editor

Every editor has undo (Ctrl+Z) and redo. That's two stacks: before each change, push the old text onto the undo stack. Undo pops it back and pushes the current text onto the redo stack. Redo does the opposite. Typing something new clears the redo stack (you can't redo into a different future).

class Editor {
  constructor() { this.text = ""; this.undoStack = []; this.redoStack = []; }
  type(words) {
    this.undoStack.push(this.text);
    this.redoStack = []; // new typing clears the redo history
    this.text += words;
  }
  undo() {
    if (this.undoStack.length === 0) return false;
    this.redoStack.push(this.text);
    this.text = this.undoStack.pop();
    return true;
  }
  redo() {
    if (this.redoStack.length === 0) return false;
    this.undoStack.push(this.text);
    this.text = this.redoStack.pop();
    return true;
  }
}
const ed = new Editor();
ed.type("Dear Sir,");
ed.type(" please send");
ed.type(" the invoice.");
console.log(JSON.stringify(ed.text));
ed.undo(); ed.undo();
console.log("undo x2:", JSON.stringify(ed.text));
ed.redo();
console.log("redo:   ", JSON.stringify(ed.text));
ed.type(" the bill.");
console.log("type:   ", JSON.stringify(ed.text));
console.log("redo now?", ed.redo(), "| stacks:", ed.undoStack.length, ed.redoStack.length);
ed.undo(); ed.undo(); ed.undo();
console.log("undo x3:", JSON.stringify(ed.text), "| undo again?", ed.undo());
"Dear Sir, please send the invoice."
undo x2: "Dear Sir,"
redo:    "Dear Sir, please send"
type:    "Dear Sir, please send the bill."
redo now? false | stacks: 3 0
undo x3: "" | undo again? false
  • JSON.stringify(text) prints the text in quotes, so an empty string "" is visible.
  • Undo twice goes back two steps; redo brings one back. Typing " the bill." clears the redo stack: redo() returns false and the redo stack has 0 items.
  • Three undos go all the way back to the empty start, and a fourth has nothing left: false.
  • Every operation is O(1) (the stacks hold whole texts here, so space grows with the number of edits; real editors store only the changes).
  • Ideas to extend it: a limit of 50 undo steps (drop the oldest), or a delete(n) command that removes the last n characters.

Your turn: how many days to wait? (solution)

Problem. Write daysToWait(temps): for each day, how many days until a warmer day, or 0 if it never comes. [31, 28, 33, 30, 29, 35] → [2, 1, 3, 2, 1, 0]. 31 waits 2 days (for 33), 28 waits 1.

Hint from the video: it's the same stack of indexes; when day i answers a waiting day j, the wait is i - j.

function daysToWait(temps) {
  const out = new Array(temps.length).fill(0);
  const stack = []; // indexes of days still waiting
  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[i] > temps[stack.at(-1)]) {
      const j = stack.pop();
      out[j] = i - j;
    }
    stack.push(i);
  }
  return out;
}
console.log(daysToWait([31, 28, 33, 30, 29, 35]));
console.log(daysToWait([30, 30, 30]), daysToWait([]));
console.log(daysToWait([40, 39, 38, 41]));
const cooling = Array.from({ length: 100000 }, (_, i) => 100000 - i);
console.time("100,000 days");
const res = daysToWait(cooling);
console.timeEnd("100,000 days");
console.log(res.every((d) => d === 0));

What we got (the timing varies):

[ 2, 1, 3, 2, 1, 0 ]
[ 0, 0, 0 ] []
[ 3, 2, 1, 0 ]
100,000 days: 8.054ms
true
  • Two changes from nextGreater: the array starts full of 0 (not -1), and we write i - j (the distance) instead of temps[i] (the value). This is why the stack must hold indexes: with temperatures alone you can't compute a distance.
  • Equal days [30, 30, 30] never get warmer: all 0. Empty list: [].
  • [40, 39, 38, 41]: all three cooler days are answered at once by 41, after 3, 2 and 1 days.
  • 100,000 cooling days in milliseconds; res.every((d) => d === 0) checks that every answer is 0 (nobody ever gets a warmer day).
  • O(n) time, O(n) space. On LeetCode this question is called "Daily Temperatures".

Practice questions (with solutions)

1. Reverse the words of a sentence with a stack. "chai is ready" → "ready is chai".

Solution
function reverseWords(sentence) {
  const stack = sentence.split(" ").filter((w) => w !== "");
  const out = [];
  while (stack.length) out.push(stack.pop());
  return out.join(" ");
}
console.log(reverseWords("chai is ready"));
console.log(JSON.stringify(reverseWords("  two   spaces ")));
console.log(JSON.stringify(reverseWords("")));
ready is chai
"spaces two"
""

split(" ") cuts the sentence at every space; filter((w) => w !== "") drops the empty pieces that extra spaces leave behind. Popping a stack gives the words back in reverse order (LIFO). O(n).

2. A stack using two queues (the homework from the video). Use each queue only as a queue: push at the back, shift from the front.

Solution
class StackFromQueues {
  // each queue is used only as a queue: push at the back, shift from the front
  constructor() { this.main = []; this.helper = []; }
  push(x) {
    this.helper.push(x);
    while (this.main.length) this.helper.push(this.main.shift());
    [this.main, this.helper] = [this.helper, this.main];
  }
  pop() { return this.main.shift(); }
  top() { return this.main[0]; }
}
const s = new StackFromQueues();
s.push(1); s.push(2); s.push(3);
console.log(s.main, s.helper);
console.log(s.pop(), s.top(), s.pop(), s.pop(), s.pop());
[ 3, 2, 1 ] []
3 2 2 1 undefined

The new item goes into the empty helper queue first, then everything from main follows behind it, so the newest item is at the front. Then the two queues swap names ([a, b] = [b, a] is destructuring, a one-line swap). pop just dequeues the front: 3, then 2, then 1, then undefined. Push is O(n) (every item moves), pop is O(1). Unlike the two-stack queue, there's no amortised trick here: each push really costs O(n).

3. Stock span. For each day's share price, how many days in a row, ending today, had a price less than or equal to today's? [100, 80, 60, 70, 60, 75, 85] → [1, 1, 1, 2, 1, 4, 6].

Solution
function stockSpan(prices) {
  const out = [];
  const stack = []; // indexes of days with a higher price
  for (let i = 0; i < prices.length; i++) {
    while (stack.length && prices[stack.at(-1)] <= prices[i]) stack.pop();
    out.push(stack.length ? i - stack.at(-1) : i + 1);
    stack.push(i);
  }
  return out;
}
console.log(stockSpan([100, 80, 60, 70, 60, 75, 85]));
console.log(stockSpan([10, 20, 30]), stockSpan([30, 20, 10]));
[
  1, 1, 1, 2,
  1, 4, 6
]
[ 1, 2, 3 ] [ 1, 1, 1 ]

(Node prints a longer array of numbers over several lines.) It's the previous greater element in disguise: pop every day that is not higher; the day left on top is the last higher price, and the span is the distance to it. If nothing is left, every day so far counts: i + 1. Rising prices give [1, 2, 3], falling prices [1, 1, 1]. O(n).

Quick quiz

const s = [];
s.push(1); s.push(2); s.push(3);
const q = [...s];
console.log(s.pop(), s.pop());
console.log(q.shift(), q.shift());

A) 3 2, then 1 2 B) 1 2, then 3 2 C) 3 2, then 3 2 D) 1 2, then 1 2

Answer
3 2
1 2

A. pop takes from the end, like a stack (LIFO): 3, then 2. q is a copy made with the spread syntax [...s] before the pops, so it still holds [1, 2, 3], and shift takes from the front, like a queue (FIFO): 1, then 2.

Interview questions

  1. What's the difference between a stack and a queue? A stack is LIFO (last in, first out: push and pop at the same end). A queue is FIFO (first in, first out: add at the back, remove from the front).
  2. How do you make a stack in JavaScript? A plain array with push, pop and at(-1) for peek. All O(1).
  3. Why is shift() slow on big arrays? It removes index 0, so every other item moves one place forward: O(n) per call.
  4. How does a min stack get the minimum in O(1)? It keeps a second stack: each entry is the minimum of everything at or below that position. Push and pop both stacks together; the top of mins is the answer.
  5. Why doesn't one min variable work? After popping the minimum, it still holds the old value, and the previous minimum is lost.
  6. How do you build a queue from two stacks? Enqueue onto an inbox. Dequeue from an outbox; only when the outbox is empty, pour the whole inbox into it (which reverses the order). Never pour back.
  7. What does amortised O(1) mean? One operation can be expensive, but the total over n operations is O(n), so the average is O(1). In the two-stack queue, each item moves from inbox to outbox only once.
  8. What is a monotonic stack? A stack kept in sorted order (always increasing or always decreasing) by popping items that break the order before each push. It solves next/previous greater/smaller in O(n).
  9. Why does the next greater stack store indexes, not values? To know where to write each answer, and to compute distances (like days to wait).
  10. The while inside the for looks like O(n²). Why is it O(n)? Each index is pushed once and popped at most once, so the while runs at most n times in total across the whole loop.

Glossary

Term Meaning
Stack A collection where you add and remove at the same end (the top), like a pile of plates
Queue A collection where you add at the back and remove from the front, like a ticket line
LIFO "Last in, first out": the rule of a stack
FIFO "First in, first out": the rule of a queue
Top The end of a stack where items are added and removed; the last item of the array
Front / back The end of a queue where items leave / join
push Add an item to the end of an array (the top of a stack, or the back of a queue)
pop Remove and return the last item of an array; undefined if it's empty
shift Remove and return the first item of an array; every other item moves forward, so O(n)
Peek Look at the top (or front) item without removing it
Enqueue Add an item to the back of a queue
Dequeue Remove the item at the front of a queue
Min stack A stack that can also give its smallest item in O(1), using a second stack of minimums
Max stack The same, for the largest item, with Math.max and -Infinity
Stale value A value that was right once but is out of date now (the old min after a pop)
Inbox / outbox The two stacks of a two-stack queue: new items go in the inbox; items leave from the outbox
Head index A number pointing to the front of a queue stored in an array, so nobody has to move
Amortised O(1) Some operations are slow, but the total over n operations is O(n), so O(1) on average
Monotonic stack A stack whose items always go in one direction (for example, colder towards the top)
Next greater element For each item, the first later item that is strictly bigger (-1 if none)
Previous smaller element For each item, the nearest earlier item that is strictly smaller (-1 if none)
Circular array An array where you wrap around from the last item back to the first
Index The position number of an item in an array, starting at 0
at(-1) Reads the last item of an array (at with a negative number counts from the end)
arr[-1] Not the last item: just undefined
Infinity / -Infinity Special numbers bigger / smaller than every other number
Math.min / Math.max The smallest / largest of the numbers given; Math.min() with none is Infinity
% (remainder) What is left after division: 7 % 6 is 1, used to wrap around in a circular array
Big-O How the work grows as the input grows
O(1), O(n), O(n²) Constant work / work in step with n / work growing with n times n
console.time / console.timeEnd Start a timer with a label / print how long it took since then
Array.from({ length: n }, fn) Make an array of n items, item i being fn(_, i)
new Array(n).fill(x) Make an array of n copies of x
class / constructor A blueprint for objects / the function that sets up each new object
this Inside a class method, the object the method was called on
Getter (get size()) A method you read like a property, without brackets
Ternary operator cond ? a : b: a if cond is true, else b
Spread (...) Spreads out an array's values: [...s] copies an array; Math.min(...arr) passes them one by one
Destructuring swap [a, b] = [b, a]: swap two variables in one line
padEnd(n) Add spaces to the end of a string until it is n characters long
JSON.stringify Turns a value into text, so strings show their quotes and "" is visible
every true if a test passes for every item of an array
Undo / redo stack The two stacks an editor uses to go back and forward through changes

Summary

  • A stack is LIFO (push / pop / at(-1)); a queue is FIFO. On an array, push and pop are O(1), but shift() is O(n): we measured 200,000 shifts in seconds and 200,000 pops in under a millisecond.
  • Min stack: one min variable goes stale after a pop. Keep a second stack of minimums, pushed and popped together: every operation O(1), O(n) extra space.
  • Queue from two stacks: pouring back on every dequeue is O(n²). Refill the outbox only when it's empty and never pour back: each item moves once, so amortised O(1). A head index is another fast queue.
  • Next greater element: nested loops are O(n²) on cooling days. A monotonic stack of waiting indexes answers each day when a warmer one arrives: each index pushed once, popped at most once, O(n). Use strict >, and store indexes so you know where to write.
  • The same stack gives days to wait (i - j), next greater in a circular array (loop twice), previous smaller and stock span.
  • Next episode: Map and Set questions: an LRU cache built with a Map, grouping anagrams, and the longest consecutive sequence.