The JavaScript toolkit for DSA

Why a language chapter in a DSA course

Most interview bugs in JavaScript are not algorithm bugs. The idea on the whiteboard is right, and the code still fails, because a queue was built on shift() and quietly became O(n²), because sort() with no comparator puts 10 before 2, because a modular product lost its low digits, or because a recursion that is fine on paper throws RangeError at depth ten thousand. On top of that, three structures that other languages ship in their standard library are missing here: a heap, a deque and an ordered set. In an interview you build them yourself, so you need to be able to write each one from memory.

This chapter is the reference the later chapters send you back to. Stacks and queues, linked lists, hashing, heaps, graphs and dynamic programming all lean on something in it. Read it once straight through, then come back to a single section when a later chapter points at it.

How the claims in this chapter were checked. Every line that ends in a comment of the form // → value shows what Node 24.14.1 printed for that expression; each one was run, not recalled. Two kinds of statement are kept apart. Some are guaranteed by the language specification: a stable sort, insertion order in Map, how equality works for keys, the 32-bit window of the bit operators. Others are about speed, which the specification does not promise and an engine may improve. For those, the chapter says how the cost is described by the algorithm, shows a measurement, and tells you what to say in an interview. Timings come from one laptop: the milliseconds will differ on yours, but the ratios between rows are what to look at.

Array operations and what they really cost

An array is a numbered row of slots. Reading or writing slot i does not depend on how long the row is, so it is O(1). Adding or removing at the end touches one slot, so push and pop are O(1) (amortized, as the complexity chapter showed). Anything that changes the position of elements, or builds a new row, has to touch every slot involved, and that is where the cost hides.

A row of this table is a statement about what the method has to do, not a promise about the engine. Engines are free to be faster than the description, and the measurements below show where being slower than you hoped still bites.

The queue built on shift() is quadratic

Dequeue from the front of an array with shift() and the language moves every remaining element down one place, which is n moves for an array of length n. Draining n items that way costs about n²/2 moves in total. Here is that loop, timed for growing n, next to a loop that only moves a read index:

const a = Array.from({ length: 100000 }, (_, i) => i);
const start = performance.now();
while (a.length > 0) a.shift();
const ms = performance.now() - start;

Each doubling of n multiplies the time by about four or more. That is the signature of a quadratic loop, and it is why the first row is the dangerous one: at 10,000 elements the same code finishes in 2 ms and passes every small test. The fix is in the next section.

Copies in a recursion do the same damage

Backtracking code often writes recurse([...path, x]) because it avoids undoing the change. That copy is O(length of path) at every call. Building a list of n items by repeated copying is n²/2 element copies:

The habit that avoids it: change the one shared array with push, recurse, then undo with pop. Copy only at the moment you record an answer (results.push([...path])), because that copy is the size of the output and cannot be avoided.

Methods that change the array and methods that return a new one

sort, reverse, splice, fill and push/pop/shift change the array they are called on. slice, concat, map, filter and the spread syntax return a new one. sort in particular also returns the same array, which surprises people who write const sorted = a.sort() and then find that a changed.

const original = [3, 1, 2];
const sorted = original.sort();
sorted === original; // → true
original; // → [ 1, 2, 3 ]
[...[3, 1, 2]].sort(); // → [ 1, 2, 3 ]
[3, 1, 2].toSorted(); // → [ 1, 2, 3 ]
[3, 1, 2].toReversed(); // → [ 2, 1, 3 ]
[3, 1, 2].with(0, 9); // → [ 9, 1, 2 ]

toSorted, toReversed, toSpliced and with exist in Node 24, as the output shows. They are newer than the older methods, so check what the interview editor runs before leaning on them, and know the portable form: copy first with [...a] or a.slice(), then change the copy.

The queue without shift: a head index

A queue needs two things: add at the back, take from the front. Adding at the back is push. For the front, the array does not have to delete anything. It only has to remember where the front is. Keep a number head that points at the next item to take; "dequeue" is reading queue[head] and adding one to head. Nothing moves, so each step is O(1).

Breadth-first search is the standard use. Each node enters the queue once, so the array never grows past the number of nodes, and the consumed prefix is harmless garbage you do not need to free.

function bfsDistances(n, edges, start) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }

  const dist = new Array(n).fill(-1);
  const queue = [start];
  dist[start] = 0;

  for (let head = 0; head < queue.length; head++) {
    // queue.length is re-read each time, so pushes inside the loop are seen
    const node = queue[head];
    for (const next of adj[node]) {
      if (dist[next] === -1) {
        dist[next] = dist[node] + 1;
        queue.push(next);
      }
    }
  }
  return dist;
}

bfsDistances(6, [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]], 0); // → [ 0, 1, 1, 2, 3, -1 ]

Dry run: the graph 0-1, 0-2, 1-3, 2-3, 3-4, start 0, node 5 isolated

The loop ends when head reaches 5, the queue's length. Node 5 was never reached, so its distance stays -1. Setting dist[next] at the moment of pushing, not when taking, is what stops a node from entering the queue twice. The graph chapters build on exactly this loop.

If you want the push and shift vocabulary without the O(n) cost, wrap the head index in a small class. One refinement keeps memory from growing forever on a long-running queue: when the consumed prefix is at least half the array, cut it off with slice.

class Queue {
  #items = [];
  #head = 0;

  get size() {
    return this.#items.length - this.#head;
  }

  push(x) {
    this.#items.push(x);
  }

  peek() {
    return this.#items[this.#head];
  }

  shift() {
    if (this.size === 0) return undefined;
    const x = this.#items[this.#head];
    this.#items[this.#head] = undefined;
    this.#head++;
    if (this.#head * 2 >= this.#items.length) {
      this.#items = this.#items.slice(this.#head);
      this.#head = 0;
    }
    return x;
  }
}

const q = new Queue();
q.push("a");
q.push("b");
q.shift(); // → 'a'
q.size; // → 1
q.shift(); // → 'b'
q.shift(); // → undefined

Why the slice does not break the O(1) bound: it runs only when the consumed prefix is at least as long as what remains, so it copies at most as many elements as there have been shifts since the last cut. Each shift pays for one element of a later copy, which is the same amortized argument as the dynamic array. The class was run against a plain-array model on thousands of random push, shift and peek sequences. The two-stack queue in the stacks and queues chapter is the alternative when you cannot index into an array.

Copies, references and holes

Arrays are objects, and a variable holds a reference to one. Two variables can name the same array, and a "copy" is often a second reference or a copy of only the outer layer. Four mistakes come from this, and they all pass a one-element test.

new Array(3); // → [ <3 empty items> ]
new Array(3).map(() => 1); // → [ <3 empty items> ]
new Array(3).fill(0); // → [ 0, 0, 0 ]
Array.from({ length: 3 }, (_, i) => i * 2); // → [ 0, 2, 4 ]

new Array(3) makes three holes: slots that have never been assigned. map, forEach and filter skip holes, which is why the second line returns holes again. fill and Array.from make real elements.

const shared = new Array(2).fill([]);
shared[0].push(1);
shared; // → [ [ 1 ], [ 1 ] ]

const separate = Array.from({ length: 2 }, () => []);
separate[0].push(1);
separate; // → [ [ 1 ], [] ]

const grid = [[1, 2], [3, 4]];
const outerCopy = [...grid];
outerCopy[0][0] = 99;
grid; // → [ [ 99, 2 ], [ 3, 4 ] ]

const base = [[1, 2], [3, 4]];
const safe = base.map((row) => [...row]);
safe[0][0] = 99;
base; // → [ [ 1, 2 ], [ 3, 4 ] ]

Spread, slice and concat copy one level. For a 2D array, copy each row. structuredClone(grid) copies every level and also works, at a higher cost than mapping the rows.

A few smaller behaviours that decide whether a loop is correct:

[1, 2, 3][-1]; // → undefined
[1, 2, 3].at(-1); // → 3
[1, 2] === [1, 2]; // → false
const sparse = [1];
sparse[5] = 1;
sparse; // → [ 1, <4 empty items>, 1 ]
Math.max(...new Array(100000).fill(1)); // → 1
Math.max(...new Array(1000000).fill(1)); // → RangeError: Maximum call stack size exceeded
new Array(-1); // → RangeError: Invalid array length

• Negative indexes are not an error: a[-1] is undefined. Use at(-1) for the last element.
• Equality of arrays is identity. Two arrays with the same contents are not ===. Compare element by element, or compare a joined string.
• Writing past the end leaves holes, and the length jumps. A loop that does a[i] = x with a skipped i produces holes that map then ignores.
• Spreading a long array into a call turns every element into an argument. 100,000 worked here and 1,000,000 threw, so use a loop for a maximum over a large input. The same limit applies to push(...big).
• a.length = 0 empties the array that everyone holding a reference sees. Assigning a = [] only changes your variable.

Sorting: the default comparator, comparators and stability

sort() with no argument converts every element to a string and compares the strings by their UTF-16 code units. That is correct for words of one case and wrong for numbers.

[10, 2, 1].sort(); // → [ 1, 10, 2 ]
[-1, -2, 3, 10, 9].sort(); // → [ -1, -2, 10, 3, 9 ]
[[10, 1], [9, 2]].sort(); // → [ [ 10, 1 ], [ 9, 2 ] ]
[10, 2, 1].sort((a, b) => a - b); // → [ 1, 2, 10 ]
[10, 2, 1].sort((a, b) => b - a); // → [ 10, 2, 1 ]

The comparator receives two elements and answers with a number. Negative means the first goes before the second, positive means the second goes first, and zero means they are equal for this sort. For two finite numbers a - b has exactly the right sign, so it is a correct ascending comparator and b - a a correct descending one. It is not correct for anything else:

[3, 1, 2].sort((a, b) => a > b); // → [ 3, 1, 2 ]
['b', 'a', 'C'].sort((a, b) => a - b); // → [ 'b', 'a', 'C' ]
[3n, 1n, 2n].sort((a, b) => a - b); // → TypeError: Cannot convert a BigInt value to a number
[3n, 1n, 2n, 10n].sort((a, b) => (a < b ? -1 : a > b ? 1 : 0)); // → [ 1n, 2n, 3n, 10n ]
[3, undefined, 1, 2].sort((a, b) => b - a); // → [ 3, 2, 1, undefined ]

• A comparator that returns a boolean never says "negative", because false becomes 0 and true becomes 1. The array comes back unchanged. Return a number.
• Subtracting strings gives NaN, which counts as "equal", so nothing moves. Compare strings with a < b ? -1 : a > b ? 1 : 0.
• BigInts cannot be subtracted into a number for the comparator, so use the three-way comparison from the line after it.
• undefined always sorts to the end and the comparator is never called for it.
• The default order of arrays of arrays compares their string form, so [10, 1] comes before [9, 2]. For intervals use (a, b) => a[0] - b[0] || a[1] - b[1].

Two orders for strings

['b', 'B', 'a', 'A', 'é'].sort(); // → [ 'A', 'B', 'a', 'b', 'é' ]
['b', 'B', 'a', 'A', 'é'].sort((x, y) => x.localeCompare(y)); // → [ 'a', 'A', 'b', 'B', 'é' ]

The default and the three-way comparison use code unit order, where every capital letter comes before every lowercase one. localeCompare follows the locale's dictionary order. Problems that ask for the "lexicographically smallest" string mean code unit order, which is what < gives you.

Stability

Since ES2019 the language guarantees that sort is stable: elements that compare as equal keep the order they had in the input. That is what makes multi-key sorting work. Here the records are sorted by score only, and the names within one score stay in input order:

const records = [
  { name: "a", score: 2 },
  { name: "b", score: 1 },
  { name: "c", score: 2 },
  { name: "d", score: 1 },
  { name: "e", score: 2 },
];
records.sort((x, y) => x.score - y.score).map((r) => r.name).join(""); // → 'bdace'
[{ n: "b", s: 2 }, { n: "a", s: 2 }, { n: "c", s: 3 }]
  .sort((x, y) => y.s - x.s || x.n.localeCompare(y.n))
  .map((r) => r.n); // → [ 'c', 'a', 'b' ]

The second sort shows the single-comparator way to use two keys: first || second, because a difference of zero is falsy and falls through to the next key. Cost: O(n log n) comparisons, and each comparison costs what your function does. Sorting n strings of length L is O(L · n log n), not O(n log n).

Strings: immutable, UTF-16, and building one

A string cannot be changed in place. Assigning to an index does not edit it. In sloppy-mode code the assignment is ignored without a word, and in strict code (every module, and the practice runner on this site) it throws:

"use strict";
let s = "abc";
s[0] = "x"; // → TypeError: Cannot assign to read only property '0' of string 'abc'

To "change" a character, make an array of characters, change the array and join it back, or build the result from slices. Both are O(n), so an edit-one-character loop over a string is O(n²).

Length counts UTF-16 code units

"a😀b".length; // → 4
[..."a😀b"].length; // → 3
"a😀b".split("").length; // → 4
"😀".codePointAt(0); // → 128512
"😀".charCodeAt(0); // → 55357
"abc".charCodeAt(5); // → NaN
"abc"[5]; // → undefined

A character outside the basic range takes two code units. length, indexing, charCodeAt and split("") count code units and can cut such a character in half. Spread, Array.from and for...of walk code points. Interview strings are almost always lowercase letters, where the two agree. When a problem mentions emoji or "any Unicode text", switch to the code point forms.

Characters as numbers

"a".charCodeAt(0); // → 97
"c".charCodeAt(0) - "a".charCodeAt(0); // → 2
String.fromCharCode(97 + 2); // → 'c'
"10" < "9"; // → true
"Zebra" < "apple"; // → true
"5" + 1; // → '51'
"5" - 1; // → 4

The first three lines are the letter-to-index idiom behind every 26-slot counting array. Comparing strings with < compares character by character, so a string of digits is not compared as a number. The last two lines are the other way + bites: with a string on either side it concatenates, and every other arithmetic operator converts to a number.

Parsing

parseInt("08"); // → 8
parseInt("12px"); // → 12
Number("12px"); // → NaN
Number(""); // → 0
["1", "2", "3"].map(parseInt); // → [ 1, NaN, NaN ]
["1", "2", "3"].map(Number); // → [ 1, 2, 3 ]

map passes three arguments, and parseInt reads the second as the radix, so the second element is parsed in base 1 and the third in base 2. Pass Number, or write (x) => parseInt(x, 10). An empty string becomes 0, not NaN, so check for it yourself when it matters.

Building a string

In the model, s += piece creates a new string holding a copy of everything so far, which would make a loop of n appends O(n²), the same shape as the array copies above. Node 24 does better in practice: a loop of 1,000,000 single-character appends took 52 ms with += and 14 ms with an array of pieces and one join, with no quadratic growth visible. So in JavaScript, += in a loop is not the disaster it is elsewhere. The habit is still cheap and portable: push the pieces into an array and call join("") once. For interview analysis, say that the join is O(total length).

"hello".slice(-3); // → 'llo'
"hello".substring(-3); // → 'hello'
"hello".slice(1, -1); // → 'ell'
"a-b-c".replace("-", "+"); // → 'a+b-c'
"a-b-c".replaceAll("-", "+"); // → 'a+b+c'
[..."hello"].reverse().join(""); // → 'olleh'

slice accepts negative positions counted from the end. substring treats negatives as 0 and swaps its arguments if they are the wrong way round, so prefer slice. Treat slice as O(length of the piece), and indexOf or includes for a substring as at least O(n), with O(n · m) as the safe upper budget.

Map and Set: equality, order and composite keys

Map and Set decide whether two keys are "the same" with an operation the specification calls SameValueZero. It is ===, except that NaN equals itself and +0 equals -0. Anything that is an object, including every array, is the same key only as itself.

new Map([[NaN, "a"]]).get(NaN); // → 'a'
[...new Map([[-0, "a"]]).keys()]; // → [ 0 ]
new Set([1, "1"]).size; // → 2
new Set([1, 1n]).size; // → 2
new Set([[1, 2], [1, 2]]).size; // → 2
new Map([[[1, 2], "x"]]).get([1, 2]); // → undefined
new Set("hello").size; // → 4

Composite keys: pairs, coordinates, states

Because an array key is compared by identity, a visited set of [row, col] pairs does not work. Turn the pair into one primitive. There are three honest ways, with different limits:

const a = [1, 23];
const b = [12, 3];
`${a[0]}${a[1]}` === `${b[0]}${b[1]}`; // → true
`${a[0]},${a[1]}` === `${b[0]},${b[1]}`; // → false

Order, and what it gives you for free

Iteration order is insertion order, guaranteed. Setting a key that already exists keeps its position. Deleting a key and setting it again moves it to the end. That small rule is the whole of an LRU cache: on every access, delete and re-set the key, and the oldest key is always the first one.

const m = new Map([["a", 1], ["b", 2], ["c", 3]]);
m.set("a", 9);
[...m.keys()]; // → [ 'a', 'b', 'c' ]
m.delete("a");
m.set("a", 9);
[...m.keys()]; // → [ 'b', 'c', 'a' ]
m.keys().next().value; // → 'b'

class LRUCache {
  #map = new Map();
  #capacity;

  constructor(capacity) {
    this.#capacity = capacity;
  }

  get(key) {
    if (!this.#map.has(key)) return -1;
    const value = this.#map.get(key);
    this.#map.delete(key);
    this.#map.set(key, value);
    return value;
  }

  put(key, value) {
    this.#map.delete(key);
    this.#map.set(key, value);
    if (this.#map.size > this.#capacity) {
      this.#map.delete(this.#map.keys().next().value);
    }
  }
}

const cache = new LRUCache(2);
cache.put(1, 10);
cache.put(2, 20);
cache.get(1); // → 10
cache.put(3, 30);
cache.get(2); // → -1
cache.get(3); // → 30

Every operation is a handful of O(1) map operations. The class was checked against a list-based model on random sequences. Note the has call in get: a stored value of 0 or undefined must not be confused with a missing key.

Plain objects as maps: the traps

An object works as a counter until a key collides with something every object already has, or with how objects order their keys.

const counts = {};
const word = "constructor";
counts[word] = (counts[word] || 0) + 1;
counts[word]; // → 'function Object() { [native code] }1'
Object.keys({ b: 1, 2: 1, a: 1, 1: 1, "-1": 1 }); // → [ '1', '2', 'b', 'a', '-1' ]
const tally = new Map();
tally.set(word, (tally.get(word) ?? 0) + 1);
tally.get(word); // → 1

The word "constructor" already exists on every object, so counts[word] || 0 finds a function and glues "1" to it. Object keys are always strings (the number 1 and the string "1" are one key), integer looking keys come first in ascending order, and then the rest in insertion order. A Map has none of these problems. Use get(k) ?? 0 rather than get(k) || 0 when the stored value can legitimately be 0 and you want to keep it, and use has to test presence: if (map.get(k)) is false for a stored 0.

Changing a collection while looping over it

const s = new Set([1]);
const seen = [];
for (const x of s) {
  seen.push(x);
  if (x < 4) s.add(x + 1);
}
seen; // → [ 1, 2, 3, 4 ]
const mm = new Map([[1, 1], [2, 2], [3, 3]]);
const visited = [];
for (const [k] of mm) {
  visited.push(k);
  mm.delete(k + 1);
}
visited; // → [ 1, 3 ]

Items added during the loop are visited, and items deleted before the loop reaches them are skipped. That is well defined, and it is also an easy way to write a loop that never ends if you add a new item on every step. When in doubt, loop over a copy: for (const x of [...s]).

Cost, and when to reach for a set

has, get, set and delete are O(1) on average, and size is O(1). The specification asks only that access be sublinear on average, so O(1) average is the working assumption, as in the hashing chapter. The array methods on the same job: testing "have I seen n numbers" with includes inside a loop over n numbers, against a Set:

A fourfold input made the array version thirteen to sixteen times slower, which is the quadratic shape again.

[...new Map([["a", 1], ["b", 3], ["c", 2]])].sort((x, y) => y[1] - x[1]); // → [ [ 'b', 3 ], [ 'c', 2 ], [ 'a', 1 ] ]
Object.groupBy([1, 2, 3, 4], (x) => (x % 2 ? "odd" : "even")); // → [Object: null prototype] { odd: [ 1, 3 ], even: [ 2, 4 ] }
new Set([1, 2]).union(new Set([2, 3])); // → Set(3) { 1, 2, 3 }
new Set([...new Set([1, 2]), ...new Set([2, 3])]); // → Set(3) { 1, 2, 3 }

Sorting a map by value means spreading it into an array of pairs first, since a Map itself has no sort. groupBy and the Set methods union, intersection and difference exist in Node 24, but they are recent, so the spread form is the safe one in an unfamiliar environment.

Numbers: doubles, safe integers and division

Every JavaScript number is a 64-bit floating-point value. Integers are exact only while they fit in the 53 bits the format gives to digits. Past that, whole numbers start to be skipped:

Number.MAX_SAFE_INTEGER; // → 9007199254740991
2 ** 53 === 2 ** 53 + 1; // → true
Number.MAX_SAFE_INTEGER + 2; // → 9007199254740992
Number.isSafeInteger(2 ** 53); // → false
0.1 + 0.2; // → 0.30000000000000004
0.1 + 0.2 === 0.3; // → false

The consequences for interview code are concrete. Sums and products of large inputs can leave the safe range without any warning: the result is a number, just a wrong one. Factorials are a clean example:

function lastSafeFactorial() {
  let f = 1;
  let n = 1;
  while (Number.isSafeInteger(f * (n + 1))) {
    n++;
    f *= n;
  }
  return n;
}
lastSafeFactorial(); // → 18

19! is already past the safe range. A problem that asks for "the number of ways" modulo 10⁹ + 7 is built so the answer stays small; the danger is the intermediate product, covered after the division rules. When a problem involves fractions, avoid floating point: compare a / b with c / d as a * d against c * b, and keep everything an integer. If floats are unavoidable, compare with a tolerance: Math.abs(x - y) < 1e-9.

Division, remainder and the minus-zero

-7 / 2; // → -3.5
Math.floor(-7 / 2); // → -4
Math.trunc(-7 / 2); // → -3
-7 % 2; // → -1
((-7 % 5) + 5) % 5; // → 3
7 % -5; // → 2
Math.round(2.5); // → 3
Math.round(-2.5); // → -2

/ never rounds: integer division is something you write. Use Math.floor to round toward negative infinity and Math.trunc to cut toward zero, and choose on purpose, because they differ for negative numbers. % gives the remainder with the sign of the left operand, so -7 % 5 is -2 and a "wrap an index around" formula needs the fix on the fifth line, ((x % m) + m) % m, to land in 0..m-1. Math.round rounds halves toward positive infinity.

Math.trunc(-0.5); // → -0
-4 % 2; // → -0
-0 === 0; // → true
Object.is(-0, 0); // → false
String(-0); // → '0'
[-0].includes(0); // → true
Math.max(); // → -Infinity
Math.min(); // → Infinity
Math.max(NaN, 1); // → NaN
NaN === NaN; // → false
Number.isNaN("abc"); // → false
isNaN("abc"); // → true

Negative zero is a real value that behaves like 0 in arithmetic and in ===, but a console prints it as -0 and Object.is can tell it apart. It appears from Math.trunc and Math.round of a small negative number and from a negative number's remainder. If a result must print as 0, add 0 to it: -0 + 0 is 0. Infinity is the right starting value for a running minimum, and -Infinity for a running maximum. A NaN poisons every comparison, because all of them are false, so if (x < best) silently never fires for a NaN x. Use Number.isNaN, which does not convert its argument first the way the global isNaN does.

The middle of a range

const lo = 2 ** 31;
const hi = 2 ** 31 + 10;
Math.floor((lo + hi) / 2); // → 2147483653
lo + Math.floor((hi - lo) / 2); // → 2147483653
(lo + hi) >> 1; // → 5

In JavaScript lo + hi cannot overflow until the sum passes 2⁵³, so the textbook worry about (lo + hi) / 2 belongs to languages with 32-bit integers. The trap is the opposite one: the shortcut (lo + hi) >> 1 forces the sum into 32 bits first, and it gives 5 here. Write Math.floor((lo + hi) / 2), or lo + ((hi - lo) >> 1) while the range is below 2³¹.

BigInt: exact integers, with rules

A BigInt is a separate type that holds a whole number of any size exactly. Write a literal with an n suffix or convert with BigInt(x). It exists for the places where the 2⁵³ limit above would change an answer.

2n ** 100n; // → 1267650600228229401496703205376n
BigInt(Number.MAX_SAFE_INTEGER) + 2n; // → 9007199254740993n
-7n / 2n; // → -3n
-7n % 2n; // → -1n
1n + 1; // → TypeError: Cannot mix BigInt and other types, use explicit conversions
BigInt(1.5); // → RangeError: The number 1.5 cannot be converted to a BigInt because it is not an integer
1n == 1; // → true
1n === 1; // → false
10n > 9; // → true
Number(2n ** 64n); // → 18446744073709552000
JSON.stringify({ a: 1n }); // → TypeError: Do not know how to serialize a BigInt
Math.max(1n, 2n); // → TypeError: Cannot convert a BigInt value to a number

• No mixing. Arithmetic between a BigInt and a number throws. Convert one side explicitly.
• Division truncates toward zero and drops the remainder, like Math.trunc, and % takes the sign of the left operand.
• Comparison works across types (10n > 9), but === does not (1n === 1 is false), and a Map treats 1n and 1 as different keys.
• Converting back with Number(big) rounds once the value is beyond the safe range.
• No Math functions and no JSON. Print with String(big) or big.toString().

The multiplication that loses digits

Counting problems ask for an answer modulo 10⁹ + 7 and multiply two numbers that are each below that. The product can be about 10¹⁸, far past 2⁵³, so the remainder of the rounded product is wrong:

const MOD = 1000000007;
const x = 999999999;
const y = 999999998;
(x * y) % MOD; // → 70
Number((BigInt(x) * BigInt(y)) % BigInt(MOD)); // → 72
Number.isSafeInteger(x * y); // → false
function mulMod(a, b, m) {
  return Number((BigInt(a) * BigInt(b)) % BigInt(m));
}
mulMod(x, y, MOD); // → 72

The first answer is a plausible-looking 70 and the true one is 72, with no error raised. Do the multiplication in BigInt and convert the already reduced result back, which is safe because it is below the modulus. Additions need no such care: the sum of two values below 10⁹ + 7 stays safe. Reach for BigInt when exactness is the point (huge factorials, exact products, 64-bit wrap-around with BigInt.asUintN(64, x)), and keep ordinary counters as numbers, since mixing the types costs conversions.

function factorialString(n) {
  let f = 1n;
  for (let i = 2n; i <= BigInt(n); i++) f *= i;
  return f.toString();
}
factorialString(25); // → '15511210043330985984000000'
BigInt.asUintN(64, -1n); // → 18446744073709551615n

Bit operations and the 32-bit window

The bit operators &, |, ^, ~, <<, >> and >>> do not work on the 64-bit double you wrote. They first convert each operand to a signed 32-bit integer, work on that, and convert back. Everything surprising about them follows from that one step.

1 << 30; // → 1073741824
1 << 31; // → -2147483648
1 << 32; // → 1
2 ** 31 | 0; // → -2147483648
2 ** 32 | 0; // → 0
(2 ** 40 + 3) | 0; // → 3
1e10 ^ 0; // → 1410065408
-1 >> 0; // → -1
-1 >>> 0; // → 4294967295
-8 >> 1; // → -4
-8 >>> 1; // → 2147483644
3.7 | 0; // → 3
-3.7 | 0; // → -3

• Bit 31 is the sign bit. 1 << 31 is negative, and any number from 2³¹ up reads as a negative one.
• The shift count is taken modulo 32, so 1 << 32 is 1 << 0.
• A value of 2³² or more loses its upper bits: (2 ** 40 + 3) | 0 is 3. Bit tricks are only for values that fit in 32 bits. For wider ones use BigInt, which has its own &, |, <<, or plain arithmetic.
• >> copies the sign bit in from the left; >>> fills with zeros. x >>> 0 is the idiom that reads the 32 bits as an unsigned number.
• x | 0 and ~~x cut off the fractional part toward zero, like Math.trunc, but only inside the 32-bit window.

Parity, masks and printing bits

-3 % 2; // → -1
-3 % 2 === 1; // → false
(-3 & 1) === 1; // → true
(1 << 30) - 1; // → 1073741823
(1 << 31) - 1; // → -2147483649
2 ** 31 - 1; // → 2147483647
(-5).toString(2); // → '-101'
(-5 >>> 0).toString(2); // → '11111111111111111111111111111011'
(5).toString(2).padStart(8, "0"); // → '00000101'
parseInt("101", 2); // → 5
Math.clz32(1); // → 31
Math.imul(65537, 65537); // → 131073

An "is it odd" test written as n % 2 === 1 fails for every negative odd number, because their remainder is -1. Test (n & 1) === 1, or n % 2 !== 0. A mask of the low k bits, (1 << k) - 1, is right up to k = 30 and wrong from 31, as the last two mask lines show; use 2 ** k - 1 while you stay out of the bit operators. A bitmask over items, where bit i means "item i is chosen", is therefore safe for up to 30 items with 1 << i. (-5).toString(2) prints a minus sign, not the stored bits; to see two's complement, shift by zero first. Math.imul multiplies two 32-bit integers and keeps the low 32 bits exactly, which an ordinary * cannot do once the product passes 2⁵³. The bit-manipulation chapter builds the tricks on this footing.

Typed arrays: fixed-size, zero-filled numbers

A typed array such as Int32Array, Uint8Array or Float64Array is a fixed-length array of one numeric type, and every slot starts at 0. You pick one when you know the size up front and the values are numbers: a sieve, a counting array, a DP table, a visited flag, a queue of node numbers.

new Int32Array(1000000).byteLength; // → 4000000
new Uint8Array(1000000).byteLength; // → 1000000
new Uint8Array([256, -1, 257, 3.9]); // → Uint8Array(4) [ 0, 255, 1, 3 ]
new Uint8ClampedArray([256, -1, 300]); // → Uint8ClampedArray(3) [ 255, 0, 255 ]
new Int32Array([2 ** 31, 2 ** 32 + 5]); // → Int32Array(2) [ -2147483648, 5 ]
new Int32Array([Infinity, 1.9]); // → Int32Array(2) [ 0, 1 ]
new Float64Array(2).fill(Infinity); // → Float64Array(2) [ Infinity, Infinity ]
new Int32Array([10, 2, 1]).sort(); // → Int32Array(3) [ 1, 2, 10 ]
typeof new Int32Array(2).push; // → 'undefined'

• Values wrap or clamp silently. A Uint8Array stores 256 as 0 and -1 as 255. The clamped variant pins to 0..255. An Int32Array wraps at 2³¹. Pick the width for the largest value you will store.
• An integer array cannot hold Infinity. It stores 0. For a DP table that uses Infinity as "unreachable", use a Float64Array, or a large integer sentinel that fits.
• The length is fixed: no push, pop or shift, and writing past the end is ignored.
• sort() is numeric by default, unlike a normal array.
• subarray is a view that shares memory with the original, slice is a copy. Writing through the view changes the original.

function countPrimes(n) {
  const composite = new Uint8Array(n + 1);
  let count = 0;
  for (let i = 2; i <= n; i++) {
    if (composite[i] === 1) continue;
    count++;
    for (let j = i * i; j <= n; j += i) composite[j] = 1;
  }
  return count;
}
countPrimes(100); // → 25
countPrimes(1000000); // → 78498

The array of flags starts zeroed, so there is no fill loop, and a million flags take a million bytes. The same fixed size is what makes a typed array a good queue for BFS, because every node enters once: const queue = new Int32Array(n) with two indexes, a head and a tail, replaces the growing array. A grid can also be stored flat in one typed array with the index r * cols + c.

function bfsTyped(n, edges, start) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const dist = new Int32Array(n).fill(-1);
  const queue = new Int32Array(n);
  let head = 0;
  let tail = 0;
  queue[tail++] = start;
  dist[start] = 0;
  while (head < tail) {
    const node = queue[head++];
    for (const next of adj[node]) {
      if (dist[next] === -1) {
        dist[next] = dist[node] + 1;
        queue[tail++] = next;
      }
    }
  }
  return Array.from(dist);
}
bfsTyped(6, [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]], 0); // → [ 0, 1, 1, 2, 3, -1 ]

Recursion depth: the stack runs out

Every call that has not returned yet takes space on the call stack, and the stack has a fixed size. When a recursion nests too deeply, JavaScript throws RangeError: Maximum call stack size exceeded. The limit is not a number in the language. It depends on how big each frame is, and on the runtime. In Node 24 on the machine used here:

So plan on a few thousand levels, and treat anything near ten thousand as already unsafe. A linked list of 100,000 nodes, a depth-first search of a path-shaped graph with 100,000 nodes, or a memoized recursion over n = 100,000 all fail, even though each is O(n) on paper. The language specification describes proper tail calls, but Node does not implement them, so moving the recursive call to the last position buys nothing:

function sumTo(n, acc = 0) {
  return n === 0 ? acc : sumTo(n - 1, acc + n);
}
sumTo(1000); // → 500500
sumTo(100000); // → RangeError: Maximum call stack size exceeded

The fix is to replace the call stack with a stack of your own, which lives in the heap and can hold millions of entries. For depth-first search that is an array used as a stack:

function countReachable(n, edges, start) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const seen = new Uint8Array(n);
  const stack = [start];
  seen[start] = 1;
  let count = 0;
  while (stack.length > 0) {
    const node = stack.pop();
    count++;
    for (const next of adj[node]) {
      if (seen[next] === 0) {
        seen[next] = 1;
        stack.push(next);
      }
    }
  }
  return count;
}

function countReachableRecursive(adj, node, seen) {
  seen[node] = 1;
  let count = 1;
  for (const next of adj[node]) {
    if (seen[next] === 0) count += countReachableRecursive(adj, next, seen);
  }
  return count;
}

Run both on a path graph 0-1-2-...-199,999: the loop version returns 200,000, and the recursive one throws RangeError. The loop marks a node as seen when it is pushed, so each node enters the stack once, and the visiting order differs from the recursive one. Where the order matters (for example a topological order from a depth-first search) you keep an index per stack entry instead. Keep ordinary recursion for trees and graphs whose depth is known to be small, such as a balanced tree of height 20, and say the limit out loud when the input could be a long chain.

No built-in heap: a minimal one with a comparator

A priority queue hands back the smallest (or largest) item you have stored so far, and accepts new items in between. It is the structure behind "k largest", "merge k sorted lists", Dijkstra and scheduling problems. The standard way to build one is a binary heap: a complete binary tree kept in an array, where every parent comes out before its children. JavaScript has no heap in the language. In an interview you write it, so here is one you can type from memory, and the heaps chapter explains why it is correct and puts it to work.

The array stores the tree level by level: the children of the item at index i are at 2i + 1 and 2i + 2, and its parent at (i - 1) >> 1. The one design choice is how to say which item comes out first. Do it the way sort does: the constructor takes a comparator, and an item a sits closer to the top than b when compare(a, b) < 0. Then the same class is a min-heap, a max-heap, or a heap of pairs ordered by their first field.

class Heap {
  #items;
  #compare;

  constructor(compare = (a, b) => a - b, items = []) {
    this.#compare = compare;
    this.#items = [...items];
    for (let i = (this.#items.length >> 1) - 1; i >= 0; i--) this.#siftDown(i);
  }

  get size() {
    return this.#items.length;
  }

  peek() {
    return this.#items[0];
  }

  push(item) {
    this.#items.push(item);
    this.#siftUp(this.#items.length - 1);
  }

  pop() {
    const items = this.#items;
    if (items.length === 0) return undefined;
    const top = items[0];
    const last = items.pop();
    if (items.length > 0) {
      items[0] = last;
      this.#siftDown(0);
    }
    return top;
  }

  #siftUp(i) {
    const items = this.#items;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.#compare(items[i], items[parent]) >= 0) break;
      [items[i], items[parent]] = [items[parent], items[i]];
      i = parent;
    }
  }

  #siftDown(i) {
    const items = this.#items;
    const n = items.length;
    while (true) {
      let best = i;
      const left = 2 * i + 1;
      const right = left + 1;
      if (left < n && this.#compare(items[left], items[best]) < 0) best = left;
      if (right < n && this.#compare(items[right], items[best]) < 0) best = right;
      if (best === i) break;
      [items[i], items[best]] = [items[best], items[i]];
      i = best;
    }
  }
}

const minHeap = new Heap();
[5, 3, 8, 1].forEach((x) => minHeap.push(x));
minHeap.peek(); // → 1
minHeap.pop(); // → 1
minHeap.pop(); // → 3
minHeap.size; // → 2
new Heap((a, b) => b - a, [4, 9, 2]).pop(); // → 9
const byDistance = new Heap((a, b) => a[0] - b[0]);
byDistance.push([7, "far"]);
byDistance.push([2, "near"]);
byDistance.pop(); // → [ 2, 'near' ]
new Heap().pop(); // → undefined

Dry run: push 5, 3, 8, 1, then pop twice

The cost: push and pop are O(log n), because each moves along one path of the tree and a complete tree of n items is about log₂ n levels tall. peek and size are O(1). The constructor builds a heap from an array in O(n) by sifting down from the last parent to the root, which the heaps chapter proves. A top-k loop shows the typical use: keep a min-heap of the k largest so far and drop its minimum whenever it grows past k.

function kthLargest(nums, k) {
  const heap = new Heap();
  for (const x of nums) {
    heap.push(x);
    if (heap.size > k) heap.pop();
  }
  return heap.peek();
}
kthLargest([3, 2, 1, 5, 6, 4], 2); // → 5

No built-in deque: a ring buffer

A deque (double-ended queue) adds and removes at both ends in O(1). The head-index queue gives you one end; the other end of a plain array is O(n) with unshift. The structure behind "sliding window maximum", 0-1 breadth-first search and "palindrome check from both ends" is the ring buffer: a fixed row of slots in which the live items occupy a stretch that may wrap around the end.

Keep two numbers, head (the slot of the front item) and size. The item at logical position i lives in slot (head + i) % capacity. Pushing at the back writes to logical position size; pushing at the front moves head one slot backwards, wrapping around, and writes there. When the row is full, build one twice as long, copy the items in logical order and reset head to 0.

class Deque {
  #buf = new Array(4);
  #head = 0;
  #size = 0;

  get size() {
    return this.#size;
  }

  #slot(i) {
    return (this.#head + i) % this.#buf.length;
  }

  #grow() {
    const bigger = new Array(this.#buf.length * 2);
    for (let i = 0; i < this.#size; i++) bigger[i] = this.#buf[this.#slot(i)];
    this.#buf = bigger;
    this.#head = 0;
  }

  pushBack(x) {
    if (this.#size === this.#buf.length) this.#grow();
    this.#buf[this.#slot(this.#size)] = x;
    this.#size++;
  }

  pushFront(x) {
    if (this.#size === this.#buf.length) this.#grow();
    this.#head = (this.#head - 1 + this.#buf.length) % this.#buf.length;
    this.#buf[this.#head] = x;
    this.#size++;
  }

  popFront() {
    if (this.#size === 0) return undefined;
    const x = this.#buf[this.#head];
    this.#buf[this.#head] = undefined;
    this.#head = this.#slot(1);
    this.#size--;
    return x;
  }

  popBack() {
    if (this.#size === 0) return undefined;
    const slot = this.#slot(this.#size - 1);
    const x = this.#buf[slot];
    this.#buf[slot] = undefined;
    this.#size--;
    return x;
  }

  peekFront() {
    return this.#size === 0 ? undefined : this.#buf[this.#head];
  }

  peekBack() {
    return this.#size === 0 ? undefined : this.#buf[this.#slot(this.#size - 1)];
  }

  at(i) {
    return i >= 0 && i < this.#size ? this.#buf[this.#slot(i)] : undefined;
  }
}

Dry run: capacity 4, then a push that forces the buffer to grow

Every operation is O(1) except the doubling, which copies n items. Doubling happens after the size has doubled, so the copies over n pushes add up to fewer than 2n item moves: O(1) amortized, the same argument as push on a dynamic array. Two details that lose offers: the - 1 + length in pushFront keeps the index from going negative, since % of a negative number is negative; and the full test must happen before the write, or a push on a full buffer overwrites the front. Setting a popped slot back to undefined lets the removed item be collected.

What it is for: sliding window maximum

Keep the indexes of candidates in the deque so their values are decreasing from front to back. A new number removes every smaller candidate from the back, because those can never be a window maximum while the newer, larger number is in range. The front is expired when its index leaves the window.

function slidingMax(nums, k) {
  const out = [];
  const candidates = new Deque();
  for (let i = 0; i < nums.length; i++) {
    while (candidates.size > 0 && nums[candidates.peekBack()] <= nums[i]) {
      candidates.popBack();
    }
    candidates.pushBack(i);
    if (candidates.peekFront() <= i - k) candidates.popFront();
    if (i >= k - 1) out.push(nums[candidates.peekFront()]);
  }
  return out;
}
slidingMax([1, 3, 1, 2, 0, 5], 3); // → [ 3, 3, 2, 5 ]

Dry run: slidingMax([1, 3, 1, 2, 0, 5], 3)

Each index is pushed once and popped at most once, so the whole pass is O(n), where a rescan of every window is O(n · k). The monotonic chapter treats this pattern in full. The deque was checked against a plain-array model on random mixes of pushes, pops, peeks and reads, including runs that wrap and grow repeatedly.

No built-in ordered set: why, and what to use

An ordered set (a "TreeSet" or "TreeMap" in other languages) keeps its keys sorted and answers questions about the order: the largest key not above x (floor), the smallest key not below x (ceiling), how many keys are smaller (rank), all keys in a range. JavaScript does not have one. Set and Map are hash containers that iterate in insertion order, and they hold no comparison function, so they cannot tell you anything about order by key. An ordered container needs a comparison and a different layout, usually a balanced tree, and the standard library does not include one. So the interview question is: which of the simpler things already does the job?

The sorted array is the one to have ready, because it is short and its weakness is easy to state. A search is a binary search, and an insert has to open a gap, which is the same O(n) shift as unshift. Measured here, inserting n values into the middle of an array by splice took 4 ms for 10,000, 115 ms for 50,000 and 579 ms for 100,000 (inserting always at the front: 8, 358 and 1,253 ms). That is fine for tens of thousands of updates and a problem for hundreds of thousands.

class SortedList {
  #items = [];
  #compare;

  constructor(compare = (a, b) => a - b) {
    this.#compare = compare;
  }

  get size() {
    return this.#items.length;
  }

  #firstNotBefore(x) {
    let lo = 0;
    let hi = this.#items.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.#compare(this.#items[mid], x) < 0) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  #firstAfter(x) {
    let lo = 0;
    let hi = this.#items.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.#compare(this.#items[mid], x) <= 0) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  add(x) {
    this.#items.splice(this.#firstAfter(x), 0, x);
  }

  has(x) {
    const i = this.#firstNotBefore(x);
    return i < this.#items.length && this.#compare(this.#items[i], x) === 0;
  }

  remove(x) {
    const i = this.#firstNotBefore(x);
    if (i === this.#items.length || this.#compare(this.#items[i], x) !== 0) return false;
    this.#items.splice(i, 1);
    return true;
  }

  rank(x) {
    return this.#firstNotBefore(x);
  }

  at(i) {
    return this.#items.at(i);
  }

  floor(x) {
    return this.#items[this.#firstAfter(x) - 1];
  }

  lower(x) {
    return this.#items[this.#firstNotBefore(x) - 1];
  }

  ceiling(x) {
    return this.#items[this.#firstNotBefore(x)];
  }

  higher(x) {
    return this.#items[this.#firstAfter(x)];
  }
}

const set = new SortedList();
[5, 1, 9, 5].forEach((x) => set.add(x));
set.floor(6); // → 5
set.ceiling(6); // → 9
set.floor(0); // → undefined
set.higher(9); // → undefined
set.lower(5); // → 1
set.rank(5); // → 1
set.has(7); // → false
set.remove(5); // → true
set.size; // → 3
set.at(-1); // → 9

Two binary searches do all the work. firstNotBefore is the first position whose item is not smaller than x, the classic lower bound; firstAfter is the first position whose item is larger, the upper bound. floor and lower are the item just before one of those, and ceiling and higher the item at it. add inserts after equal items, so the list is a multiset, and remove takes out one copy. Both searches return the length when nothing qualifies, which is why reading one past the end gives undefined and not an error. The list was checked against brute-force scans on random operations.

Destructuring, swaps and loops: small idioms with sharp edges

The swap [a[i], a[j]] = [a[j], a[i]] builds a two-element array on the right, then assigns from it, so both values are read before either is written. It is the idiom for in-place algorithms, and it is correct when i === j.

const arr = [10, 20];
[arr[0], arr[1]] = [arr[1], arr[0]];
arr; // → [ 20, 10 ]
const [first, ...rest] = [1, 2, 3];
rest; // → [ 2, 3 ]
[...["a", "b"].entries()]; // → [ [ 0, 'a' ], [ 1, 'b' ] ]
const out = [];
for (const i in ["a", "b"]) out.push(i + 1);
out; // → [ '01', '11' ]
[1, 2, 3].reduce((a, b) => a + b, 0); // → 6
[].reduce((a, b) => a + b); // → TypeError: Reduce of empty array with no initial value
eval("let i = 0, j = 1\nconst a = [10, 20]\n[a[i], a[j]] = [a[j], a[i]]"); // → ReferenceError: Cannot access 'a' before initialization

• Rest copies. const [head, ...rest] = list and list.slice(1) both copy the tail. A recursion that peels one element off the front at every level copies n, n-1, n-2, ... elements, which is O(n²). Pass an index instead.
• for...in on an array gives string indexes, so i + 1 is string glue. Use for...of, or a plain index loop, or entries() when you need both.
• forEach cannot stop early; a return inside only skips to the next item, and break is a syntax error. Use for...of, or some and every to stop on a condition.
• reduce without an initial value throws on an empty array and uses the first element as the start otherwise. Pass the initial value.
• A line starting with [ or ( continues the previous line when that line has no semicolon. The last line above shows what happens to a swap written in a no-semicolon style. Either end every statement with a semicolon or put one before such a line.

Reading input and writing output fast

Interview platforms usually give you a function to complete, and none of this matters. Contest-style judges give you standard input and expect standard output, and two habits decide whether you finish in time: read everything at once, and print once.

const lines = require("fs").readFileSync(0, "utf8").split("\n");
const [n, k] = lines[0].split(" ").map(Number);
const values = lines[1].split(" ").map(Number);
console.log(values.reduce((a, b) => a + b, 0));

Fed the two lines 3 2 and 10 20 30 on standard input, this prints 60. Three details of the input text: the text ends with a newline, so split("\n") leaves an empty string as the last element; on a platform that ends lines with \r\n every line keeps a trailing "\r", which Number("5\r") forgives (it gives 5) but "5\r" === "5" does not (it gives false), so call trim() before comparing strings; and a list of numbers is split(" ").map(Number), not map(parseInt).

For output, one console.log per line is a separate write each time. Printing 300,000 lines one call at a time took about 1,000 ms to a file and 500 ms through a pipe, and building an array of the lines, then printing out.join("\n") once, took 25 ms for the same text. Collect the output in an array and print it once at the end.

Recognizing it in an unseen problem

This chapter does not describe a pattern, so recognition works the other way round: a symptom in your own solution points at the toolkit entry that fixes it.

Related chapters: hashing builds on the Map and Set rules, stacks and queues and linked lists use the head index and the deque, heaps explains the heap above, and bit manipulation builds on the 32-bit window.