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+shiftmake a queue. arr.at(-1)reads the last item (the top of a stack). A negative index inatcounts from the end;arr[-1]does not work (it'sundefined).
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
shiftcheap 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: ifminshas items (a length of 0 counts as false), take its top; otherwiseInfinity. (cond ? a : bis 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
undefinedfor an empty stack, becauseat(-1)of an empty array isundefined.
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, andpop()of an empty array isundefined. - 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 === 0dequeues 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 pairsistrueifchis 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 givesundefined, 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 stale10as the one-variable version. Math.min()with no numbers isInfinity. That's whyMinStackstarts fromInfinity: it's the "no minimum yet" value.values.at(-1)andvalues[values.length - 1]are both2;values[-1]isundefined.
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()returnsfalseand 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 writei - j(the distance) instead oftemps[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
- 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).
- How do you make a stack in JavaScript? A plain array with
push,popandat(-1)for peek. All O(1). - Why is
shift()slow on big arrays? It removes index 0, so every other item moves one place forward: O(n) per call. - 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
minsis the answer. - Why doesn't one
minvariable work? After popping the minimum, it still holds the old value, and the previous minimum is lost. - 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.
- 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.
- 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).
- 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).
- The
whileinside theforlooks like O(n²). Why is it O(n)? Each index is pushed once and popped at most once, so thewhileruns 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,pushandpopare O(1), butshift()is O(n): we measured 200,000 shifts in seconds and 200,000 pops in under a millisecond. - Min stack: one
minvariable 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.