JavaScript for DSA
The parts of JavaScript you actually use in interviews, with the traps to avoid. Every snippet runs: press Run, or Edit to experiment.
Variables, types and equality
let vs const, primitives vs references, typeof, === and the truthy/falsy rules that decide every if.
Most wrong answers in JavaScript aren't algorithm bugs. They're an index 0 read as "not found", an array two variables secretly share, or == converting a string behind your back. These rules decide what every assignment, if and comparison in a solution actually does.
let, const and block scope
Use const for anything you never reassign (arrays, maps and sets included: their contents can still change) and let for counters, pointers and running totals. Both exist only inside the nearest block. Skip var: it belongs to the whole function, so a loop variable leaks past its loop and every closure created in the loop shares the same one.
const seen = new Set(); // the binding is fixed; seen.add(x) is still fine
let left = 0, right = n - 1; // pointers move, so let
for (let i = 0; i < n; i++) {} // i exists only inside the loop
k = 2; let k = 1; // ReferenceError: used before its declaration
const total = 0; total += 1; // TypeError: Assignment to constant variable// const by default, let when the variable must change. Both are block-scoped.
const nums = [3, 1, 2];
nums.push(4); // allowed: const blocks reassignment, not mutation
console.log(nums); // [3, 1, 2, 4]
let best = -Infinity;
for (const x of nums) {
const doubled = x * 2; // a fresh variable each iteration, gone after the block
if (doubled > best) best = doubled;
}
console.log(best, typeof doubled); // 8 undefined: doubled doesn't exist out here
// var ignores blocks: one variable for the whole function, visible after the loop.
function loopCounterAfterLoop() {
for (var i = 0; i < 3; i++) {}
return i;
}
console.log(loopCounterAfterLoop()); // 3
// Closures made in a loop: let gives each iteration its own i, var shares one j.
const withLet = [];
for (let i = 0; i < 3; i++) withLet.push(() => i);
const withVar = [];
for (var j = 0; j < 3; j++) withVar.push(() => j);
console.log(withLet.map((f) => f()), withVar.map((f) => f())); // [0, 1, 2] [3, 3, 3]Primitives vs references
Numbers, strings, booleans, null, undefined, bigints and symbols are primitives: assigning or passing one copies the value. Arrays, objects, Maps and Sets are references: assigning one copies a pointer, so two names can edit the same data. That's what makes "modify the array in place" work, and it's also behind the most common backtracking bug.
// Primitives are copied by value.
let a = 5;
let b = a;
b++;
console.log(a, b); // 5 6
// Arrays, objects, Maps and Sets are references: assignment copies the pointer, not the data.
const row = [0, 0, 0];
const alias = row;
alias[0] = 9;
console.log(row, row === alias); // [9, 0, 0] true: one array, two names
const copy = [...row]; // a new array holding the same items
copy[1] = 7;
console.log(row, copy); // [9, 0, 0] [9, 7, 0]
// A function gets the reference: mutating the parameter changes the caller's array...
function zeroFirst(arr) { arr[0] = 0; }
zeroFirst(row);
console.log(row); // [0, 0, 0]
// ...but reassigning the parameter only rebinds the local name.
function replaceAll(arr) { arr = [1, 2, 3]; }
replaceAll(row);
console.log(row); // [0, 0, 0]: the caller never sees the new array
// The backtracking bug: pushing the live path stores the same array every time.
const path = [];
const wrong = [];
const right = [];
for (const x of [1, 2, 3]) {
path.push(x);
wrong.push(path); // a reference to the one shared array
right.push([...path]); // a snapshot of its current contents
}
path.length = 0; // backtracking eventually empties the path
console.log(wrong); // [[], [], []]
console.log(right); // [[1], [1, 2], [1, 2, 3]]Take a snapshot with [...arr], arr.slice() or { ...obj }. Those copies are shallow: the rows of a 2D array are still shared (see Arrays: create, read, update).
typeof and type checks
typeof is fine for numbers, strings and functions, but it answers 'object' for null, arrays, Maps and Sets alike. Use the specific checks instead.
typeof 42 // 'number' (NaN and Infinity too)
typeof 'a' // 'string'
typeof undefined // 'undefined'
typeof 10n // 'bigint'
typeof (() => 1) // 'function'
typeof null // 'object' a historical bug: test x === null
typeof [1, 2] // 'object' test Array.isArray(x)
typeof new Map() // 'object' test x instanceof Map
Number.isNaN(x) // the reliable NaN test (x !== x also works)
Number.isInteger(x) // true for 3 and 3.0, false for 3.5Equality and truthiness
Always compare with === and !==. == converts types first, with rules so irregular that 0 == '' and 0 == '0' are true while '' == '0' is false. The single useful exception is x == null, which matches both null and undefined.
An if converts its condition to a boolean. Exactly eight values are falsy: false, 0, -0, 0n, '', null, undefined and NaN. Everything else is truthy, including [], {} and '0'. In DSA code the dangerous one is 0: it's a valid index, a count, a stored value and a node value.
// The only falsy values. Everything else is truthy, including [], {} and '0'.
const falsy = [false, 0, -0, 0n, '', null, undefined, NaN];
console.log(falsy.every((v) => !v)); // true
console.log(Boolean([]), Boolean({}), Boolean('0')); // true true true
// === compares without converting types; == converts first, with irregular rules.
console.log(1 === '1', 1 == '1'); // false true
console.log(0 == '', 0 == '0', '' == '0'); // true true false: not even transitive
console.log(null == undefined, null == 0); // true false: the one useful == (x == null)
// Arrays and objects compare by reference, never by contents. NaN never equals anything.
console.log([1, 2] === [1, 2]); // false
console.log(NaN === NaN, Number.isNaN(NaN)); // false true
// The DSA trap: index 0, count 0 and value 0 are all falsy.
const nums = [7, 8, 9];
const idx = nums.indexOf(7); // 0
if (idx) console.log('found'); // never runs
if (idx !== -1) console.log('found at', idx); // found at 0
const firstSeenAt = new Map([['a', 0]]);
console.log(firstSeenAt.get('a') ? 'seen' : 'new'); // new (wrong: 'a' was seen at index 0)
console.log(firstSeenAt.has('a') ? 'seen' : 'new'); // seennull, undefined, ?. and ??
undefined means nothing was ever put there: a declared but unset variable, a missing property, an index past the end, a function without return. null means deliberately empty, which is why a missing tree child and the end of a linked list are null. Optional chaining and the nullish operators let you handle both without a crash or an accidental fallback.
// undefined: nothing was ever put here. null: deliberately empty.
const arr = [10, 20];
const obj = { a: 1 };
function noReturn() {}
let notSet;
console.log(arr[5], obj.b, noReturn(), notSet); // undefined undefined undefined undefined
// Tree and list nodes use null for "no child" and "end of list".
const leaf = { val: 4, left: null, right: null };
const root = { val: 2, left: leaf, right: null };
// ?. returns undefined instead of throwing when the left side is null or undefined.
console.log(root.left?.val, root.right?.val); // 4 undefined
console.log(root.right?.left?.val); // undefined
try {
console.log(root.right.val); // throws: no ?. and right is null
} catch (e) {
console.log(e.name); // TypeError
}
// ?? falls back only on null/undefined. || falls back on every falsy value, 0 included.
const counts = { x: 0 };
console.log(counts.x || 10, counts.x ?? 10); // 10 0
console.log(counts.y || 10, counts.y ?? 10); // 10 10
// ??= assigns only when the value is missing: a one-line default.
const memo = {};
memo.k ??= 0;
memo.k += 5;
memo.k ??= 100; // ignored: k is already 5
console.log(memo); // { k: 5 }| Expression | Kicks in when the left side is |
|---|---|
a || b | any falsy value: 0, '', NaN, false, null, undefined |
a ?? b | only null or undefined |
a?.b, a?.[i], f?.() | null or undefined: the whole chain becomes undefined |
a ??= b | null or undefined: only then is b assigned |
Numbers, Math and integer tricks
Integer division, modulo with negatives, Infinity as a sentinel, safe integers, BigInt and floating point.
JavaScript has a single number type: a 64-bit float that stores integers exactly up to 2^53. That covers almost every interview problem, but / never rounds for you, % keeps the sign of negatives, and a product of two large values loses digits without any warning.
Integer division and rounding
a / b always produces a float, so pick a rounding explicitly. Math.floor rounds down and Math.trunc rounds toward zero: they agree for positives and differ for negatives. x | 0 and ~~x truncate as well, but they squeeze the value into 32 bits first, so they wrap around above about 2.1 billion.
// / always returns a float. Choose the rounding the problem needs.
console.log(7 / 2, Math.floor(7 / 2), Math.trunc(7 / 2)); // 3.5 3 3
// With negatives they differ: floor rounds down, trunc rounds toward zero.
console.log(Math.floor(-7 / 2), Math.trunc(-7 / 2)); // -4 -3
// | 0 and ~~ also truncate, but only for results inside the 32-bit range.
console.log((-7 / 2) | 0, ~~(-7 / 2)); // -3 -3
console.log(3e9 | 0); // -1294967296: wrapped around
// Ceiling division: how many groups of k do n items need?
const n = 10, k = 3;
console.log(Math.ceil(n / k), Math.floor((n + k - 1) / k)); // 4 4
// Binary search midpoint: all three agree for ordinary indices...
let lo = 0, hi = 9;
console.log(lo + Math.floor((hi - lo) / 2), Math.floor((lo + hi) / 2), (lo + hi) >> 1); // 4 4 4
// ...but >> 1 breaks once lo + hi reaches 2^31 (searching a big answer range).
lo = 2 ** 30; hi = 2 ** 31;
console.log(Math.floor((lo + hi) / 2), (lo + hi) >> 1); // 1610612736 -536870912
// Math.round sends .5 up (toward +Infinity), not away from zero.
console.log(Math.round(2.5), Math.round(-2.5)); // 3 -2For a binary search midpoint, lo + Math.floor((hi - lo) / 2) is correct for every safe integer. (lo + hi) >> 1 is a fine shortcut for array indices but breaks when you binary search over a large answer range. Unlike Java or C++, lo + hi itself never overflows here; precision only runs out past 2^53.
Modulo with negative numbers
% is a remainder, not a mathematical modulo: -7 % 3 is -1. That breaks circular-array indexing, hash buckets and "is it odd?" tests on negatives. Add the modulus back to land in range.
// % is a remainder: the result takes the sign of the LEFT operand.
console.log(7 % 3, -7 % 3, 7 % -3); // 1 -1 1
// A true modulo always lands in 0..m-1.
const mod = (a, m) => ((a % m) + m) % m;
console.log(mod(-7, 3), mod(7, 3), mod(-3, 3)); // 2 1 0
// Circular arrays: stepping back from index 0.
const ring = ['a', 'b', 'c', 'd', 'e'];
const i = 0;
console.log(ring[(i - 1) % ring.length], ring[mod(i - 1, ring.length)]); // undefined e
// Odd test: compare with 0, because -3 % 2 is -1, not 1.
console.log(-3 % 2 === 1, -3 % 2 !== 0); // false true
// "Return the answer modulo 1e9 + 7": reduce after every step so values stay small.
const MOD = 1_000_000_007;
let ways = 1;
for (let step = 0; step < 100; step++) ways = (ways * 2) % MOD;
console.log(ways); // 976371285 (2^100 mod 1e9+7)Infinity and number limits
Infinity and -Infinity are ordinary numbers: they compare, add and pass through Math.min/Math.max correctly, which makes them the natural starting value for a running minimum or maximum and for "unreached" cells in a DP table.
let best = Infinity; // running minimum: any real value beats it
let most = -Infinity; // running maximum
const dist = new Array(n).fill(Infinity); // "not reached yet" in shortest paths and min-cost DP
Infinity + 5 === Infinity; // true: adding a cost to an unreached state is safe
return best === Infinity ? -1 : best; // "never updated" becomes the required -1
Number.MAX_SAFE_INTEGER; // a finite alternative when a sentinel must stay an integer| Constant | Value | Meaning |
|---|---|---|
Number.MAX_SAFE_INTEGER | 2^53 − 1 ≈ 9.007e15 | every integer up to here is exact |
Number.MAX_VALUE | ≈ 1.8e308 | largest finite number (integers that big are approximate) |
Number.MIN_VALUE | 5e-324 | smallest positive number, not the most negative one |
Number.EPSILON | ≈ 2.2e-16 | gap between 1 and the next float |
| 32-bit signed range | −2^31 to 2^31 − 1 | what bitwise operators and x | 0 work in |
Safe integers and BigInt
Sums are rarely a problem: 10^5 values of up to 10^9 add up to 10^14, far below 2^53 ≈ 9 × 10^15. Products are: two values near 10^9 multiply to 10^18, and the low digits silently vanish. Factorials past 18!, Fibonacci numbers past F(78) and 2 ** n past n = 53 overflow the same way.
When a problem says "return the answer modulo 1e9 + 7", reduce after every addition. For multiplications, convert to BigInt, multiply, take the remainder and convert back. BigInt arithmetic is exact at any size but slower than numbers, can't be mixed with numbers in arithmetic, and doesn't work with Math.*.
// Numbers are exact integers only up to 2^53 - 1.
console.log(Number.MAX_SAFE_INTEGER); // 9007199254740991
console.log(2 ** 53 === 2 ** 53 + 1); // true: the + 1 is lost
console.log(Number.isSafeInteger(2 ** 53)); // false
// The classic silent overflow: multiplying two values near 1e9 before taking %.
const MOD = 1_000_000_007;
const a = 999_999_999, b = 999_999_999;
console.log((a * b) % MOD); // 63 (wrong: a * b is about 1e18)
console.log(Number((BigInt(a) * BigInt(b)) % BigInt(MOD))); // 64 (exact)
// BigInt: exact integers of any size. Literals end in n.
console.log(2n ** 64n); // 18446744073709551616n
console.log(7n / 2n, -7n / 2n); // 3n -3n: division truncates toward zero
try {
console.log(2n ** 64n + 1); // throws
} catch (e) {
console.log(e.name); // TypeError: BigInt and number don't mix
}
console.log(5n > 3, 2n == 2, 2n === 2); // true true false: compare freely, but === checks the type
console.log(Number(123n), BigInt(42)); // 123 42n: convert explicitly
// 25! as a number vs as a BigInt.
let asNumber = 1;
let asBig = 1n;
for (let i = 1; i <= 25; i++) {
asNumber *= i;
asBig *= BigInt(i);
}
console.log(asNumber); // 1.5511210043330986e+25 (approximate)
console.log(asBig); // 15511210043330985984000000n (exact)Floating point and parsing
Floats can't represent most decimals exactly, so never compare computed decimals with ===: check Math.abs(a - b) < 1e-9. toFixed(2) is for display and returns a string. To read numbers out of strings, Number(s) insists on the whole string being numeric, while parseInt(s, 10) reads leading digits and stops. Always pass the radix to parseInt.
// Most decimals have no exact binary form, so tiny errors creep in.
console.log(0.1 + 0.2, 0.1 + 0.2 === 0.3); // 0.30000000000000004 false
const EPS = 1e-9;
console.log(Math.abs(0.1 + 0.2 - 0.3) < EPS); // true: compare with a tolerance
// toFixed rounds for display and returns a STRING.
const avg = (1 + 2 + 2) / 3;
console.log(avg.toFixed(2), typeof avg.toFixed(2)); // 1.67 string
console.log(avg.toFixed(2) + 1); // 1.671: string concatenation
console.log(Number(avg.toFixed(2)) + 1); // 2.67
console.log((1.005).toFixed(2)); // 1.00: 1.005 is stored as 1.00499999...
// Parsing: Number() needs the whole string to be numeric; parseInt() reads leading digits.
console.log(Number('42'), Number(' 42 '), Number('42px'), Number('')); // 42 42 NaN 0
console.log(parseInt('42px', 10), parseInt('3.9', 10), parseInt('', 10)); // 42 3 NaN
console.log(parseInt('1010', 2), parseInt('ff', 16)); // 10 255
// + on a string concatenates; - converts. Convert explicitly before doing math.
console.log('7' + 1, '7' - 1, Number('7') + 1); // 71 6 8Math helpers and huge arrays
Math.abs(-3) // 3
Math.min(a, b), Math.max(a, b)
Math.sqrt(49) // 7 (Number.isInteger(Math.sqrt(x)) tests a perfect square)
Math.pow(2, 10), 2 ** 10 // 1024 both ways
(-2) ** 2 // 4 (-2 ** 2 is a SyntaxError: add parentheses)
Math.sign(-5) // -1
Math.hypot(3, 4) // 5 distance from the origin to (3, 4)
Math.log2(1024) // 10
Math.floor(Math.random() * n) // random integer from 0 to n - 1Math.max(...arr) is handy for small arrays, but spreading turns every element into a function argument, and engines cap the argument count (somewhere between about 65,000 and 500,000, depending on the engine). Inputs of 10^5 or more are common in hidden tests, so use a loop or reduce there.
const small = [3, -1, 7, 2];
console.log(Math.max(...small), Math.min(...small)); // 7 -1
console.log(Math.max(), Math.min()); // -Infinity Infinity: what an empty array gives
// Spreading passes every element as a separate argument, and engines cap the argument count.
const huge = Array.from({ length: 1_000_000 }, (_, i) => i);
try {
console.log(Math.max(...huge));
} catch (e) {
console.log(e.name); // RangeError
}
// A loop (or reduce) handles any length, still in O(n).
let best = -Infinity;
for (const x of huge) if (x > best) best = x;
console.log(best); // 999999
console.log(huge.reduce((m, x) => (x > m ? x : m), -Infinity)); // 999999Used in: Binary SearchGreedyBit Manipulation
Strings and characters
Immutable strings, char codes, slicing, splitting and joining, and building strings without O(n²) concatenation.
Palindromes, anagrams, substring windows and parsing problems all run on strings. JavaScript strings are immutable sequences of UTF-16 code units: reading a character is O(1), but every "change" builds a new string, so knowing what copies is what keeps a loop O(n).
Reading characters and immutability
Index with s[i] or s.at(i) (which accepts negatives: s.at(-1) is the last character). An index past the end gives undefined, not an error. You can't assign to s[i]: strict mode throws a TypeError and sloppy mode silently ignores it. Build a new string, or work on an array of characters and join it back.
const s = 'hello';
console.log(s[0], s.at(-1), s.length); // h o 5
console.log(s[10], s.charAt(10) === ''); // undefined true: out of range is not an error
// Strings are immutable: methods return a NEW string and leave s alone.
const upper = s.toUpperCase();
console.log(s, upper); // hello HELLO
const fixed = 'j' + s.slice(1); // "change" the first letter by building a new string
console.log(fixed, s); // jello hello
// To edit several characters, go through an array and join once.
const chars = [...s];
[chars[0], chars[4]] = [chars[4], chars[0]];
console.log(chars.join('')); // oellh
// for...of walks characters; indexing walks UTF-16 code units (an emoji is two).
for (const ch of 'hi!') console.log(ch, ch.charCodeAt(0));
// h 104
// i 105
// ! 33
console.log('😀'.length, [...'😀'].length); // 2 1Interview inputs are almost always ASCII, where one character is one code unit. Emoji and some other symbols take two: for...of and [...s] handle them, s[i] and s.length don't.
Character codes and the array of 26
s.charCodeAt(i) turns a character into a number and String.fromCharCode(code) turns it back. Subtracting 97 (the code of 'a') maps lowercase letters to 0..25, which is what makes a plain array of 26 counters work as a fast, fixed-size frequency table. Use codePointAt only if you must handle emoji.
// Lowercase letters are codes 97..122, uppercase 65..90, digits 48..57.
console.log('a'.charCodeAt(0), 'z'.charCodeAt(0), 'A'.charCodeAt(0), '0'.charCodeAt(0)); // 97 122 65 48
console.log(String.fromCharCode(99), String.fromCharCode(65 + 25)); // c Z
// Letter -> index 0..25 and back.
const idx = (ch) => ch.charCodeAt(0) - 97;
console.log(idx('a'), idx('e'), String.fromCharCode(97 + 4)); // 0 4 e
console.log('7'.charCodeAt(0) - 48, Number('7')); // 7 7: digit character -> number
// Shift letters by k, wrapping past 'z' (Caesar cipher).
const shift = (s, k) => [...s].map((ch) => String.fromCharCode(97 + ((idx(ch) + k) % 26))).join('');
console.log(shift('xyz', 3)); // abc
// The array of 26: letter counts in O(1) extra space, faster than a Map.
function isAnagram(a, b) {
if (a.length !== b.length) return false;
const count = new Array(26).fill(0);
for (let i = 0; i < a.length; i++) {
count[a.charCodeAt(i) - 97]++;
count[b.charCodeAt(i) - 97]--;
}
return count.every((c) => c === 0);
}
console.log(isAnagram('listen', 'silent'), isAnagram('rat', 'car')); // true false
// The counts joined into a string make an O(k) grouping key (no sorting needed).
function signature(word) {
const count = new Array(26).fill(0);
for (const ch of word) count[idx(ch)]++;
return count.join(',');
}
console.log(signature('eat') === signature('tea'), signature('eat') === signature('tan')); // true falseconst isLower = (ch) => ch >= 'a' && ch <= 'z';
const isDigit = (ch) => ch >= '0' && ch <= '9';
const isAlnum = (ch) => /[a-z0-9]/i.test(ch); // letters or digits, any case
const counts = new Array(26).fill(0); // 'a'..'z'; use 128 for any ASCII character
counts[ch.charCodeAt(0) - 97]++;Slicing, searching and splitting
slice(start, end) copies the characters from start up to, but not including, end, and accepts negative indices counted from the end. substring looks similar but swaps reversed arguments and treats negatives as 0; substr is deprecated. Prefer slice everywhere.
s.slice(i, j) // characters i..j-1 (a new string)
s.indexOf(t), s.lastIndexOf(t) // first / last position, or -1
s.includes(t), s.startsWith(t), s.endsWith(t)
s.split(','), s.split('') // to an array ([...s] for characters)
arr.join(''), arr.join(' ') // back to a string
s.trim(), s.toLowerCase(), s.toUpperCase()
s.repeat(3), s.padStart(8, '0'), s.replaceAll('a', 'b')const s = 'interview';
console.log(s.slice(0, 5), s.slice(5), s.slice(-4)); // inter view view
console.log([s.slice(5, 2), s.substring(5, 2)]); // ['', 'ter']: substring swaps reversed arguments
console.log(s.slice(-4, -1), s.substring(-4)); // vie interview: substring treats negatives as 0
console.log(s.indexOf('e'), s.lastIndexOf('e'), s.indexOf('z')); // 3 7 -1
console.log(s.includes('view'), s.startsWith('inter'), s.endsWith('w')); // true true true
// split keeps empty fields; trim and split on a regex to get words.
console.log('a,b,,c'.split(',')); // ['a', 'b', '', 'c']
console.log(' two spaces '.split(' ')); // ['', '', 'two', '', '', 'spaces', '']
console.log(' two spaces '.trim().split(/\s+/)); // ['two', 'spaces']
console.log([...'abc'], ['2024', '01', '05'].join('-')); // ['a', 'b', 'c'] 2024-01-05
console.log('ab'.repeat(3), '7'.padStart(3, '0'), 'MiXeD'.toLowerCase()); // ababab 007 mixedBuilding strings efficiently
In principle result += ch copies the whole string each time, which would make a loop O(n²). Modern engines optimise plain appends, so a short += loop is fine in practice, but you can't rely on it in a complexity argument, and it doesn't help when you need to change characters in the middle. The idiom that is linear everywhere: push pieces into an array (or use it as a stack) and call join('') once at the end.
// Collect pieces in an array and join once: linear in every engine.
function compress(s) { // 'aaabcc' -> 'a3b1c2'
const parts = [];
let i = 0;
while (i < s.length) {
let j = i;
while (j < s.length && s[j] === s[i]) j++;
parts.push(s[i], j - i);
i = j;
}
return parts.join('');
}
console.log(compress('aaabcc')); // a3b1c2
// Split, transform the array, join.
console.log(' the sky is blue '.trim().split(/\s+/).reverse().join(' ')); // blue is sky the
// An array used as a stack of characters, joined at the end.
function removeAdjacentPairs(s) {
const stack = [];
for (const ch of s) {
if (stack.at(-1) === ch) stack.pop();
else stack.push(ch);
}
return stack.join('');
}
console.log(removeAdjacentPairs('abbaca')); // ca
// Reverse in place: two pointers over a character array.
const chars = [...'stressed'];
for (let l = 0, r = chars.length - 1; l < r; l++, r--) [chars[l], chars[r]] = [chars[r], chars[l]];
console.log(chars.join('')); // dessertsComparing and sorting strings
===, < and > compare strings character by character by code unit. So every uppercase letter sorts before every lowercase one and '10' < '9'. That's exactly what the default sort() does too. Use a.localeCompare(b) when you need dictionary order, and lowercase both sides for case-insensitive comparisons.
// < and > compare UTF-16 code units, one character at a time.
console.log('apple' < 'banana', 'app' < 'apple'); // true true: a prefix sorts first
console.log('Zebra' < 'apple'); // true: all uppercase letters come before lowercase
console.log('10' < '9', 10 < 9); // true false: digits compared as characters
// The default sort uses the same code-unit order; localeCompare gives dictionary order.
const words = ['banana', 'Cherry', 'apple'];
console.log([...words].sort()); // ['Cherry', 'apple', 'banana']
console.log([...words].sort((a, b) => a.localeCompare(b))); // ['apple', 'banana', 'Cherry']
console.log('Hello'.toLowerCase() === 'hELLO'.toLowerCase()); // true: case-insensitive equality
// Sorted characters: the classic anagram key, O(k log k) per word.
const key = (w) => [...w].sort().join('');
console.log(key('listen'), key('listen') === key('silent')); // eilnst true
// Template literals build composite keys and readable output.
const r = 2, c = 5;
console.log(`${r},${c}`, `cell (${r}, ${c}) = ${r * c}`); // 2,5 cell (2, 5) = 10What string operations cost
| Operation | Cost |
|---|---|
s[i], s.at(i), s.length, charCodeAt | O(1) |
slice, substring, trim, toLowerCase, repeat | O(length of the result) |
split, join, [...s], for...of | O(n) |
indexOf, includes for a pattern of length m | O(n · m) worst case, usually much faster |
s === t, s < t | O(length) worst case |
[...s].sort().join('') | O(n log n) |
s += t in a loop | O(n) per step in theory, often optimised; use an array and join to be safe |
Calling slice or includes inside a loop over the same string quietly multiplies the cost by n: an O(n) loop around them is O(n²).
Used in: Hash Maps and SetsSliding WindowTries (Prefix Trees)
Arrays: create, read, update
Creating 1D and 2D arrays safely, push/pop vs shift/unshift costs, slice vs splice, and at(-1).
Arrays are the input to most problems and the storage behind DP tables, stacks, queues and adjacency lists. The traps are in how you create them (shared rows), which end you add to and remove from (O(1) or O(n)), and whether a method copies the array or changes it.
Creating 1D arrays
const nums = [5, 1, 4]; // literal
const zeros = new Array(n).fill(0); // n zeros (DP rows, counters)
const dist = new Array(n).fill(Infinity); // "unreached"
const ids = Array.from({ length: n }, (_, i) => i); // [0, 1, …, n-1] (union-find parents)
const chars = Array.from('abc'); // from any iterable: ['a', 'b', 'c']new Array(n) on its own creates n holes: slots with no value that map, forEach and reduce skip, so new Array(n).map(…) does nothing useful. Always fill first or use Array.from. Holes also appear with delete arr[i] and literals like [1, , 3]; avoid them.
const zeros = new Array(5).fill(0);
console.log(zeros); // [0, 0, 0, 0, 0]
const idx = Array.from({ length: 5 }, (_, i) => i);
console.log(idx); // [0, 1, 2, 3, 4]
const squares = Array.from({ length: 4 }, (_, i) => i * i);
console.log(squares); // [0, 1, 4, 9]
console.log(Array.from('abc'), Array.from(new Set([3, 3, 1]))); // ['a', 'b', 'c'] [3, 1]
// new Array(n) alone makes n HOLES: empty slots that map, forEach and reduce skip.
const holes = new Array(3);
let visits = 0;
holes.forEach(() => visits++);
console.log(holes.length, 0 in holes, visits); // 3 false 0
console.log(new Array(3).fill(0).map((_, i) => i * 10)); // [0, 10, 20]: fill first, then map
// A single number means "length". Array.of always means "these items".
console.log(new Array(3).length, Array.of(3), Array.of(3, 4)); // 3 [3] [3, 4]
// length is writable: shrink to truncate, set to 0 to clear in place.
const a = [1, 2, 3, 4];
a.length = 2;
console.log(a); // [1, 2]
a.length = 0;
console.log(a); // []2D arrays without shared rows
fill(value) stores the same value in every slot. When that value is an array, every row is the same array, and writing to grid[0][0] changes every row. This is one of the most common bugs in DP and grid solutions. Array.from with a function creates a fresh row for each index.
const grid = Array.from({ length: m }, () => new Array(n).fill(0)); // m × n zeros
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0)); // with a padding row/column
const adj = Array.from({ length: n }, () => []); // n empty adjacency lists
const copy = grid.map((row) => [...row]); // copy a grid row by rowconst rows = 3, cols = 4;
// WRONG: fill puts the SAME row object into every slot.
const shared = new Array(rows).fill(new Array(cols).fill(0));
shared[0][0] = 1;
console.log(shared.map((r) => r.join(''))); // ['1000', '1000', '1000']: every row changed
console.log(shared[0] === shared[2]); // true: one row, three references
// The same trap with fill([]) for buckets or adjacency lists.
const buckets = new Array(3).fill([]);
buckets[0].push('x');
console.log(buckets); // [['x'], ['x'], ['x']]
// RIGHT: Array.from calls the function once per row, so every row is a new array.
const grid = Array.from({ length: rows }, () => new Array(cols).fill(0));
grid[0][0] = 1;
console.log(grid.map((r) => r.join(''))); // ['1000', '0000', '0000']
const adj = Array.from({ length: 3 }, () => []);
adj[0].push(1);
console.log(adj); // [[1], [], []]
// Copying a grid: [...grid] copies only the outer array; the rows are still shared.
const shallow = [...grid];
const deep = grid.map((row) => [...row]); // or structuredClone(grid)
grid[1][1] = 7;
console.log(shallow[1][1], deep[1][1]); // 7 0Array ends and their costs
Arrays are fast at the end and slow at the front. push, pop and at(-1) make an array a perfect stack. shift and unshift move every other element one slot, so a queue built on shift() turns an O(n) BFS into O(n²) on large inputs (see Stacks, queues and deques for a fast queue).
arr.push(x); // add to the end, returns the new length
arr.pop(); // remove and return the last item (undefined if empty)
arr.at(-1); // peek at the last item: same as arr[arr.length - 1]
arr.unshift(x); // add to the front: shifts everything
arr.shift(); // remove from the front: shifts everything| Operation | Cost |
|---|---|
arr[i], arr[i] = x, arr.length, at(i) | O(1) |
push, pop | O(1) (push is amortised) |
shift, unshift | O(n) |
splice(i, k, …items) | O(n − i): everything after i moves |
slice, concat, [...arr], flat | O(n) for the new array |
indexOf, includes, find, findIndex | O(n) |
reverse, fill | O(n) |
sort | O(n log n) |
slice, splice and copies
The two names differ by one letter and behave in opposite ways. slice(start, end) copies a range into a new array and leaves the original alone. splice(start, deleteCount, …items) mutates: it removes and/or inserts in place and returns the removed items. Spread and concat also copy. ES2023 added non-mutating versions of the mutating methods: toReversed, toSorted, toSpliced and with(i, value).
const a = [10, 20, 30, 40, 50];
// slice(start, end) COPIES a range and leaves the original alone.
console.log(a.slice(1, 3), a.slice(-2)); // [20, 30] [40, 50]
console.log(a); // [10, 20, 30, 40, 50]
// splice(start, deleteCount, ...items) MUTATES and returns what it removed.
const removed = a.splice(1, 2); // remove 2 items starting at index 1
console.log(removed, a); // [20, 30] [10, 40, 50]
a.splice(1, 0, 15, 17); // insert at index 1, removing nothing
console.log(a); // [10, 15, 17, 40, 50]
a.splice(-1); // remove from the last index to the end
console.log(a); // [10, 15, 17, 40]
// Spread and concat make new (shallow) arrays.
const b = [1, 2];
console.log([...b, 3], b.concat([4, 5]), b); // [1, 2, 3] [1, 2, 4, 5] [1, 2]
// Non-mutating twins (ES2023): toReversed, toSorted, toSpliced, with.
console.log(b.toReversed(), b.with(0, 99), b.toSpliced(0, 1), b); // [2, 1] [99, 2] [2] [1, 2]Searching an array
arr.indexOf(x) // first index of x (compared with ===), or -1
arr.lastIndexOf(x) // last index, or -1
arr.includes(x) // true/false; unlike indexOf it finds NaN
arr.find((x) => x > 3) // first element passing the test, or undefined
arr.findIndex((x) => x > 3) // its index, or -1
arr.findLast((x) => x > 3) // search from the end (also findLastIndex)Every one of these scans the array. Inside a loop they make your solution O(n²); when you test membership repeatedly, build a Set once (see Map and Set).
In-place edits vs new arrays
"Modify the array in place" means writing into the array you were given: nums[i] = …, push, splice, reverse, fill, sort, or nums.length = k to cut the tail. map, filter, slice, concat and spread all return a new array, and assigning it to the parameter only changes your local variable.
// "Remove every val in place": a write pointer, then cut the tail with length.
function removeValue(nums, val) {
let w = 0;
for (const x of nums) if (x !== val) nums[w++] = x;
nums.length = w;
return w;
}
const nums = [3, 2, 2, 3, 4];
console.log(removeValue(nums, 3), nums); // 3 [2, 2, 4]: the caller's array changed
// filter builds a NEW array; reassigning the parameter doesn't reach the caller.
function removeWithFilter(arr, val) {
arr = arr.filter((x) => x !== val);
return arr.length;
}
const other = [3, 2, 2, 3, 4];
console.log(removeWithFilter(other, 3), other); // 3 [3, 2, 2, 3, 4]: unchanged
// reverse and fill work in place and return the same array.
const a = [1, 2, 3, 4, 5];
console.log(a.reverse() === a); // true
a.fill(0, 3); // from index 3 to the end
console.log(a); // [5, 4, 3, 0, 0]
// flat returns a new array with nested arrays spread out.
console.log([[1], [2, [3]]].flat(), [[1], [2, [3]]].flat(Infinity)); // [1, 2, [3]] [1, 2, 3]Used in: Two PointersPrefix Sums and Difference ArraysBinary SearchStacks and Monotonic StacksUnion-Find (Disjoint Set Union)BacktrackingDynamic Programming I: 1DDynamic Programming II: Grids, Strings and KnapsackDesign Data Structures: LRU, LFU and FriendsMatrix and Grid Simulation
Iterating and transforming arrays
for, for...of, forEach, map, filter, reduce, some, every, find and when each one is the right tool.
Almost every solution is a loop over an array. Picking the right form decides whether you can stop early, whether you have the index, and whether you quietly allocate a new array at every step of a chain.
Choosing a loop
| Loop | Gives you | break / continue | Use it for |
|---|---|---|---|
for (let i = 0; …; i++) | the index | yes | index math, neighbours, two pointers, going backwards |
for (const x of arr) | each value | yes | reading every element; also strings, Maps and Sets |
for (const [i, x] of arr.entries()) | index and value | yes | when you need both and might stop early |
arr.forEach((x, i) => …) | value and index | no | side effects when you never stop early |
for (const k in obj) | keys, as strings | yes | plain objects only, and Object.keys is usually better |
for...in on an array hands you '0', '1', … as strings, so k + 1 concatenates, and it also visits any extra enumerable properties. Use for...of or a counted loop instead.
const nums = [4, 8, 15, 16];
// for: you control the index (go backwards, step by 2, look at neighbours).
const backwards = [];
for (let i = nums.length - 1; i >= 0; i--) backwards.push(nums[i]);
console.log(backwards); // [16, 15, 8, 4]
// for...of: the values themselves; break and continue work.
const small = [];
for (const x of nums) {
if (x > 10) break;
small.push(x);
}
console.log(small); // [4, 8]
// for...in: KEYS, as strings. It's meant for objects, not arrays.
const keys = [];
for (const k in nums) keys.push(k);
console.log(keys); // ['0', '1', '2', '3']
console.log(keys[1] + 1); // 11: string concatenation, not 2
// forEach can't stop early: return only ends the current callback.
let calls = 0;
nums.forEach((x) => {
calls++;
if (x === 8) return; // behaves like continue, never like break
});
console.log(calls); // 4: every element was still visitedmap, filter and reduce
map returns a new array of the same length, filter returns a new array of the elements that pass, and reduce folds the array into a single value (a sum, a Map, an object). Always give reduce its initial value: without one it uses the first element as the accumulator, which is wrong whenever the result has a different type, and it throws on an empty array.
const nums = [3, 1, 4, 1, 5];
console.log(nums.map((x) => x * 2)); // [6, 2, 8, 2, 10]
console.log(nums.filter((x) => x % 2 === 1)); // [3, 1, 1, 5]
console.log(nums.map((x, i) => x * i)); // [0, 1, 8, 3, 20]: callbacks also get the index
// reduce folds the array into one value. Always pass the initial value.
console.log(nums.reduce((sum, x) => sum + x, 0)); // 14
const freq = nums.reduce((m, x) => m.set(x, (m.get(x) ?? 0) + 1), new Map());
console.log(freq); // Map(4) { 3 => 1, 1 => 2, 4 => 1, 5 => 1 }
// Without an initial value, the first ELEMENT becomes the accumulator...
const pairs = [[1, 'a'], [2, 'b']];
console.log(pairs.reduce((acc, [n]) => acc + n)); // 1,a2: acc started as the array [1, 'a']
console.log(pairs.reduce((acc, [n]) => acc + n, 0)); // 3
// ...and an empty array throws.
try {
[].reduce((a, b) => a + b);
} catch (e) {
console.log(e.name); // TypeError
}
// map calls fn(value, index, array): parseInt takes the index as its radix.
console.log(['1', '2', '3'].map(parseInt)); // [1, NaN, NaN]
console.log(['1', '2', '3'].map(Number)); // [1, 2, 3]Early exit with some, every and find
some stops at the first element that passes, every at the first that fails, and find/findIndex at the first match. On an empty array, every is true and some is false. forEach has no way to stop: if you need to break, use for...of or one of these.
nums.some((x) => x < 0) // is there any negative?
nums.every((x, i) => i === 0 || nums[i - 1] <= x) // is it sorted?
nums.find((x) => x > target) // first element above target, or undefined
nums.findIndex((x) => x > target) // its index, or -1const nums = [2, 4, 7, 8, 10];
let checks = 0;
const isOdd = (x) => {
checks++;
return x % 2 !== 0;
};
// some, every, find and findIndex stop as soon as the answer is known.
console.log(nums.some(isOdd), checks); // true 3: stopped at 7
checks = 0;
console.log(nums.every((x) => !isOdd(x)), checks); // false 3: stopped at 7 again
console.log(nums.find((x) => x > 5), nums.findIndex((x) => x > 5)); // 7 2
console.log(nums.find((x) => x > 50), nums.findIndex((x) => x > 50)); // undefined -1
// Empty arrays: every is true (no counterexample), some is false.
console.log([].every((x) => x > 0), [].some((x) => x > 0)); // true false
// Index and value together, with early exit.
for (const [i, x] of nums.entries()) {
if (x > 7) {
console.log(`first value above 7 is ${x} at index ${i}`); // first value above 7 is 8 at index 3
break;
}
}Index and value together
for (const [i, x] of arr.entries()) {} // index and value, break works
arr.forEach((x, i) => {}); // index is the second argument
arr.map((x, i) => x * i); // so is map's, filter's, some's…
for (const i of arr.keys()) {} // 0, 1, 2, … (rarely needed)Callbacks receive (value, index, array), so passing a function that takes a second parameter can surprise you: ['1', '2', '3'].map(parseInt) gives [1, NaN, NaN] because the index becomes the radix. Write map(Number) or map((s) => parseInt(s, 10)).
Chaining and hot loops
A chain like arr.filter(…).map(…).reduce(…) is still O(n) overall, but every step is another pass and another array. That's fine for clarity. Switch to a plain for loop when you need several results at once, when you might stop early, or inside the inner loop of an O(n²) DP where allocation adds up. Above all, watch for searches hidden in a callback: includes, indexOf or find inside filter or map is a nested loop.
const scores = [72, 95, 64, 88, 100, 53];
// A chain reads well, but each step is a full pass that builds a new array.
const curvedTotal = scores.filter((s) => s >= 60).map((s) => s + 5).reduce((a, b) => a + b, 0);
console.log(curvedTotal); // 444
// One loop: one pass, no intermediate arrays, and several results at once.
let total = 0, passed = 0, best = -Infinity;
for (const s of scores) {
if (s < 60) continue;
total += s + 5;
passed++;
if (s > best) best = s;
}
console.log(total, passed, best); // 444 5 100
// A hidden nested loop: includes inside filter is O(n * m).
const a = [1, 2, 3, 4, 5, 6];
const b = [4, 5, 6, 7];
console.log(a.filter((x) => b.includes(x))); // [4, 5, 6]: O(n * m)
const inB = new Set(b);
console.log(a.filter((x) => inB.has(x))); // [4, 5, 6]: O(n + m)| Method | Time | Extra space |
|---|---|---|
for, for...of, forEach | O(n) | O(1) |
map, filter | O(n) | O(n) for the new array |
reduce | O(n) | whatever the accumulator holds |
some, every, find, findIndex | O(position of the first decisive element), O(n) worst | O(1) |
a.filter(…).map(…) | O(n) per step | one new array per step |
includes / indexOf inside any of the above | O(n · m) | O(1) |
Sorting and comparators
The default lexicographic sort trap, numeric and multi-key comparators, stability and toSorted.
Sorting first is the setup step for two pointers, intervals, greedy and binary search. In JavaScript the default sort() compares numbers as strings, a bug that passes the sample tests with single digits and fails the hidden ones with 10 or more.
The default sort trap
Without a comparator, sort converts every element to a string and orders by UTF-16 code units, so 100 comes before 25 and -1 before -5. For numbers, always pass (a, b) => a - b (ascending) or (a, b) => b - a (descending). sort also mutates the array and returns the same array, not a copy.
// Without a comparator, sort converts every element to a string and compares those.
console.log([10, 9, 1, 100, 25].sort()); // [1, 10, 100, 25, 9]
console.log([-1, -5, 2].sort()); // [-1, -5, 2]: '-1' < '-5' as text
console.log([10, 9, 1, 100, 25].sort((a, b) => a - b)); // [1, 9, 10, 25, 100]
console.log([10, 9, 1, 100, 25].sort((a, b) => b - a)); // [100, 25, 10, 9, 1]
// sort mutates the array AND returns it: both names point at the same sorted array.
const nums = [3, 1, 2];
const sorted = nums.sort((a, b) => a - b);
console.log(sorted === nums, nums); // true [1, 2, 3]
// toSorted (ES2023) returns a sorted copy and leaves the original alone.
const original = [3, 1, 2];
console.log(original.toSorted((a, b) => a - b), original); // [1, 2, 3] [3, 1, 2]
console.log([...original].sort((a, b) => a - b)); // [1, 2, 3]: copy first, works everywhereWriting comparators
A comparator (a, b) => … returns a negative number to put a first, a positive number to put b first, and 0 for a tie. It must be consistent: the same pair always gets the same answer. Common mistakes break that contract silently, and the result then depends on the engine and the input size.
nums.sort((a, b) => a - b); // numbers ascending
nums.sort((a, b) => b - a); // numbers descending
words.sort(); // strings by code unit: fine for plain lowercase
words.sort((a, b) => a.localeCompare(b)); // dictionary order, case-aware
const cmp = (a, b) => (a < b ? -1 : a > b ? 1 : 0); // generic: numbers, strings, BigInts// Comparator contract: negative = a first, positive = b first, 0 = tie.
// Returning a boolean is a bug: true/false become 1/0, never negative.
console.log([3, 1, 2].sort((a, b) => a > b)); // [3, 1, 2] in V8 (Chrome, Node): nothing moved
// a - b only works for numbers. On strings it is NaN, which counts as a tie.
console.log(['pear', 'fig', 'apple'].sort((a, b) => a - b)); // ['pear', 'fig', 'apple']
// A three-way compare works for numbers, strings and BigInts alike.
const cmp = (a, b) => (a < b ? -1 : a > b ? 1 : 0);
console.log(['pear', 'fig', 'apple'].sort(cmp)); // ['apple', 'fig', 'pear']
console.log([3n, 1n, 2n].sort(cmp)); // [1n, 2n, 3n] (a - b would throw a TypeError here)
console.log(['b', 'C', 'a'].sort((a, b) => a.localeCompare(b))); // ['a', 'b', 'C']: dictionary order
// Descending: swap the arguments, or negate the result.
console.log(['fig', 'apple', 'pear'].sort((a, b) => cmp(b, a))); // ['pear', 'fig', 'apple']Multi-key and tuple sorts
Compare the first key, and only on a tie move on to the next: a[0] - b[0] || a[1] - b[1] works because a tie is 0, which is falsy, so || evaluates the second key. This is the standard setup for intervals (by start, then end), frequency rankings, and "sort these indices by their values".
// Intervals by start, then by end: || moves on to the next key only on a tie (0).
const intervals = [[5, 8], [1, 4], [1, 2], [3, 9]];
intervals.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
console.log(intervals); // [[1, 2], [1, 4], [3, 9], [5, 8]]
// By frequency (descending), then by value (ascending).
const nums = [4, 1, 2, 2, 3, 3, 3, 4];
const count = new Map();
for (const x of nums) count.set(x, (count.get(x) ?? 0) + 1);
const byFreq = [...count.keys()].sort((a, b) => count.get(b) - count.get(a) || a - b);
console.log(byFreq); // [3, 2, 4, 1]
// Longest word first, ties alphabetical.
const words = ['kiwi', 'fig', 'banana', 'apple', 'date'];
console.log(words.sort((a, b) => b.length - a.length || a.localeCompare(b))); // ['banana', 'apple', 'date', 'kiwi', 'fig']
// Sort indices by the values they point to, leaving the data where it is.
const heights = [160, 150, 175, 155];
const order = heights.map((_, i) => i).sort((i, j) => heights[i] - heights[j]);
console.log(order); // [1, 3, 0, 2]
// Stable since ES2019: ties keep their original relative order.
const tasks = [['write', 2], ['test', 1], ['ship', 2], ['plan', 1]];
console.log(tasks.toSorted((a, b) => a[1] - b[1]).map(([name]) => name)); // ['test', 'plan', 'write', 'ship']Stable sorts and toSorted
Since ES2019 sort is guaranteed stable: elements that compare as equal keep their original relative order. That means you can sort by a secondary key first and then by the , and that ties never shuffle unpredictably.
sort, reverse and splice change the array in place. When the caller's array must stay untouched (or you're sorting a parameter you'll read again), use the ES2023 copies or copy first:
const sorted = nums.toSorted((a, b) => a - b); // new array; nums unchanged
const backwards = nums.toReversed(); // new array
const copySorted = [...nums].sort((a, b) => a - b); // same idea, works in older engines
nums.sort((a, b) => a - b).reverse(); // both mutate nums in placeSorting costs and counting sort
| Operation | Time | Extra space |
|---|---|---|
sort(cmp), toSorted(cmp) | O(n log n) comparisons | O(n) (merge buffer; toSorted also copies) |
| Comparator calls | about n log₂ n of them | keep each O(1): precompute keys outside |
| Sorting n strings of length up to L | O(n log n · L) | O(n) |
| Counting sort over values 0..k | O(n + k) | O(k) |
| Bucket by frequency | O(n) | O(n) |
If a problem demands O(n), a comparison sort is out. When the values come from a small range (letters, ages, scores, digits) or you only need them grouped by count, counting into an array or buckets beats sort.
// Counting sort: O(n + k) for integers in a small range 0..k.
function countingSort(nums, maxValue) {
const count = new Array(maxValue + 1).fill(0);
for (const x of nums) count[x]++;
const out = [];
for (let v = 0; v <= maxValue; v++) {
for (let c = 0; c < count[v]; c++) out.push(v);
}
return out;
}
console.log(countingSort([3, 0, 2, 3, 1, 0], 3)); // [0, 0, 1, 2, 3, 3]
// Bucket by frequency: the k most frequent values in O(n), no comparison sort at all.
function topKFrequent(nums, k) {
const freq = new Map();
for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
const buckets = Array.from({ length: nums.length + 1 }, () => []); // index = frequency
for (const [x, f] of freq) buckets[f].push(x);
const res = [];
for (let f = nums.length; f > 0 && res.length < k; f--) res.push(...buckets[f]);
return res.slice(0, k);
}
console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // [1, 2]Used in: Two PointersIntervals and Sweep LineHeaps: Top-K, K-way Merge and Two HeapsGreedy
Objects as records and dictionaries
Object literals, dynamic keys, Object.keys/values/entries, and why string keys bite when you count numbers.
Plain objects are JavaScript's records ({ start, end }, { node, depth }) and the quick dictionary many solutions reach for. They're great for fixed shapes and string keys, but every key becomes a string and every object inherits a few keys you never added, which bites when you count numbers or arbitrary words.
Object literals and dynamic keys
const point = { r: 0, c: 0 }; // literal
const { r, c } = point; // read several fields at once
const state = { r, c, steps: 0 }; // shorthand: { r: r, c: c, steps: 0 }
point.r = 3; // dot: the key is literally "r"
point[key] = 1; // brackets: the key is the VALUE of key
const obj = { [key]: 1 }; // computed key in a literal
obj.missing; // undefined, not an error
delete obj[key]; // remove a keyUse dot access for fixed field names and brackets whenever the key is in a variable. obj.key and obj[key] are different lookups: the first always reads a property named "key".
Keys, values and entries
Object.keys, Object.values and Object.entries return arrays you can loop over or chain, and Object.fromEntries turns [key, value] pairs back into an object. All of them include only the object's own enumerable string keys, which is what you want (unlike for...in, which also walks inherited ones).
const scores = { ana: 90, ben: 72, cy: 85 };
console.log(Object.keys(scores)); // ['ana', 'ben', 'cy']
console.log(Object.values(scores)); // [90, 72, 85]
console.log(Object.entries(scores)); // [['ana', 90], ['ben', 72], ['cy', 85]]
console.log(Object.keys(scores).length); // 3: there is no .size, and this is O(n)
// Loop over pairs with destructuring.
let best = null;
for (const [name, score] of Object.entries(scores)) {
if (best === null || score > scores[best]) best = name;
}
console.log(best); // ana
// fromEntries turns pairs back into an object: filter or transform in one line.
const passed = Object.fromEntries(Object.entries(scores).filter(([, s]) => s >= 80));
console.log(passed); // { ana: 90, cy: 85 }
const curved = Object.fromEntries(Object.entries(scores).map(([k, v]) => [k, v + 5]));
console.log(curved); // { ana: 95, ben: 77, cy: 90 }
// Computed keys and shorthand.
const field = 'age';
const x = 3, y = 4;
const person = { name: 'Ana', [field]: 31, x, y }; // [expr] computes the key; x means x: x
person[`${field}Next`] = 32; // brackets read or write any computed key
console.log(person); // { name: 'Ana', age: 31, x: 3, y: 4, ageNext: 32 }
console.log(person.field, person[field]); // undefined 31: .field looks for a key named "field"| Operation | Cost |
|---|---|
obj[key], obj[key] = v, key in obj, Object.hasOwn | O(1) average |
Object.keys / values / entries | O(n), builds a new array |
Object.keys(obj).length (the "size") | O(n) |
{ ...obj }, Object.assign({}, obj) | O(n) |
structuredClone(obj) | O(total size of everything nested) |
Keys are always strings
obj[3] and obj['3'] are the same entry: numbers (and anything else) are converted to strings when used as keys. When you count numbers in an object, Object.keys gives you strings back, includes(3) fails, and arithmetic on a key concatenates. Arrays and objects used as keys turn into strings like '1,2' and '[object Object]'. Key order also isn't pure insertion order: integer-like keys ('0', '2', '10') come first in ascending order, then everything else as inserted.
// Counting numbers in an object: every key is turned into a string.
const nums = [3, -1, 3, 10, 2];
const count = {};
for (const n of nums) count[n] = (count[n] ?? 0) + 1;
console.log(count); // { '2': 1, '3': 2, '10': 1, '-1': 1 }
console.log(Object.keys(count)); // ['2', '3', '10', '-1']: strings, not numbers
console.log(Object.keys(count).includes(3)); // false: 3 !== '3'
console.log(Object.keys(count).map(Number)); // [2, 3, 10, -1]: convert back yourself
console.log(count[3] === count['3']); // true: obj[3] and obj['3'] are the same key
// Key order: integer-like keys first, ascending; then the rest in insertion order.
// That is why 2, 3 and 10 jumped ahead while '-1' (not integer-like) stayed last.
// Arrays and objects used as keys are stringified too.
const visited = {};
visited[[1, 2]] = true; // key '1,2'
visited[{ r: 0 }] = true;
visited[{ r: 5 }] = true; // the same key as the line above
console.log(Object.keys(visited)); // ['1,2', '[object Object]']
// A Map keeps number keys as numbers, in insertion order.
const m = new Map();
for (const n of nums) m.set(n, (m.get(n) ?? 0) + 1);
console.log([...m.keys()]); // [3, -1, 10, 2]Checking whether a key exists
key in obj also finds inherited keys, so 'toString' in {} is true. Object.hasOwn(obj, key) checks only the object's own keys. Testing obj[key] for truthiness fails on a stored 0, and even !== undefined fails when undefined was stored deliberately. If keys come from input words, inherited names like constructor can collide with your counts: a Map, or an object made with Object.create(null), has no inherited keys.
const counts = { a: 1, zero: 0, nothing: undefined };
// Three ways to ask "is this key here?", with different answers.
console.log('zero' in counts, Object.hasOwn(counts, 'zero'), counts.zero !== undefined); // true true true
console.log('nothing' in counts, Object.hasOwn(counts, 'nothing'), counts.nothing !== undefined); // true true false
console.log('toString' in counts, Object.hasOwn(counts, 'toString')); // true false: in sees inherited keys
// Truthiness is the worst test: a stored 0 looks missing.
console.log(counts.zero ? 'present' : 'missing'); // missing
// Every plain object already "has" constructor, toString, valueOf...
const freq = {};
for (const w of ['constructor', 'a']) freq[w] = (freq[w] || 0) + 1;
console.log(typeof freq.constructor, freq.a); // string 1: the function Object got a '1' glued on
// Object.create(null) makes a dictionary with no inherited keys at all.
const dict = Object.create(null);
for (const w of ['constructor', 'a']) dict[w] = (dict[w] ?? 0) + 1;
console.log(dict.constructor, dict.a, 'toString' in dict); // 1 1 falseCopying objects
Spread { ...obj } and Object.assign({}, obj) are shallow: top-level fields are copied, but nested arrays, objects and Sets are still shared. structuredClone(obj) makes a full deep copy of plain data (arrays, objects, Maps, Sets, Dates). It throws on functions, and class instances come back as plain objects. Avoid JSON.parse(JSON.stringify(x)): it turns Maps and Sets into {}, Infinity into null, and drops undefined.
const original = { name: 'grid', size: [2, 3], tags: new Set(['a']) };
// Spread (and Object.assign) copy only the top level.
const shallow = { ...original };
shallow.name = 'copy'; // top-level property: independent
shallow.size.push(4); // nested array: SHARED with original
console.log(original.name, original.size); // grid [2, 3, 4]
// Later properties win, so "a copy with one change" is one line.
const resized = { ...original, size: [5, 5] };
console.log(resized.size, original.size); // [5, 5] [2, 3, 4]
// structuredClone copies every level, including arrays, Maps, Sets and Dates.
const deep = structuredClone(original);
deep.size.push(9);
deep.tags.add('b');
console.log(original.size, original.tags.size); // [2, 3, 4] 1
console.log(deep.size, deep.tags.size); // [2, 3, 4, 9] 2
// A JSON round trip is lossy: Sets become {}, Infinity becomes null, undefined disappears.
console.log(JSON.parse(JSON.stringify({ s: new Set([1]), best: Infinity, gone: undefined }))); // { s: {}, best: null }For counting, lookups by number, or any key that isn't a fixed field name, prefer a Map: it keeps key types, has an O(1) size, and inherits nothing. See Map and Set.
Used in: Hash Maps and Sets
Map and Set
The hash map and hash set of JavaScript: O(1) average lookups, counting, grouping and encoding composite keys.
Map and Set are JavaScript's hash map and hash set. Lookups, inserts and deletes cost O(1) on average, which is why "use a hash map" turns so many O(n²) brute forces into O(n). Reach for them whenever you ask "have I seen this before?", "how many times?", or "which group does this belong to?".
Map basics
const m = new Map(); // or new Map([[k1, v1], [k2, v2]])
m.set(key, value); // insert or overwrite, returns m
m.get(key); // value, or undefined if missing
m.has(key); // true / false
m.delete(key); // true if it was there
m.size; // number of entries (a property, not a method)
for (const [k, v] of m) {} // entries in insertion orderconst ages = new Map();
ages.set('ada', 36).set('alan', 41); // set returns the map, so calls chain
console.log(ages.get('ada')); // 36
console.log(ages.get('grace')); // undefined: missing keys are not an error
console.log(ages.has('alan'), ages.size); // true 2
ages.set('ada', 37); // same key: overwrites, size stays 2
ages.delete('alan');
console.log([...ages]); // [['ada', 37]]: entries in insertion order
// Any value can be a key, and keys keep their type (1 and '1' are different keys).
const m = new Map([[1, 'number one'], ['1', 'string one']]);
console.log(m.get(1), '|', m.get('1')); // number one | string one
for (const [name, age] of ages) console.log(name, age); // iterate entries directlyCounting and grouping with a Map
Three idioms cover most hash map problems: count occurrences, group items by a computed key, and remember something about values you've already passed (an index, a count, a prefix sum).
// Frequency count: the most common Map idiom in DSA problems.
function countChars(s) {
const freq = new Map();
for (const ch of s) freq.set(ch, (freq.get(ch) ?? 0) + 1);
return freq;
}
console.log(countChars('banana')); // Map(3) { 'b' => 1, 'a' => 3, 'n' => 2 }
// Group by a computed key: anagrams share the same sorted letters.
function groupAnagrams(words) {
const groups = new Map();
for (const w of words) {
const key = [...w].sort().join('');
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(w);
}
return [...groups.values()];
}
console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']));
// "Have I seen the complement before?" in one pass (Two Sum).
function twoSum(nums, target) {
const seen = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(nums[i], i);
}
return [];
}
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1](freq.get(ch) ?? 0) + 1 reads as "current count, or 0 if this is the first time". Use ?? rather than || when 0 is a meaningful stored value: 0 || fallback picks the fallback.
Map or plain object?
Map | {} object | |
|---|---|---|
| Key types | anything; 1 and '1' stay different | strings and symbols only: obj[1] is obj['1'] |
| Size | m.size, O(1) | Object.keys(o).length, O(n) |
| Order | insertion order | integer-like keys first, ascending, then insertion order |
| Accidental keys | none | inherits constructor, toString… unless you use Object.create(null) |
| Speed for frequent add/delete | built for it | fine for small, fixed shapes |
Default to Map for counting and lookups. A plain object is fine for fixed records like { count: 0, best: -Infinity }, and an array of 26 is fastest when keys are lowercase letters: counts[ch.charCodeAt(0) - 97]++.
Set basics
A Set stores unique values: perfect for "visited", "seen", and removing duplicates.
const seen = new Set([3, 1, 3, 2, 1]);
console.log(seen, seen.size); // Set(3) { 3, 1, 2 } 3: duplicates collapse
console.log(seen.has(2), seen.has(5)); // true false: O(1) average membership test
seen.add(5).add(5); // adding again does nothing
seen.delete(3);
console.log([...seen]); // [1, 2, 5]
// Deduplicate an array (keeps first-seen order).
console.log([...new Set(['b', 'a', 'b', 'c', 'a'])]); // ['b', 'a', 'c']
// Set algebra with plain loops (works in every engine).
const a = new Set([1, 2, 3, 4]);
const b = new Set([3, 4, 5]);
console.log([...a].filter((x) => b.has(x))); // intersection [3, 4]
console.log([...new Set([...a, ...b])]); // union [1, 2, 3, 4, 5]
console.log([...a].filter((x) => !b.has(x))); // difference [1, 2]Composite keys in a Map or Set
Keys are compared with SameValueZero: primitives by value, objects and arrays by reference. Two separate [0, 1] arrays are two different keys, so encode pairs and coordinates as strings or numbers.
// Arrays and objects are compared by reference, so they make useless keys:
const visited = new Set();
visited.add([0, 1]);
console.log(visited.has([0, 1])); // false: a different array object
// Encode the coordinates as a string (or a number) instead.
const key = (r, c) => `${r},${c}`;
visited.add(key(0, 1));
console.log(visited.has(key(0, 1))); // true
// For a grid with known width, a number key is faster than a string.
const cols = 1000;
const id = (r, c) => r * cols + c;
const seen = new Set([id(2, 7)]);
console.log(seen.has(id(2, 7)), id(2, 7)); // true 2007Map and Set costs
| Operation | Average cost |
|---|---|
set, get, has, delete, add | O(1) |
size | O(1) |
[...m], m.keys(), iterating | O(n) |
new Set(array) | O(n) |
Building a string key like `${r},${c}` | O(length of the key) |
"O(1) average" assumes good hashing, which the engine handles for you; worst cases don't come up in interview problems.
Used in: Hash Maps and SetsSliding WindowPrefix Sums and Difference ArraysTries (Prefix Trees)Graph BFS and DFSDynamic Programming I: 1DDesign Data Structures: LRU, LFU and Friends
Destructuring, spread and rest
Swap in one line, unpack pairs in loops, copy arrays shallowly and collect arguments.
Destructuring and spread turn swaps, pair unpacking and copies into one-liners, and they show up in almost every solution: [a, b] = [b, a], for (const [k, v] of map), [...arr]. Two facts keep them safe: every spread or rest is an O(n) copy, and every copy is only one level deep.
Array destructuring and swaps
Square brackets on the left of = unpack by position. You can skip positions, give defaults for missing ones, and collect the remainder with ...rest. The same syntax swaps two variables or two array slots without a temporary, which is the standard way to swap in two-pointer and partition code.
// Array destructuring unpacks by position.
const [first, second] = [10, 20, 30];
console.log(first, second); // 10 20
const [, , third] = [10, 20, 30]; // skip positions with empty slots
console.log(third); // 30
const [x = 0, y = 0] = [5]; // defaults fill missing positions
console.log(x, y); // 5 0
const [head, ...tail] = [1, 2, 3, 4]; // rest collects the remainder into a new array
console.log(head, tail); // 1 [2, 3, 4]
// Swap two variables, or two array slots, in one line.
let a = 1, b = 2;
[a, b] = [b, a];
console.log(a, b); // 2 1
const nums = [5, 6, 7];
[nums[0], nums[2]] = [nums[2], nums[0]];
console.log(nums); // [7, 6, 5]
// The semicolon pitfall: without a semicolon, a line starting with [ continues the
// previous line. These two lines run as const arr = [9, 8][a, b] = [b, a]
const arr = [9, 8]
[a, b] = [b, a]
console.log(arr, a, b); // [1, 2] 2 1: arr got the pair, and nothing was swappedThe last lines show the one real pitfall. JavaScript inserts semicolons only where a line can't continue, and a line starting with [ can continue the previous expression. If the line before a swap has no semicolon, the swap is parsed as an index into it. Either end statements with semicolons or start the swap line with one: ;[a, b] = [b, a].
Object destructuring
Curly braces unpack by name. Rename with key: newName, default with key = value, and nest to reach inner fields. It's especially handy in function parameters for options and records.
const { start, end } = interval; // two fields at once
const { val: v, left, right } = node; // rename val to v
const { k = 1 } = options; // default when options.k is undefined
const { left: { val: leftVal } } = node; // nested (throws if node.left is null)
function dist({ r, c }, { r: r2, c: c2 }) { // destructure parameters
return Math.abs(r - r2) + Math.abs(c - c2);
}
const { a, ...others } = obj; // others: a shallow copy without aDestructuring null or undefined throws a TypeError, so guard nodes that may be missing (if (!node) return 0;) before unpacking them.
Destructuring in loops and callbacks
Anything that yields pairs or tuples can be unpacked right in the loop head or the callback parameter: Map entries, Object.entries(obj), arr.entries(), edge lists, intervals and BFS queue items.
for (const [key, count] of map) {} // Map entries
for (const [key, value] of Object.entries(obj)) {} // keys are strings
for (const [i, x] of arr.entries()) {} // index and value
for (const [u, v, w] of edges) {} // weighted edge list
intervals.sort(([s1], [s2]) => s1 - s2); // in a comparator
const [r, c] = queue[head++]; // BFS state// Maps, Object.entries and arr.entries() all yield [key, value] pairs: unpack them in the loop head.
const freq = new Map([['a', 3], ['b', 1], ['c', 2]]);
const parts = [];
for (const [ch, n] of freq) parts.push(`${ch}=${n}`);
console.log(parts.join(' ')); // a=3 b=1 c=2
for (const [i, x] of [7, 3, 9].entries()) {
if (x === 9) console.log('9 is at index', i); // 9 is at index 2
}
// Edge lists: [from, to, weight] triples straight into an adjacency list.
const edges = [[0, 1, 4], [0, 2, 1], [2, 1, 2]];
const adj = Array.from({ length: 3 }, () => []);
for (const [u, v, w] of edges) adj[u].push([v, w]);
console.log(adj); // [[[1, 4], [2, 1]], [], [[1, 2]]]
// Callbacks can destructure their parameter too.
const intervals = [[1, 3], [2, 6], [8, 10]];
console.log(intervals.map(([start, end]) => end - start)); // [2, 4, 2]
// BFS: a queue of [row, col, dist] tuples.
const queue = [[0, 0, 0], [0, 1, 1]];
let qHead = 0;
const [r, c, d] = queue[qHead++];
console.log(r, c, d); // 0 0 0
// Object destructuring: by name, with renaming, nesting and defaults.
const node = { val: 5, left: { val: 3 }, right: null };
const { val, left: { val: leftVal }, right } = node;
console.log(val, leftVal, right); // 5 3 null
function area({ w, h = 1 }) {
return w * h;
}
console.log(area({ w: 4, h: 2 }), area({ w: 4 })); // 8 4Spread for copies and concatenation
... inside an array literal spreads any iterable: arrays, strings (into characters), Sets, Maps, map.keys(). Inside an object literal it copies own properties, and later keys override earlier ones. Inside a call, f(...arr) passes the elements as separate arguments. Every spread is shallow: nested arrays and objects are shared, not copied.
const a = [1, 2];
const b = [3, 4];
console.log([...a, ...b], [0, ...a, 9]); // [1, 2, 3, 4] [0, 1, 2, 9]
const copy = [...a];
copy.push(99);
console.log(a, copy); // [1, 2] [1, 2, 99]
// Spread works on any iterable: strings, Sets, Maps and their keys().
console.log([...'abc'], [...new Set([2, 2, 1])]); // ['a', 'b', 'c'] [2, 1]
const m = new Map([['x', 1], ['y', 2]]);
console.log([...m], [...m.keys()]); // [['x', 1], ['y', 2]] ['x', 'y']
// Objects: later keys win, so "copy with changes" is one expression.
const state = { r: 0, c: 0, steps: 0 };
const moved = { ...state, c: 1, steps: state.steps + 1 };
console.log(moved, state.steps); // { r: 0, c: 1, steps: 1 } 0
// Shallow: the inner arrays are shared between the copy and the original.
const grid = [[1, 2], [3, 4]];
const outerCopy = [...grid];
outerCopy[0][0] = 'X';
console.log(grid[0]); // ['X', 2]
// Rest parameters collect any number of arguments into a real array.
function maxOf(first, ...rest) {
let best = first;
for (const x of rest) if (x > best) best = x;
return best;
}
console.log(maxOf(3, 9, 4), maxOf(7)); // 9 7
const args = [5, 1, 8];
console.log(maxOf(...args), Math.max(...args)); // 8 8: spread an array into separate arguments| Expression | Cost |
|---|---|
const [a, b] = pair, [a, b] = [b, a] | O(1) |
[...arr], [...a, ...b], [...str] | O(n) |
const [head, ...tail] = arr | O(n): tail is a new array |
{ ...obj } | O(number of keys) |
f(...arr), Math.max(...arr) | O(n), and limited by the engine's maximum argument count |
Spreading inside a loop (path = [...path, x] at every step) turns an O(n) loop into O(n²). Push and pop on one array instead, and copy only when you save a result.
Rest parameters and rest elements
...name on the receiving side collects whatever is left into a real array (or object). It must come last.
function sum(...nums) { // sum(1, 2, 3): nums is [1, 2, 3]
return nums.reduce((a, b) => a + b, 0);
}
function maxOf(first, ...rest) {} // at least one argument, the rest in an array
const [first, ...others] = arr; // array rest: a copy of arr without its first item
const { id, ...fields } = record; // object rest: every key except idPrefer rest parameters to the old arguments object, which isn't a real array and doesn't exist in arrow functions.
Used in: Two PointersIntervals and Sweep LineIn-place Linked List ManipulationBacktrackingMatrix and Grid Simulation
Functions, arrow functions and closures
Declarations vs arrows, default parameters, closures that hold state, and nested helpers for DFS.
Most solutions are one main function plus a helper or two. Knowing how JavaScript functions capture variables lets you write a recursive DFS helper that updates an outer best without threading it through every call, and pass comparators and predicates into sorts, heaps and binary searches.
Declarations, expressions and arrows
All three create ordinary function values. The differences that matter in DSA code are hoisting and the arrow return rules. Arrows also have no this of their own, which you only care about inside class methods (see Classes for data structures); for standalone helpers, this never comes up.
function add(a, b) { return a + b; } // declaration: hoisted, callable anywhere in its scope
const mul = function (a, b) { return a * b; }; // expression: usable only after this line
const sq = (x) => x * x; // arrow, no braces: the expression is returned
const sum = (a, b) => { return a + b; }; // arrow with braces: needs an explicit return
const pair = (a, b) => ({ a, b }); // object literal: wrap it in parentheses// A declaration is hoisted: you can call it above the line that defines it.
console.log(square(4)); // 16
function square(x) {
return x * x;
}
// A const function (expression or arrow) exists only after its line runs.
try {
cube(2);
} catch (e) {
console.log(e.name); // ReferenceError: cube is not ready yet
}
const cube = (x) => x * x * x;
console.log(cube(2)); // 8
// Arrow bodies: no braces returns the expression; braces need an explicit return.
const double = (x) => x * 2;
const doubleBroken = (x) => { x * 2; };
const doubleFixed = (x) => { return x * 2; };
console.log(double(5), doubleBroken(5), doubleFixed(5)); // 10 undefined 10
// Returning an object literal from a concise arrow needs parentheses.
const asPair = (a, b) => ({ a, b });
console.log(asPair(1, 2)); // { a: 1, b: 2 }Use whichever style you like for the main function, but be consistent: declarations let you put helpers at the bottom of the file, while const arrows must be defined before the line that first calls them runs.
Default and rest parameters
A default kicks in when the argument is missing or undefined. It is evaluated on every call and can refer to earlier parameters, so function dfs(node, depth = 0) and function solve(nums, lo = 0, hi = nums.length - 1) are idiomatic. Rest parameters (...rest) collect extra arguments into a real array.
// Defaults apply when the argument is missing or undefined (not when it is null).
function greet(name = 'friend') {
return `hi ${name}`;
}
console.log(greet(), greet(undefined), greet(null)); // hi friend hi friend hi null
// A default can use earlier parameters: handy for recursive helpers.
function sumRange(nums, lo = 0, hi = nums.length - 1) {
if (lo > hi) return 0;
return nums[lo] + sumRange(nums, lo + 1, hi);
}
console.log(sumRange([1, 2, 3, 4]), sumRange([1, 2, 3, 4], 2)); // 10 7
// Default values are created fresh on every call, so a default [] or Map is never shared.
function collect(x, into = []) {
into.push(x);
return into;
}
console.log(collect(1), collect(2)); // [1] [2]
// Rest parameters gather the remaining arguments into a real array.
function maxOf(first, ...rest) {
let best = first;
for (const x of rest) if (x > best) best = x;
return best;
}
console.log(maxOf(3, 9, 4), maxOf(7)); // 9 7Coming from Python: a default [] or new Map() is not shared between calls in JavaScript. Each call that omits the argument gets a fresh one.
Closures that hold state
A function keeps access to the variables that were in scope where it was created, even after the outer function has returned. That gives you private state without a class: counters, id generators and memo .
// A closure keeps the variables of the scope it was created in alive.
function makeCounter() {
let count = 0; // private: only the returned function can see it
return () => ++count;
}
const next = makeCounter();
const other = makeCounter(); // a second, independent count
console.log(next(), next(), next(), other()); // 1 2 3 1
// A memo cache held in a closure: wrap any one-argument function.
function memoize(fn) {
const cache = new Map();
return (x) => {
if (!cache.has(x)) cache.set(x, fn(x));
return cache.get(x);
};
}
let calls = 0;
const slowSquare = (x) => {
calls++;
return x * x;
};
const fastSquare = memoize(slowSquare);
console.log(fastSquare(9), fastSquare(9), fastSquare(9), 'calls:', calls); // 81 81 81 calls: 1
// let gives each loop iteration its own binding; var shares one variable.
const withLet = [];
for (let i = 0; i < 3; i++) withLet.push(() => i);
const withVar = [];
for (var j = 0; j < 3; j++) withVar.push(() => j);
console.log(withLet.map((f) => f()), withVar.map((f) => f())); // [0, 1, 2] [3, 3, 3]Each call to makeCounter() creates a new count, so two counters never interfere. The last example is the classic var trap: var is function-scoped, so every closure sees the same j, which is 3 when they finally run.
Nested helper functions: the DFS idiom
Define the recursive helper inside the main function. It can read the input and read or write the accumulators (best, result, visited, path) through the closure, so its own parameters are only the things that change per call, like the current node or index.
// TreeNode is provided in the editor (see "Linked list and tree nodes").
// The helper returns one thing (a height) and updates another (best) through the closure.
function diameter(root) {
let best = 0; // longest path seen so far, in edges
function height(node) {
if (!node) return 0;
const left = height(node.left);
const right = height(node.right);
best = Math.max(best, left + right); // path that bends at this node
return 1 + Math.max(left, right);
}
height(root);
return best;
}
const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log(diameter(root)); // 3: 4 -> 2 -> 1 -> 3
// Backtracking: the helper shares `path` and `result` instead of passing them around.
function subsets(nums) {
const result = [];
const path = [];
function choose(i) {
if (i === nums.length) {
result.push([...path]); // push a copy: path keeps changing
return;
}
path.push(nums[i]); // take nums[i]
choose(i + 1);
path.pop(); // undo, then skip nums[i]
choose(i + 1);
}
choose(0);
return result;
}
console.log(subsets([1, 2, 3])); // [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]Two rules keep this idiom correct. Declare the accumulator with let (or as an array or Map) outside the helper, and assign to it rather than to a parameter: reassigning a parameter only changes the helper's local copy. When you store a mutable path in the result, push a copy ([...path]), or every entry ends up pointing at the same emptied array.
Returning multiple values
A function returns one value, so return an array or an object and destructure it at the call site. Arrays are shorter for fixed-position tuples; objects are self-describing when there are three or more fields.
function minMax(nums) {
let lo = Infinity, hi = -Infinity;
for (const x of nums) { lo = Math.min(lo, x); hi = Math.max(hi, x); }
return [lo, hi];
}
const [lo, hi] = minMax([4, 1, 7]); // lo = 1, hi = 7
// Tree DP often returns two answers per node: with and without this node.
function rob(node) {
if (!node) return [0, 0]; // [best if robbed, best if skipped]
const [lRob, lSkip] = rob(node.left);
const [rRob, rSkip] = rob(node.right);
return [node.val + lSkip + rSkip, Math.max(lRob, lSkip) + Math.max(rRob, rSkip)];
}
function balance(node) { // object: named fields read better
if (!node) return { height: 0, ok: true };
const l = balance(node.left), r = balance(node.right);
const ok = l.ok && r.ok && Math.abs(l.height - r.height) <= 1;
return { height: 1 + Math.max(l.height, r.height), ok };
}
const { ok } = balance(root);Passing comparators and callbacks
Functions are values, so a generic routine can take the problem-specific part as an argument: a comparator for sort or a heap, a predicate for a binary search on the answer, a key function for grouping. A comparator returns a negative number when a should come first, positive when b should, and 0 for a tie (more in Sorting and comparators).
// Functions are values: pass them in to customise what a generic helper does.
function countIf(items, test) {
let n = 0;
for (const x of items) if (test(x)) n++;
return n;
}
console.log(countIf([3, 8, 1, 10], (x) => x > 2)); // 3
// A function that builds a comparator: sort people by one computed key.
const byKey = (key) => (a, b) => key(a) - key(b);
const people = [{ name: 'Ann', age: 31 }, { name: 'Bo', age: 25 }, { name: 'Cy', age: 28 }];
people.sort(byKey((p) => p.age));
console.log(people.map((p) => p.name)); // ['Bo', 'Cy', 'Ann']
// Binary search on the answer: the predicate is the only problem-specific part.
function firstTrue(lo, hi, ok) { // smallest x in [lo, hi] with ok(x) true
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (ok(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
console.log(firstTrue(0, 100, (x) => x * x >= 50)); // 8: the smallest x with x² >= 50
// Passing a method directly loses its object; wrap it in an arrow.
const seen = new Set();
try {
[1, 2].forEach(seen.add);
} catch (e) {
console.log(e.name); // TypeError: add was called without its Set
}
[1, 2].forEach((x) => seen.add(x));
console.log(seen); // Set(2) { 1, 2 }Methods are the exception: seen.add on its own forgets which Set it belongs to, so pass (x) => seen.add(x) instead.
Used in: Tree Depth-First Search
Recursion, the call stack and memoization
Base cases, how deep JavaScript can recurse, memoizing with a Map, and turning recursion into a loop.
Trees, backtracking, divide and conquer and top-down dynamic programming are all recursion. JavaScript handles it well up to a few thousand levels, so you need to know where the stack limit is, how to memoize, and how to switch to a loop when the input is deep.
Base case and recursive case
Every recursive function has the same two parts: a base case that answers the smallest input directly, and a recursive case that calls itself on a strictly smaller input and combines the result. Trust the recursive call to be correct for the smaller input; your job is only the combine step.
function solve(input) {
if (isSmallest(input)) return directAnswer(input); // base case(s) first
const sub = solve(smallerPart(input)); // must make progress
return combine(input, sub);
}// Fast power: the base case stops the recursion, and every call halves n.
function power(x, n, depth = 0) {
console.log(`${' '.repeat(depth)}power(${x}, ${n})`); // indentation = stack depth
if (n === 0) return 1; // base case
const half = power(x, Math.floor(n / 2), depth + 1); // smaller subproblem
return n % 2 === 0 ? half * half : half * half * x; // combine on the way back
}
console.log(power(2, 10));
// power(2, 10)
// power(2, 5)
// power(2, 2)
// power(2, 1)
// power(2, 0)
// 1024: only 5 frames deep, O(log n)
// Recursion on lists and trees follows the shape of the data.
// ListNode and TreeNode are provided in the editor.
const listLength = (node) => (node === null ? 0 : 1 + listLength(node.next));
const maxDepth = (node) => (node === null ? 0 : 1 + Math.max(maxDepth(node.left), maxDepth(node.right)));
const list = new ListNode(1, new ListNode(2, new ListNode(3)));
const tree = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3));
console.log(listLength(list), maxDepth(tree)); // 3 3The indentation shows the call stack: each call waits for the one below it, and the answers flow back up in reverse order. For trees and lists the base case is almost always node === null.
Recursion depth limits
Every pending call holds a stack frame. The engine's stack is small (about 1 MB in V8), which works out to roughly 10,000 frames for a tiny function and fewer when each frame has more parameters and locals. The exact number varies by engine and changes between versions, so treat anything above a few thousand levels as unsafe. Going over throws a catchable RangeError: Maximum call stack size exceeded.
// How deep can this engine recurse? Recurse until the stack overflows, then report.
function probe(depth) {
try {
return probe(depth + 1);
} catch {
return depth;
}
}
console.log('max depth here:', probe(0)); // around 10000 (Node 24: ~9000), varies by engine
// What the overflow looks like: a RangeError you can catch, not a crash.
const countDown = (n) => (n === 0 ? 0 : countDown(n - 1));
try {
countDown(1e6);
} catch (e) {
console.log(e instanceof RangeError, e.message); // true Maximum call stack size exceeded
}
console.log(countDown(1000)); // 0: a depth of 1000 is fine everywhere
// Tail position does not help: only Safari implements tail-call optimisation.
function sumTo(n, acc = 0) {
if (n === 0) return acc;
return sumTo(n - 1, acc + n); // a tail call, still a new frame in V8 and Firefox
}
try {
console.log(sumTo(1e6));
} catch (e) {
console.log(e.name); // RangeError (Safari prints 500000500000)
}What this means in practice:
- Recursion over a balanced tree is always fine: depth is O(log n).
- Recursion over a linked list, a skewed tree, or a path through a big grid can be as deep as n. If n can reach 10^4 or more, use a loop or an explicit stack.
- You can't raise the limit in a browser or a judge (
node --stack-sizeexists, but you rarely control the flags).
Tail calls are not optimised in practice. ES2015 specified proper tail calls, but only Safari ships them. V8 (Chrome, Node) and Firefox still push a new frame for return f(n - 1, acc), so rewriting into tail form does not save you. A tail-recursive function converts mechanically into a while loop: the parameters become loop variables.
function sumTo(n, acc = 0) { // tail call, but still one frame per level in V8
if (n === 0) return acc;
return sumTo(n - 1, acc + n);
}
function sumToLoop(n, acc = 0) { // the same steps with O(1) stack
while (n !== 0) {
acc += n;
n -= 1;
}
return acc;
}Memoization with a Map or an array
When the same arguments come up again and again (overlapping subproblems), each answer the first time you compute it. That is top-down dynamic programming, and it turns exponential recursions into polynomial ones.
// Plain recursion recomputes the same subproblems again and again.
let calls = 0;
function fib(n) {
calls++;
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
console.log(fib(25), 'calls:', calls); // 75025 calls: 242785
// Memo in a Map: each n is computed once.
calls = 0;
function fibMemo(n, memo = new Map()) {
calls++;
if (n < 2) return n;
if (memo.has(n)) return memo.get(n);
const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, result);
return result;
}
console.log(fibMemo(25), 'calls:', calls); // 75025 calls: 49
// Two-dimensional state: an array of arrays (or a Map with key `${r},${c}`).
function gridPaths(rows, cols) {
const memo = Array.from({ length: rows }, () => new Array(cols).fill(-1)); // -1 = not computed
function paths(r, c) {
if (r === rows - 1 || c === cols - 1) return 1;
if (memo[r][c] !== -1) return memo[r][c];
return (memo[r][c] = paths(r + 1, c) + paths(r, c + 1));
}
return paths(0, 0);
}
console.log(gridPaths(3, 7), gridPaths(16, 16)); // 28 155117520Pick the cache by the shape of the state:
| State | Cache | Check |
|---|---|---|
One small integer i | new Array(n + 1).fill(-1) | memo[i] !== -1 |
Two integers (i, j) | 2D array via Array.from | memo[i][j] !== -1 |
| Large, sparse or non-numeric | new Map() with key `${i},${j}` or i * W + j | memo.has(key) |
Use a sentinel that can never be a real answer (-1 for counts, undefined for anything). Never test if (memo[i]): a stored answer of 0 is falsy and gets recomputed every time.
Recursion to iteration with an explicit stack
Any recursion can be run with your own array as the stack, which lives on the heap and can hold millions of entries. For DFS, push the start node, then loop: pop a node, process it, push its children. Push them in reverse of the order you want to visit them, since the last one pushed is popped first.
// ListNode and TreeNode are provided in the editor.
// A 100,000-node linked list: far deeper than the call stack allows.
let head = null;
for (let i = 0; i < 100000; i++) head = new ListNode(i, head);
const lengthRec = (node) => (node ? 1 + lengthRec(node.next) : 0);
try {
lengthRec(head);
} catch (e) {
console.log('recursive:', e.name); // recursive: RangeError
}
function lengthLoop(node) {
let n = 0;
for (; node; node = node.next) n++;
return n;
}
console.log('loop:', lengthLoop(head)); // loop: 100000
// Tree DFS with an explicit stack: same pre-order as the recursive version.
const tree = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
function preorderRec(node, out = []) {
if (!node) return out;
out.push(node.val);
preorderRec(node.left, out);
preorderRec(node.right, out);
return out;
}
function preorderStack(root) {
const out = [];
const stack = root ? [root] : [];
while (stack.length) {
const node = stack.pop();
out.push(node.val);
if (node.right) stack.push(node.right); // push right first so left is popped first
if (node.left) stack.push(node.left);
}
return out;
}
console.log(preorderRec(tree), preorderStack(tree)); // [1, 2, 4, 5, 3] [1, 2, 4, 5, 3]Simple recursions on lists ("do something with this node, then recurse on next") don't even need a stack: they are a plain loop. Keep the recursive version when depth is bounded (balanced trees, backtracking over n ≤ 20 choices); it is shorter and easier to get right.
Passing indices instead of slicing
arr.slice(1) copies the rest of the array, so recursing on slices costs O(n) per call and O(n²) overall, in both time and memory. Pass the whole array plus indices (i, or lo and hi) instead. The same goes for strings: engines can sometimes share memory for s.slice(1), but indices are O(1) in every engine and make the cost obvious.
// Slicing a fresh array on every call copies O(n) elements per level: O(n²) in total.
let copied = 0;
function sumSlice(nums) {
if (nums.length === 0) return 0;
const rest = nums.slice(1);
copied += rest.length;
return nums[0] + sumSlice(rest);
}
// Passing an index shares one array: O(1) extra work per call.
function sumFrom(nums, i = 0) {
if (i === nums.length) return 0;
return nums[i] + sumFrom(nums, i + 1);
}
const nums = Array.from({ length: 2000 }, (_, i) => i + 1);
console.log(sumSlice(nums), 'elements copied:', copied); // 2001000 elements copied: 1999000
console.log(sumFrom(nums)); // 2001000, nothing copied
// Same idea with two indices: check a palindrome from both ends inward.
function isPal(s, lo = 0, hi = s.length - 1) {
if (lo >= hi) return true;
return s[lo] === s[hi] && isPal(s, lo + 1, hi - 1);
}
console.log(isPal('racecar'), isPal('rocket')); // true falseRecursion costs
| Approach | Time | Extra space |
|---|---|---|
| Plain recursion | number of calls × work per call | O(max depth) stack |
| Two branches per call, depth n (naive Fibonacci, subsets) | O(2^n) | O(n) |
| Memoized | number of distinct states × work per state | states + O(depth) |
| Slicing the input each call | adds O(n) per call: often O(n²) total | O(n²) copied |
| Explicit stack | same as the recursion | O(max stack size), on the heap |
Used in: Tree Depth-First SearchBacktrackingDynamic Programming I: 1DDynamic Programming II: Grids, Strings and Knapsack
Classes for data structures
class syntax, constructors, methods, getters and private fields for Trie, UnionFind and friends.
Design problems (Min Stack, , Trie) ask you to write a class, and union-find, tries and heaps are cleanest as one. You need only a small slice of the class syntax: a constructor, methods, maybe a getter or a private field.
Class syntax essentials
class Name {
field = 0; // public field: set on every new instance
#secret = []; // private field: only code inside the class can read it
constructor(a, b) { // runs on `new Name(a, b)`
this.a = a; // instance data always goes through `this`
}
method(x) { return this.a + x; } // shared by all instances
get size() { return this.#secret.length; } // read as obj.size, without ()
static of(a) { return new Name(a, 0); } // called as Name.of(a)
}
const obj = new Name(1, 2); // `new` is required: Name(1, 2) throws TypeErrorclass Interval {
constructor(start, end) { // runs on `new`: set up the fields
this.start = start;
this.end = end;
}
get length() { // getter: read as iv.length, no parentheses
return this.end - this.start;
}
overlaps(other) { // method: shared by every instance
return this.start <= other.end && other.start <= this.end;
}
static fromPair([start, end]) { // static: called on the class, not an instance
return new Interval(start, end);
}
}
const a = new Interval(1, 5);
const b = Interval.fromPair([4, 9]);
console.log(a.length, a.overlaps(b), b); // 4 true Interval { start: 4, end: 9 }
// Private #fields can only be touched inside the class body.
class Stack {
#items = []; // a field: every instance gets its own array
push(x) {
this.#items.push(x);
return this; // returning this lets calls chain
}
pop() {
return this.#items.pop();
}
peek() {
return this.#items.at(-1);
}
get size() {
return this.#items.length;
}
}
const s = new Stack().push(1).push(2).push(3);
console.log(s.pop(), s.peek(), s.size); // 3 2 2
console.log(Object.keys(s)); // []: private fields are invisible from outside
// Forgetting `new` is a TypeError, not a silent bug.
try {
Stack();
} catch (e) {
console.log(e.name); // TypeError
}Class bodies always run in strict mode, so a missing this. fails loudly: items.push(x) instead of this.items.push(x) throws ReferenceError, and so does count = 0, which outside strict mode would quietly create a global. Class declarations are not hoisted like functions: define the class above the code that uses it.
Union-Find as a class
Union-find (disjoint set union) keeps a parent array where each group is a tree and its root is the group's representative. Two tricks keep the trees flat: path halving in find (point each visited node at its grandparent) and union by size (hang the smaller tree under the larger one).
class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i); // everyone is their own root
this.size = new Array(n).fill(1);
this.count = n; // number of separate groups
}
find(x) {
while (this.parent[x] !== x) {
this.parent[x] = this.parent[this.parent[x]]; // path halving: flatten as we climb
x = this.parent[x];
}
return x;
}
union(a, b) {
let ra = this.find(a);
let rb = this.find(b);
if (ra === rb) return false; // already connected: this edge closes a cycle
if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
this.parent[rb] = ra; // hang the smaller tree under the larger
this.size[ra] += this.size[rb];
this.count--;
return true;
}
connected(a, b) {
return this.find(a) === this.find(b);
}
}
const uf = new UnionFind(6);
console.log(uf.union(0, 1), uf.union(1, 2), uf.union(3, 4)); // true true true
console.log(uf.union(0, 2)); // false: 0 and 2 were already joined
console.log(uf.connected(0, 2), uf.connected(2, 3), uf.count); // true false 3union returning false when both items already share a root is exactly the "does this edge create a cycle?" test. Use it in Union-Find problems and Kruskal's algorithm.
Trie skeleton
A trie is a tree of nodes, one per character of a prefix. Each node holds its children (a Map from character to node, or an object, or an array of 26) and a flag for "a word ends here". A private #walk helper does the shared work of search and startsWith.
class TrieNode {
constructor() {
this.children = new Map(); // char -> TrieNode
this.isWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
node = node.children.get(ch);
}
node.isWord = true;
}
#walk(prefix) { // private helper: last node of prefix, or null
let node = this.root;
for (const ch of prefix) {
node = node.children.get(ch);
if (!node) return null;
}
return node;
}
search(word) {
return this.#walk(word)?.isWord === true;
}
startsWith(prefix) {
return this.#walk(prefix) !== null;
}
}
const trie = new Trie();
for (const w of ['car', 'card', 'care', 'dog']) trie.insert(w);
console.log(trie.search('car'), trie.search('ca'), trie.startsWith('ca')); // true false true
console.log(trie.search('cards'), trie.startsWith('do')); // false trueA Map per node is the easy default. An array of 26 indexed by ch.charCodeAt(0) - 97 is faster when the alphabet is fixed lowercase letters, at the cost of 26 slots per node.
Design-problem classes
A design problem gives you a class name and method signatures. The judge creates one instance with the constructor arguments, then calls the methods in order and compares each return value; methods that return nothing are recorded as null. Keep every bit of state on this: anything at the top level of your file is shared by every test and every instance.
// A design problem: every operation in O(1), including getMin.
class MinStack {
constructor() {
this.items = [];
this.mins = []; // mins.at(-1) is the minimum of everything in items
}
push(x) {
this.items.push(x);
this.mins.push(this.mins.length ? Math.min(x, this.mins.at(-1)) : x);
}
pop() {
this.mins.pop();
return this.items.pop();
}
top() {
return this.items.at(-1);
}
getMin() {
return this.mins.at(-1);
}
}
// How a judge drives a design problem: construct once, then call each method in order.
const ops = ['MinStack', 'push', 'push', 'push', 'getMin', 'pop', 'top', 'getMin'];
const args = [[], [5], [2], [8], [], [], [], []];
const obj = new MinStack(...args[0]);
const outputs = [null];
for (let i = 1; i < ops.length; i++) outputs.push(obj[ops[i]](...args[i]) ?? null);
console.log(outputs); // [null, null, null, null, 2, 8, 2, 2]The usual trick in these problems is to store a little extra state so every operation stays O(1): here a second stack of running minimums. LRU Cache pairs a Map (which remembers insertion order) with deleting and re-inserting a key on each access.
Costs of the class-based structures
| Structure | Operation | Cost |
|---|---|---|
| Union-find with path halving + union by size | find, union, connected | amortized O(α(n)), effectively O(1) |
| Union-find without either trick | find | O(n) worst case: a long chain |
| Trie | insert, search, startsWith | O(L) for a word of length L |
| Trie | memory | O(total characters inserted) nodes |
| Min stack | push, pop, top, getMin | O(1) |
Class, closure or plain object?
| Use | When |
|---|---|
class | several operations on shared state (data structures, design problems), many instances |
Closure (function make() { let state; return { … } }) | one-off private state, such as a counter or memoized helper |
Plain object { start, end } | a record with no behaviour, such as an interval or a node created on the fly |
Tuple array [start, end] | records you sort or destructure a lot; the most compact |
For records, tuples and object literals are usually enough: intervals.sort((a, b) => a[0] - b[0]) reads fine. Reach for a class when the same operations repeat on the same data.
Used in: Tries (Prefix Trees)Heaps: Top-K, K-way Merge and Two HeapsUnion-Find (Disjoint Set Union)Design Data Structures: LRU, LFU and Friends
Iteration protocols and generators
What for...of really iterates, entries() and keys(), and generators for lazy traversals.
for...of, spread and Array.from all speak one protocol, the iterable, so the same loop walks arrays, strings, Maps and Sets. Generators let you write your own iterables, which turns tree walks and ranges into lazy streams you can stop after the k-th value.
What for...of iterates
| Value | for (const x of value) gives |
|---|---|
| Array | the elements, in index order |
| String | characters (by code point, so an emoji counts as one) |
Map | [key, value] pairs in insertion order |
Set | the items in insertion order |
arguments, typed arrays, generator objects | their values |
Plain object {} | nothing: TypeError: … is not iterable |
// for...of works on anything iterable and gives you values.
for (const x of [10, 20]) console.log('array', x); // array 10, array 20
for (const ch of 'hi') console.log('string', ch); // string h, string i
for (const [k, v] of new Map([['a', 1]])) console.log('map', k, v); // map a 1
for (const x of new Set(['s'])) console.log('set', x); // set s
// Need the index too? Iterate entries() and destructure.
for (const [i, x] of ['a', 'b'].entries()) console.log(i, x); // 0 a, 1 b
// Map has keys(), values() and entries(); Set's values() are its items.
const freq = new Map([['x', 3], ['y', 1]]);
console.log([...freq.keys()], [...freq.values()]); // ['x', 'y'] [3, 1]
// These return one-shot iterators, not arrays.
const keys = freq.keys();
console.log(keys.length, [...keys], [...keys]); // undefined ['x', 'y'] []
// Plain objects are not iterable: go through Object.entries (or keys / values).
const counts = { a: 2, b: 5 };
try {
for (const x of counts) console.log(x);
} catch (e) {
console.log(e.name); // TypeError: counts is not iterable
}
for (const [k, v] of Object.entries(counts)) console.log(k, v); // a 2, b 5entries(), keys() and values(). Arrays, Maps and Sets all have the three methods. arr.entries() is how you get the index inside a for...of; on a Map, entries() is what plain for...of already uses.
for (const [i, x] of arr.entries()) {} // index and value
for (const k of map.keys()) {} // just the keys
const total = [...map.values()].reduce((a, b) => a + b, 0);
const firstKey = map.keys().next().value; // oldest key: what an LRU cache evictsThey return iterators, not arrays: no length, no [0], and they can be read only once. Spread them ([...m.keys()]) when you need an array. Recent engines (Node 22+ and current browsers) also have iterator helpers such as m.keys().map(f).toArray(), but spreading works everywhere.
Spreading iterables and Array.from
[...iterable] copies any iterable into a new array, and f(...iterable) passes its items as arguments. Array.from(iterable, mapFn) converts and maps in one pass, and also accepts an array-like { length: n }, which is the standard way to build ranges and 2D grids with independent rows.
// Spread drains any iterable into an array (or into function arguments).
const set = new Set([3, 1, 3, 2]);
console.log([...set], Math.max(...set)); // [3, 1, 2] 3
console.log([...'abc'], [...new Map([[1, 'one']])]); // ['a', 'b', 'c'] [[1, 'one']]
// Array.from(iterable, mapFn) converts and transforms in one pass.
const freq = new Map([['a', 2], ['b', 5]]);
console.log(Array.from(freq, ([ch, n]) => ch.repeat(n))); // ['aa', 'bbbbb']
// It also accepts { length: n }, which is how you build ranges and grids.
console.log(Array.from({ length: 5 }, (_, i) => i * i)); // [0, 1, 4, 9, 16]
const grid = Array.from({ length: 2 }, () => new Array(3).fill(0));
grid[0][0] = 1;
console.log(grid); // [[1, 0, 0], [0, 0, 0]]: rows are separate
// Objects and Maps convert both ways.
const asMap = new Map(Object.entries({ x: 1, y: 2 }));
console.log(asMap.get('y'), Object.fromEntries(asMap)); // 2 { x: 1, y: 2 }Each of these is O(n): fine once, a trap inside a loop. Math.max(...big) also passes every item as a separate argument, which throws RangeError for arrays with more than roughly 100,000 items; loop instead.
Generator functions for lazy traversals
A function* returns a generator. Each yield hands one value to the and pauses until the next value is requested, so nothing is computed ahead of time. yield* forwards everything another generator yields, which makes recursive walks read like the textbook definition.
// A generator function (function*) pauses at each yield and resumes on the next request.
function* range(start, end, step = 1) {
for (let i = start; i < end; i += step) yield i;
}
console.log([...range(0, 10, 3)]); // [0, 3, 6, 9]
const it = range(0, 2);
console.log(it.next(), it.next(), it.next()); // { value: 0, done: false } { value: 1, done: false } { value: undefined, done: true }
// Lazy in-order walk of a BST: values come out sorted, one at a time.
// TreeNode is provided in the editor.
function* inorder(node) {
if (!node) return;
yield* inorder(node.left); // yield* forwards every value of another generator
yield node.val;
yield* inorder(node.right);
}
const bst = new TreeNode(5, new TreeNode(3, new TreeNode(2), new TreeNode(4)), new TreeNode(8, null, new TreeNode(9)));
console.log([...inorder(bst)]); // [2, 3, 4, 5, 8, 9]
// Early exit: stop after k values and the rest of the tree is never visited.
function kthSmallest(root, k) {
for (const val of inorder(root)) {
if (--k === 0) return val;
}
return null;
}
console.log(kthSmallest(bst, 3)); // 4
// Breaking out of for...of closes the generator, so its finally block runs.
function* noisy() {
try {
yield 1;
yield 2;
} finally {
console.log('cleanup');
}
}
for (const x of noisy()) {
console.log('got', x); // got 1
break; // prints cleanup right away
}Generators shine when you might stop early (k-th smallest, first match, merging two sorted streams) or when the sequence is huge or infinite. Recursive generators are still recursion: each value is passed up through every nested level (O(depth) per value), and nesting a few thousand deep overflows the stack. For skewed trees, write the walk with an explicit stack inside a single generator.
Breaking out of for...of early
break, return and throw inside a for...of stop the loop immediately and close the iterator: a generator's finally block runs, and no further values are produced. forEach can't do this: return inside its callback only skips to the next element, and break is a syntax error. When you need an early exit, use for...of, a classic for, or some/find.
for (const x of nums) {
if (x === target) return true; // leaves the whole function
}
nums.forEach((x) => { if (x === target) return; }); // only ends this callbackfor...in is for object keys
for...in walks an object's enumerable string keys, including inherited ones. On an array that means indices as strings ('0' + 1 is '01') plus any extra properties, so never use it for arrays. For objects, Object.keys, Object.values and Object.entries with for...of are clearer and skip inherited keys.
// for...in walks the enumerable STRING keys of an object.
const scores = { ann: 9, bo: 7 };
for (const name in scores) console.log(name, scores[name]); // ann 9, bo 7
// On arrays it gives indices as strings, which breaks arithmetic.
const nums = [10, 20, 30];
for (const i in nums) console.log(i + 1, typeof i); // 01 string, 11 string, 21 string
// for...of gives values; entries() gives numeric indices with them.
for (const [i, x] of nums.entries()) console.log(i + 1, x); // 1 10, 2 20, 3 30
// Integer-like keys come first in ascending order, whatever order you inserted them.
const obj = { b: 1, 10: 'x', a: 2, 2: 'y' };
console.log(Object.keys(obj)); // ['2', '10', 'b', 'a']Iteration costs
| Operation | Cost |
|---|---|
for...of over an array, string, Map or Set | O(n) total |
[...it], Array.from(it), Array.from(it, f) | O(n) time and a new O(n) array |
m.keys(), arr.entries() (creating the iterator) | O(1): values come one at a time |
gen.next() on a flat generator | O(1) per value |
Recursive generator with yield* | O(depth) per value |
Object.keys(obj) / Object.entries(obj) | O(number of keys), builds a new array |
Stacks, queues and deques
Arrays as stacks, why shift() is O(n), a head-index queue, and a ring-buffer deque.
JavaScript has no Stack, Queue or Deque classes. An array is already a perfect stack, but using it as a queue with shift() quietly makes BFS quadratic on big inputs. Know the two-line head-index fix and keep a deque in your back pocket for sliding windows.
Arrays as stacks
push and pop work on the end of the array in O(1) amortized, and at(-1) peeks at the top. Popping or peeking an empty array returns undefined instead of throwing, so check stack.length when empty matters.
const stack = [];
stack.push(x); // push (several at once: push(a, b))
const top = stack.at(-1); // peek; same as stack[stack.length - 1]
const x = stack.pop(); // pop; undefined if empty
if (stack.length === 0) {} // empty check// An array is a stack: push and pop work on the end in O(1).
const stack = [];
stack.push(1, 2, 3); // push accepts several items
console.log(stack.pop(), stack.at(-1), stack.length); // 3 2 2: pop removes, at(-1) peeks
console.log([].pop(), [].at(-1)); // undefined undefined: no error on an empty stack
// Classic use: match brackets. The stack holds what is still waiting to be closed.
function isValid(s) {
const pairs = { ')': '(', ']': '[', '}': '{' };
const open = [];
for (const ch of s) {
if (ch in pairs) {
if (open.pop() !== pairs[ch]) return false; // wrong opener, or none left
} else {
open.push(ch);
}
}
return open.length === 0; // anything left was never closed
}
console.log(isValid('([]{})'), isValid('(]'), isValid('((')); // true false falseQueue with a head index
shift() removes the first element and moves every other element down one slot, so each call is O(n) and a BFS that shifts its queue is O(n²). V8 has a fast path that hides this for arrays under roughly 16,000 items, which is why a shift() BFS passes the small examples and then times out on the large hidden tests. unshift() has the same cost.
The fix is to never remove from the front: keep a head index and move it forward. Reading q[head++] is O(1).
const queue = [start];
let head = 0;
while (head < queue.length) { // not queue.length > 0: nothing is ever removed
const node = queue[head++];
for (const next of neighbours(node)) queue.push(next);
}// A queue as an array plus a head index: dequeue is head++, never shift().
const q = ['a', 'b'];
let head = 0;
q.push('c'); // enqueue at the back: O(1)
console.log(q[head++], q[head++]); // a b: dequeue from the front, O(1)
console.log(q.length - head, q[head]); // 1 c: size and front
// Why not shift()? It moves every remaining element down one slot.
function drainWithShift(n) {
const queue = Array.from({ length: n }, (_, i) => i);
let sum = 0;
while (queue.length) sum += queue.shift();
return sum;
}
function drainWithHead(n) {
const queue = Array.from({ length: n }, (_, i) => i);
let sum = 0;
for (let h = 0; h < queue.length; h++) sum += queue[h];
return sum;
}
for (const drain of [drainWithHead, drainWithShift]) {
const start = performance.now();
drain(50000);
console.log(drain.name, Math.round(performance.now() - start), 'ms');
}
// drainWithHead 1 ms
// drainWithShift 130 ms (Node 24; the gap grows with n², and engines differ)The array keeps every item ever enqueued. For BFS that is fine (each node is enqueued once, so memory is O(n) anyway). For a queue that lives a long time with many more operations than items alive at once, compact now and then: when head passes half the array, drop the consumed prefix with slice(head). Each compaction copies at most as many items as were dequeued since the last one, so it stays amortized O(1).
A small Queue class
Wrap the head index in a class when the queue is used in several places or the problem is a design problem. This one compacts automatically and exposes size as a getter. The BFS below also shows the level-by-level idiom: read the current size first, then dequeue exactly that many nodes.
// A queue with O(1) enqueue and dequeue that frees memory as it goes.
class Queue {
#items = [];
#head = 0;
enqueue(x) {
this.#items.push(x);
}
dequeue() {
if (this.#head === this.#items.length) return undefined;
const x = this.#items[this.#head++];
if (this.#head > 1024 && this.#head * 2 > this.#items.length) {
this.#items = this.#items.slice(this.#head); // compact: drop the consumed prefix
this.#head = 0;
}
return x;
}
peek() {
return this.#items[this.#head];
}
get size() {
return this.#items.length - this.#head;
}
}
// BFS level by level: read the level's size before adding the next level.
const graph = [[1, 2], [3], [3, 4], [5], [5], []]; // node -> neighbours
function levels(start) {
const queue = new Queue();
const seen = new Set([start]);
const out = [];
queue.enqueue(start);
while (queue.size > 0) {
const level = [];
for (let n = queue.size; n > 0; n--) {
const node = queue.dequeue();
level.push(node);
for (const next of graph[node]) {
if (!seen.has(next)) {
seen.add(next); // mark when enqueued, so nothing is queued twice
queue.enqueue(next);
}
}
}
out.push(level);
}
return out;
}
console.log(levels(0)); // [[0], [1, 2], [3, 4], [5]]
// A long-running queue stays small thanks to compaction.
const q = new Queue();
for (let i = 0; i < 100000; i++) {
q.enqueue(i);
if (i % 2 === 1) q.dequeue(); // two in, one out
}
console.log(q.size, q.peek()); // 50000 50000Mark nodes as visited when you enqueue them, not when you dequeue them; otherwise the same node can sit in the queue many times.
Ring-buffer deque
A deque (double-ended queue) adds and removes at both ends. A ring buffer stores items in a fixed-size array that wraps around: head is the index of the front item, and item i lives at (head + i) % capacity. When it fills up, copy the items into an array twice as large, which keeps every operation O(1) amortized.
// A double-ended queue on a circular array: O(1) at both ends (amortized when it grows).
class Deque {
constructor(capacity = 8) {
this.buf = new Array(capacity);
this.head = 0; // index of the front item
this.size = 0;
}
#grow() {
const old = this.buf;
this.buf = new Array(old.length * 2);
for (let i = 0; i < this.size; i++) this.buf[i] = old[(this.head + i) % old.length];
this.head = 0; // items are now unwrapped at the start
}
pushBack(x) {
if (this.size === this.buf.length) this.#grow();
this.buf[(this.head + this.size) % this.buf.length] = x;
this.size++;
}
pushFront(x) {
if (this.size === this.buf.length) this.#grow();
this.head = (this.head - 1 + this.buf.length) % this.buf.length; // + length keeps it non-negative
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; // let the item be garbage-collected
this.head = (this.head + 1) % this.buf.length;
this.size--;
return x;
}
popBack() {
if (this.size === 0) return undefined;
const i = (this.head + this.size - 1) % this.buf.length;
const x = this.buf[i];
this.buf[i] = undefined;
this.size--;
return x;
}
front() {
return this.size ? this.buf[this.head] : undefined;
}
back() {
return this.size ? this.buf[(this.head + this.size - 1) % this.buf.length] : undefined;
}
toArray() {
return Array.from({ length: this.size }, (_, i) => this.buf[(this.head + i) % this.buf.length]);
}
}
const d = new Deque(2);
d.pushBack(2);
d.pushBack(3);
d.pushFront(1); // full at capacity 2, so it grows to 4 first
d.pushFront(0);
console.log(d.toArray(), d.front(), d.back()); // [0, 1, 2, 3] 0 3
console.log(d.popFront(), d.popBack(), d.toArray(), d.size); // 0 3 [1, 2] 2Moving head backwards uses (head - 1 + capacity) % capacity: in JavaScript -1 % 8 is -1, not 7, so add the capacity before taking the remainder.
Monotonic deque preview
Sliding window maximum keeps a deque of indices whose values decrease from front to back. A new value pops every smaller value off the back (they can never be the maximum again), and the front is dropped once it leaves the window. Every index is pushed and popped at most once, so the whole scan is O(n) instead of O(n·k).
// Sliding window maximum with a monotonic deque of indices.
// The values at those indices only decrease from front to back, so the front is the max.
// Items leave the front (out of the window) or the back (beaten by a bigger value) but
// never enter at the front, so an array plus a head index is all the deque we need.
function maxSlidingWindow(nums, k) {
const dq = []; // indices; the live part is dq[head..]
let head = 0;
const out = [];
for (let i = 0; i < nums.length; i++) {
while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop(); // smaller values can never be a max again
dq.push(i);
if (dq[head] <= i - k) head++; // the front index slid out of the window
if (i >= k - 1) out.push(nums[dq[head]]);
}
return out;
}
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)); // [3, 3, 5, 5, 6, 7]
console.log(maxSlidingWindow([9, 8, 7, 6], 2)); // [9, 8, 7]Because nothing is ever added at the front, an array with pop() at the back and a head index at the front is a complete deque for this pattern. You need the ring buffer only when items really are pushed at both ends (0-1 BFS, palindrome checks on a stream, some design problems).
Stack and queue costs
| Operation | Array as stack | Array with shift/unshift | Head-index queue | Ring-buffer deque |
|---|---|---|---|---|
| Add at back | push O(1)* | push O(1)* | push O(1)* | O(1)* |
| Remove from back | pop O(1) | pop O(1) | not needed | O(1) |
| Remove from front | n/a | shift O(n) | head++ O(1) | O(1) |
| Add at front | n/a | unshift O(n) | not supported | O(1)* |
| Peek | at(-1) O(1) | [0] O(1) | [head] O(1) | O(1) |
| Size | length O(1) | length O(1) | length - head O(1) | O(1) |
* amortized: the array occasionally reallocates when it grows.
Used in: Sliding WindowStacks and Monotonic StacksTree Breadth-First SearchGraph BFS and DFSTopological Sort
Linked list and tree nodes
ListNode and TreeNode, dummy heads, building from arrays, and walking pointers without losing nodes.
Linked list and tree problems hand you node objects, not arrays. You need the exact node shapes, a quick way to build test inputs and print results, and the pointer discipline that stops you from losing half a list mid-rewire.
ListNode, TreeNode and the array format
These are the classes the problem editor and every Run button provide as globals, so don't redefine them in your solution:
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next; // next node, or null at the tail
}
}
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left; // child nodes, or null
this.right = right;
}
}
new ListNode(1, new ListNode(2)); // 1 -> 2
new TreeNode(1, new TreeNode(2), new TreeNode(3)); // 1 with children 2 and 3The judge converts test inputs for you: an array like [1, 2, 3] becomes a list and you receive its head; a level-order array like [3, 9, 20, null, null, 15, 7] becomes a tree and you receive its root. When you return a node, it is converted back to an array before comparing. An empty list or tree is null.
When you test on your own, write the same converters. A list is built by appending behind a dummy node. A tree is built from level order with nulls: a queue holds the nodes still waiting for children, and each pair of array entries fills the left and right child of the next node in the queue.
// ListNode and TreeNode are provided in the editor.
// Array -> list: append behind a dummy node so the first item needs no special case.
function listFromArray(values) {
const dummy = new ListNode();
let tail = dummy;
for (const v of values) tail = tail.next = new ListNode(v);
return dummy.next;
}
// List -> array, for printing and comparing.
function listToArray(head) {
const out = [];
for (let node = head; node; node = node.next) out.push(node.val);
return out;
}
const head = listFromArray([1, 2, 3]);
console.log(head.val, head.next.val, listToArray(head)); // 1 2 [1, 2, 3]
// Level order with nulls -> tree. Only real nodes get children in the array.
function treeFromLevels(values) {
if (!values.length || values[0] === null) return null;
const root = new TreeNode(values[0]);
const queue = [root];
let head = 0;
let i = 1;
while (head < queue.length && i < values.length) {
const node = queue[head++];
if (values[i] !== null && values[i] !== undefined) queue.push((node.left = new TreeNode(values[i])));
i++;
if (values[i] !== null && values[i] !== undefined) queue.push((node.right = new TreeNode(values[i])));
i++;
}
return root;
}
// Tree -> level order with nulls, trailing nulls trimmed.
function treeToLevels(root) {
const out = [];
const queue = [root];
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
out.push(node ? node.val : null);
if (node) queue.push(node.left, node.right);
}
while (out.length && out.at(-1) === null) out.pop();
return out;
}
// 1
// / \
// 2 3
// \ \
// 4 5
// /
// 6
const root = treeFromLevels([1, 2, 3, null, 4, null, 5, 6]);
console.log(root.left.right.val, root.left.right.left.val); // 4 6
console.log(treeToLevels(root)); // [1, 2, 3, null, 4, null, 5, 6]The level-order format lists children only for real nodes: a null has no entries for its own children. That is why index arithmetic like "children of i are at 2i + 1 and 2i + 2" does not work on these arrays (it only works for complete trees such as heaps). In this site's editor, console.log(head) prints a list compactly as ListNode(1 → 2 → 3) and a tree as TreeNode([…]); in plain Node, convert to an array first.
Dummy head nodes
Whenever the head itself might change (removing nodes, inserting at the front, merging), start with const dummy = new ListNode(0, head) and work from there. The real list is always dummy.next, so "the head was removed" stops being a special case.
// ListNode is provided in the editor.
const fromArray = (a) => a.reduceRight((next, val) => new ListNode(val, next), null);
const toArray = (h) => (h ? [h.val, ...toArray(h.next)] : []);
// Remove every node with a given value. The dummy makes "remove the head" an ordinary case.
function removeAll(head, target) {
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next) {
if (prev.next.val === target) prev.next = prev.next.next; // unlink; stay put to check the new next
else prev = prev.next;
}
return dummy.next; // not head: the old head may have been removed
}
console.log(toArray(removeAll(fromArray([7, 7, 1, 7, 2]), 7))); // [1, 2]
// Merge two sorted lists by appending behind a dummy, then return what follows it.
function merge(a, b) {
const dummy = new ListNode();
let tail = dummy;
while (a && b) {
if (a.val <= b.val) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = a ?? b; // attach whatever is left
return dummy.next;
}
console.log(toArray(merge(fromArray([1, 4, 5]), fromArray([2, 3, 6])))); // [1, 2, 3, 4, 5, 6]Two habits go with it: keep a prev or tail pointer that starts at the dummy, and return dummy.next, never the original head variable.
Walking a list and the save-next rule
Traverse with a separate variable (for (let node = head; node; node = node.next)), never by moving head itself, unless you are sure you don't need the start again. When you change a node's next, you destroy the only path to the rest of the list, so save curr.next in a variable before rewiring. Reversal is the canonical example: save, rewire, advance.
// ListNode is provided in the editor.
const fromArray = (a) => a.reduceRight((next, val) => new ListNode(val, next), null);
const toArray = (h) => (h ? [h.val, ...toArray(h.next)] : []);
// Walk with your own pointer so `head` still points at the start afterwards.
const head = fromArray([1, 2, 3, 4]);
let sum = 0;
for (let node = head; node; node = node.next) sum += node.val;
console.log(sum, head.val); // 10 1: head is untouched
// Reverse: save next BEFORE rewiring, or the rest of the list is lost.
function reverse(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next; // 1. save
curr.next = prev; // 2. rewire
prev = curr; // 3. advance both
curr = next;
}
return prev; // the old tail is the new head
}
console.log(toArray(reverse(fromArray([1, 2, 3, 4])))); // [4, 3, 2, 1]
// The broken order: rewire first, then try to step forward.
function reverseBroken(head) {
let prev = null;
let curr = head;
while (curr) {
curr.next = prev; // the only link to node 2 is gone
prev = curr;
curr = curr.next; // this is now prev: the loop stops after one node
}
return prev;
}
console.log(toArray(reverseBroken(fromArray([1, 2, 3, 4])))); // [1]Draw three boxes and the arrows between them before you write any pointer code. Every line should either save a pointer, rewire one next, or move a variable.
Tree traversals preview
Depth-first orders differ only in when the node itself is handled: before its children (pre-order), between them (in-order, which visits a BST in sorted order), or after them (post-order, used when a node needs its children's answers). Breadth-first visits one level at a time.
// TreeNode is provided in the editor. This tree is [1, 2, 3, 4, 5, null, 6] in level order:
// 1
// / \
// 2 3
// / \ \
// 4 5 6
const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, null, new TreeNode(6)));
// Depth-first: the three orders differ only in where the node itself is visited.
function walk(node, order, out = []) {
if (!node) return out;
if (order === 'pre') out.push(node.val);
walk(node.left, order, out);
if (order === 'in') out.push(node.val);
walk(node.right, order, out);
if (order === 'post') out.push(node.val);
return out;
}
console.log(walk(root, 'pre')); // [1, 2, 4, 5, 3, 6]
console.log(walk(root, 'in')); // [4, 2, 5, 1, 3, 6]
console.log(walk(root, 'post')); // [4, 5, 2, 6, 3, 1]
// Breadth-first: a queue, one level at a time.
function levelOrder(root) {
const out = [];
let level = root ? [root] : [];
while (level.length) {
out.push(level.map((n) => n.val));
level = level.flatMap((n) => [n.left, n.right]).filter(Boolean); // the next level
}
return out;
}
console.log(levelOrder(root)); // [[1], [2, 3], [4, 5, 6]]
// Optional chaining reads through missing nodes without crashing.
console.log(root.right.left?.val, root.right.left?.val ?? 'none'); // undefined noneThese recursive walks use O(h) stack space, where h is the tree height: O(log n) when balanced but O(n) for a skewed tree. See Recursion for the explicit-stack versions.
Null checks with ?. and ??
Most node-related crashes are TypeError: Cannot read properties of null (reading 'next'). Guard every dereference whose node might be missing:
while (fast && fast.next) {} // check before you jump two steps
const nextVal = node.next?.val; // undefined when there is no next node
const leftVal = node.left?.val ?? 0; // default for a missing child
if (!node) return 0; // the base case of nearly every tree recursion?. produces undefined, not null. A check like node?.next === null is false when node itself is missing, so compare with == null or test truthiness instead.
Node operation costs
| Operation | Cost |
|---|---|
| Access the k-th list node | O(k): walk from the head |
| Insert or delete after a node you hold | O(1) |
| Length, tail, search by value | O(n) |
| Build from an array / convert to an array | O(n) |
| Any full tree traversal | O(n) time, O(h) extra space |
Used in: Fast and Slow PointersIn-place Linked List ManipulationTree Depth-First SearchTree Breadth-First Search
Heaps and priority queues
JavaScript has no built-in heap. A 40-line binary heap with a comparator, and how to use it as min or max heap.
Top-k, merging k sorted lists, Dijkstra and scheduling problems all need a priority queue, and JavaScript doesn't have one. Be ready to write a binary heap from memory in a few minutes; it is about 40 lines and the same code serves as a min heap, a max heap or a heap of tuples.
Binary heap layout in an array
A binary heap is a complete binary tree stored level by level in an array, with one rule: every parent comes before its children in the heap's order (for a min heap, parent <= child). The smallest item is therefore always at index 0, and no pointers are needed because positions are computed:
const parent = (i) => (i - 1) >> 1; // >> 1 halves and rounds down
const left = (i) => 2 * i + 1;
const right = (i) => 2 * i + 2;
// [1, 3, 2, 7, 4, 5] is the tree 1
// / \
// 3 2
// / \ /
// 7 4 5Because the tree is complete, its height is ⌊log₂ n⌋, and every operation walks one root-to-leaf path at most.
MinHeap class with a comparator
// A binary heap stored in an array. compare(a, b) < 0 means a comes out first.
class MinHeap {
constructor(compare = (a, b) => a - b) {
this.compare = compare;
this.items = [];
}
get size() { return this.items.length; }
peek() { return this.items[0]; } // undefined when empty
push(x) {
this.items.push(x); // add as the last leaf...
this.siftUp(this.items.length - 1); // ...then float it up to its place
}
pop() {
const items = this.items;
if (items.length === 0) return undefined;
const top = items[0];
const last = items.pop(); // remove the last leaf
if (items.length > 0) {
items[0] = last; // move it to the root...
this.siftDown(0); // ...and sink it to its place
}
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; // parent already first: done
[items[i], items[parent]] = [items[parent], items[i]];
i = parent;
}
}
siftDown(i) {
const items = this.items;
const n = items.length;
while (true) {
const left = 2 * i + 1;
const right = left + 1;
let best = i;
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; // both children come later: done
[items[i], items[best]] = [items[best], items[i]];
i = best;
}
}
}
// Min heap of numbers.
const h = new MinHeap();
for (const x of [5, 1, 8, 3, 9, 2]) h.push(x);
console.log(h.peek(), h.size); // 1 6
const drained = [];
while (h.size) drained.push(h.pop());
console.log(drained, h.pop()); // [1, 2, 3, 5, 8, 9] undefined
// Max heap: flip the comparator.
const maxHeap = new MinHeap((a, b) => b - a);
for (const x of [5, 1, 8, 3]) maxHeap.push(x);
console.log(maxHeap.pop(), maxHeap.pop()); // 8 5
// [priority, value] tuples: compare by priority, break ties by value.
const tasks = new MinHeap((a, b) => a[0] - b[0] || a[1].localeCompare(b[1]));
tasks.push([2, 'write']);
tasks.push([1, 'plan']);
tasks.push([2, 'test']);
console.log(tasks.pop(), tasks.pop(), tasks.pop()); // [1, 'plan'] [2, 'test'] [2, 'write']
// k largest: keep a min heap of size k; its root is the k-th largest seen so far.
function kLargest(nums, k) {
const heap = new MinHeap();
for (const x of nums) {
heap.push(x);
if (heap.size > k) heap.pop(); // drop the smallest of the k + 1
}
return heap.peek();
}
console.log(kLargest([3, 2, 1, 5, 6, 4], 2)); // 5How it works, line by line:
constructor(compare)takes a comparator with the same contract assort: negative meansacomes out first. The default(a, b) => a - bgives a min heap of numbers.push(x)appendsxas the last leaf, which keeps the tree complete, thensiftUpswaps it with its parent while it should come out before the parent. At most one swap per level: O(log n).pop()saves the root, removes the last leaf, puts that leaf at the root, thensiftDownswaps it with whichever child should come out first, until neither child should. When the heap held a single item,items.pop()already emptied it, hence thelength > 0check.peek()reads index 0 andsizeis the array length: both O(1).siftUpstops on ties (>= 0), so equal items aren't swapped for nothing. A heap is not stable: equal priorities come out in no particular order, so add a tie-breaker field if order matters.
Max heaps and tuple priorities
Never write a second class: change the comparator.
const minHeap = new MinHeap(); // numbers, smallest first
const maxHeap = new MinHeap((a, b) => b - a); // numbers, largest first
const byPriority = new MinHeap((a, b) => a[0] - b[0]); // [priority, value] tuples
const withTies = new MinHeap((a, b) => a[0] - b[0] || a[1] - b[1]); // then by second field
const byDist = new MinHeap((a, b) => a.dist - b.dist); // objects
const byWord = new MinHeap((a, b) => (a < b ? -1 : a > b ? 1 : 0)); // strings
// Dijkstra-style: push [distance, node], and skip entries that went stale.
const pq = new MinHeap((a, b) => a[0] - b[0]);
pq.push([0, source]);
while (pq.size > 0) {
const [d, u] = pq.pop();
if (d > dist[u]) continue; // a shorter path to u was found after this was pushed
// relax the edges of u, pushing [newDist, v] for every improvement
}A heap can't update an item's priority in place. Push a new entry with the better priority and ignore the outdated one when it is popped ("lazy deletion"); the heap grows to O(E) entries, which is fine.
Heapify an array in O(n)
Pushing n items one at a time costs O(n log n). If you have them all up front, heapify instead: sift down every internal node, from the last one back to the root. Half the nodes are leaves and need no work, a quarter sink at most one level, an eighth at most two, and that sum is bounded by n, so the whole build is O(n).
// The same heap as plain functions on an array (a min heap of numbers), with a swap counter.
let swaps = 0;
function swap(a, i, j) {
[a[i], a[j]] = [a[j], a[i]];
swaps++;
}
function siftUp(a, i) {
while (i > 0 && a[(i - 1) >> 1] > a[i]) {
swap(a, i, (i - 1) >> 1);
i = (i - 1) >> 1;
}
}
function siftDown(a, i, n = a.length) {
while (true) {
const l = 2 * i + 1;
const r = l + 1;
let m = i;
if (l < n && a[l] < a[m]) m = l;
if (r < n && a[r] < a[m]) m = r;
if (m === i) return;
swap(a, i, m);
i = m;
}
}
// Heapify in place: leaves are already heaps, so fix each internal node from the last one up.
function heapify(a) {
for (let i = (a.length >> 1) - 1; i >= 0; i--) siftDown(a, i);
return a;
}
const isMinHeap = (a) => a.every((x, i) => i === 0 || a[(i - 1) >> 1] <= x);
const nums = [9, 4, 7, 1, 8, 2, 6];
console.log(heapify(nums), isMinHeap(nums)); // [1, 4, 2, 9, 8, 7, 6] true
// Why O(n)? Most nodes sit near the bottom and can sink only a level or two.
// Count swaps on n descending numbers, the worst case for a min heap:
for (const n of [1000, 100000]) {
const desc = Array.from({ length: n }, (_, i) => n - i);
swaps = 0;
heapify(desc.slice());
const viaHeapify = swaps;
swaps = 0;
const pushed = [];
for (const x of desc) {
pushed.push(x);
siftUp(pushed, pushed.length - 1);
}
console.log(n, 'heapify:', viaHeapify, 'one push at a time:', swaps);
}
// 1000 heapify: 992 one push at a time: 7987
// 100000 heapify: 99990 one push at a time: 1468946To add heapify to the class, accept an array in the constructor, copy it into items, and run the same loop with this.siftDown(i).
Heap or sort?
A heap earns its keep when items arrive over time or you need only some of them. Otherwise, sorting is simpler and just as fast.
| Situation | Use | Cost |
|---|---|---|
| All items known, you need them all in order | sort once | O(n log n) |
| k smallest or largest of n | size-k heap (min heap for the largest, max heap for the smallest) | O(n log k) |
| k smallest of n, n up to about 10^5 | sorting and slicing is fine too | O(n log n) |
| Pushes and pops interleave (Dijkstra, scheduling, k-way merge, running median) | heap | O(log n) per operation |
| Only the k-th item, and speed matters | quickselect | O(n) average |
Re-sorting an array after every insertion to fake a priority queue costs O(n log n) per insertion: that is the trap to avoid.
Heap costs
| Operation | Cost |
|---|---|
push | O(log n) |
pop | O(log n) |
peek, size | O(1) |
| Build from n items with heapify | O(n) |
| Build with n pushes | O(n log n) |
| Pop everything (heapsort) | O(n log n) |
| Find or delete an arbitrary item | O(n): heaps are only ordered along paths |
Used in: Intervals and Sweep LineHeaps: Top-K, K-way Merge and Two HeapsShortest Paths: BFS, Dijkstra, Bellman-Ford
Graphs and grids in JavaScript
Adjacency lists from edge lists, matrices, 4- and 8-direction arrays for grids, and visited sets.
Graph problems arrive as an edge list, a grid of characters, or a map of names. The first few lines of every solution turn that into a structure you can traverse, and picking the right one (plus the right "visited" record) decides both speed and correctness.
Edge list to adjacency list
An adjacency list stores, for each node, the nodes it links to. With nodes numbered 0 … n-1, use an array of arrays built with Array.from, which calls the factory once per slot so every node gets its own list. For an undirected graph push each edge both ways; for a directed one push only u → v. When node labels are strings or huge sparse numbers, use a Map and create each list on first use.
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u); // undirected only
}
for (const next of graph[node]) {} // neighbours of node// Edge list -> adjacency list. Nodes are 0 .. n-1.
const n = 5;
const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]];
// Undirected: store each edge in both directions.
const undirected = Array.from({ length: n }, () => []); // one separate array per node
for (const [u, v] of edges) {
undirected[u].push(v);
undirected[v].push(u);
}
console.log(undirected); // [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3]]
// Directed: only u -> v. Count in-degrees while you are at it (used by topological sort).
const directed = Array.from({ length: n }, () => []);
const indegree = new Array(n).fill(0);
for (const [u, v] of edges) {
directed[u].push(v);
indegree[v]++;
}
console.log(directed, indegree); // [[1, 2], [3], [3], [4], []] [0, 1, 1, 2, 1]
// Labels that are strings (or sparse numbers): use a Map and create lists on demand.
const flights = [['JFK', 'SFO'], ['JFK', 'ATL'], ['SFO', 'ATL']];
const routes = new Map();
for (const [from, to] of flights) {
if (!routes.has(from)) routes.set(from, []);
routes.get(from).push(to);
}
console.log(routes, routes.get('ATL') ?? []); // Map(2) { 'JFK' => ['SFO', 'ATL'], 'SFO' => ['ATL'] } []
// The classic bug: fill([]) puts the SAME array in every slot.
const shared = new Array(3).fill([]);
shared[0].push(9);
console.log(shared); // [[9], [9], [9]]If nodes are numbered from 1, allocate n + 1 slots and ignore index 0 rather than shifting every label.
Weighted edges and adjacency matrices
For weighted graphs store [neighbour, weight] pairs and destructure them in the loop. An adjacency matrix m[u][v] answers "is there an edge, and what does it cost?" in O(1) but takes n² memory: fine for n up to a couple of thousand and natural for dense graphs and all-pairs algorithms like Floyd-Warshall.
// Weighted directed edges [from, to, weight] -> adjacency list of [neighbour, weight].
const n = 4;
const edges = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 5]];
const graph = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) graph[u].push([v, w]);
for (const [v, w] of graph[0]) console.log(`0 -> ${v} costs ${w}`); // 0 -> 1 costs 4, 0 -> 2 costs 1
// Adjacency matrix: O(1) "is there an edge?" and weight lookups, but n² memory.
const INF = Infinity;
const dist = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : INF)));
for (const [u, v, w] of edges) dist[u][v] = Math.min(dist[u][v], w); // keep the cheapest parallel edge
console.log(dist[0]); // [0, 4, 1, Infinity]
// Floyd-Warshall in five lines: all-pairs shortest paths through the matrix, O(n³).
for (let k = 0; k < n; k++)
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];
console.log(dist[0]); // [0, 3, 1, 8]: 0 -> 2 -> 1 beats the direct edgeUse Infinity for "no edge" in distance matrices: Infinity + 5 is still Infinity and every real distance compares as smaller.
Grids as implicit graphs
A grid needs no adjacency list: each cell's neighbours are computed from a directions array. Always check the bounds before reading the cell. grid[-1] is undefined, and undefined[c] throws a TypeError.
const rows = grid.length, cols = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
// use grid[nr][nc]
}// A grid is a graph: each cell links to its up/down/left/right neighbours.
const grid = [
['.', '.', '#', '.'],
['#', '.', '#', '.'],
['.', '.', '.', '.'],
];
const rows = grid.length;
const cols = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const inBounds = (r, c) => r >= 0 && r < rows && c >= 0 && c < cols;
// Fewest steps from top-left to top-right with BFS. Visited cells are marked in a parallel grid.
function shortestPath(sr, sc, tr, tc) {
const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1)); // -1 = unvisited
dist[sr][sc] = 0;
const queue = [[sr, sc]];
for (let head = 0; head < queue.length; head++) {
const [r, c] = queue[head];
if (r === tr && c === tc) return dist[r][c];
for (const [dr, dc] of DIRS) {
const nr = r + dr;
const nc = c + dc;
if (!inBounds(nr, nc) || grid[nr][nc] === '#' || dist[nr][nc] !== -1) continue; // bounds first!
dist[nr][nc] = dist[r][c] + 1;
queue.push([nr, nc]);
}
}
return -1;
}
console.log(shortestPath(0, 0, 0, 3)); // 7: down around both walls and back up
// Eight directions add the diagonals.
const DIRS8 = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]];
const open8 = DIRS8.filter(([dr, dc]) => inBounds(1 + dr, 1 + dc) && grid[1 + dr][1 + dc] === '.');
console.log(open8.length); // 5 open cells around (1, 1)Grids from judges are often arrays of strings like '1' and '0', or arrays of strings per row (["#..", ".#."]), which are immutable. Compare with '1', not 1, and convert rows with grid.map((row) => [...row]) when you need to mark cells.
Visited sets, boolean arrays and marking the grid
Every traversal needs to remember where it has been. The options, from most flexible to leanest:
| Option | Key | Notes |
|---|---|---|
Set of strings | `${r},${c}` | works for anything, but builds a string per check |
Set of numbers | r * cols + c | no string building; still hashing |
Array or Uint8Array(rows * cols) | r * cols + c | O(1) index, compact, fastest |
| Mark the grid in place | grid[r][c] = '#' | no extra memory, but destroys the input |
The number key r * cols + c (multiply by the number of columns) is unique for every cell; decode it with Math.floor(id / cols) and id % cols. For BFS, mark a cell when you enqueue it, not when you dequeue it, or the same cell can be queued several times.
// Count islands of '1' three ways. All visit each cell once: O(rows × cols).
const grid = [
['1', '1', '0', '0'],
['1', '0', '0', '1'],
['0', '0', '1', '1'],
];
const rows = grid.length;
const cols = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
// 1. A Set of string keys: flexible, but builds a string per cell (slowest).
function islandsWithSet() {
const seen = new Set();
const flood = (r, c) => {
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1' || seen.has(`${r},${c}`)) return;
seen.add(`${r},${c}`);
for (const [dr, dc] of DIRS) flood(r + dr, c + dc);
};
let count = 0;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (grid[r][c] === '1' && !seen.has(`${r},${c}`)) {
count++;
flood(r, c);
}
return count;
}
// 2. A flat typed array indexed by r * cols + c: compact and fast. Uses an explicit stack.
function islandsWithArray() {
const seen = new Uint8Array(rows * cols); // all 0 = unvisited
let count = 0;
for (let start = 0; start < rows * cols; start++) {
if (grid[Math.floor(start / cols)][start % cols] !== '1' || seen[start]) continue;
count++;
seen[start] = 1;
const stack = [start];
while (stack.length) {
const id = stack.pop();
const r = Math.floor(id / cols); // decode id -> (row, col)
const c = id % cols;
for (const [dr, dc] of DIRS) {
const nr = r + dr;
const nc = c + dc;
const next = nr * cols + nc; // encode (row, col) -> id
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] !== '1' || seen[next]) continue;
seen[next] = 1;
stack.push(next);
}
}
}
return count;
}
// 3. Mark the grid itself: no extra memory, but it destroys the input (work on a copy if needed).
function islandsByMarking(g) {
const sink = (r, c) => {
if (r < 0 || r >= rows || c < 0 || c >= cols || g[r][c] !== '1') return;
g[r][c] = '0';
for (const [dr, dc] of DIRS) sink(r + dr, c + dc);
};
let count = 0;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (g[r][c] === '1') {
count++;
sink(r, c);
}
return count;
}
const copy = grid.map((row) => [...row]);
console.log(islandsWithSet(), islandsWithArray(), islandsByMarking(copy)); // 2 2 2
console.log(grid[0].join(''), copy[0].join('')); // 1100 0000Marking the grid is the shortest code, so it is common in interviews. Say out loud that it mutates the input, and restore the cells afterwards in backtracking problems such as word search.
Graph representation costs
| Representation | Memory | Neighbours of u | Is there an edge u–v? |
|---|---|---|---|
| Adjacency list (arrays) | O(V + E) | O(deg u) | O(deg u) |
Adjacency list of Sets | O(V + E) | O(deg u) | O(1) average |
| Adjacency matrix | O(V²) | O(V) | O(1) |
| Grid with a directions array | O(rows × cols) for the grid | O(4) or O(8) | O(1) |
BFS and DFS over an adjacency list cost O(V + E); over a grid, O(rows × cols). Building the list from an edge list is O(V + E).
Used in: Graph BFS and DFSTopological SortShortest Paths: BFS, Dijkstra, Bellman-Ford
Bitwise operators
&, |, ^, ~, <<, >> and >>>, the 32-bit rule, masks, and the tricks interviewers expect.
Bit tricks replace whole data structures: XOR finds the unpaired value in O(1) space, an integer mask stores a subset or a visited set, and x & (x - 1) counts set bits. In JavaScript there's one rule to keep in mind at all times: every bitwise operator first converts its operands to 32-bit signed integers.
The bitwise operators
| Operator | Name | Example | Result | Typical use |
|---|---|---|---|---|
a & b | AND | 0b1100 & 0b1010 | 0b1000 (8) | test a bit, keep only masked bits |
a | b | OR | 0b1100 | 0b1010 | 0b1110 (14) | set a bit, union of two masks |
a ^ b | XOR | 0b1100 ^ 0b1010 | 0b0110 (6) | toggle a bit, cancel pairs |
~a | NOT | ~5 | -6 | build "everything but this bit" masks |
a << k | left shift | 1 << 4 | 16 | the mask for bit k; multiply by 2^k |
a >> k | sign-propagating right shift | -16 >> 2 | -4 | divide by 2^k, rounding down |
a >>> k | zero-fill right shift | -1 >>> 28 | 15 | read bits as unsigned |
Their precedence is lower than comparisons: x & 1 === 0 means x & (1 === 0). Always parenthesise: (x & 1) === 0.
The 32-bit rule
Numbers are 64-bit floats, but &, |, ^, ~, << and >> work on a 32-bit signed copy: fractions are truncated, bits above 31 are dropped, and bit 31 is the sign. So 1 << 31 is negative, 1 << 32 is 1 (shift counts wrap at 32), and anything at or above 2^31 wraps around. x >>> 0 reinterprets the same 32 bits as an unsigned number from 0 to 2^32 − 1, which is also how you print a negative number's bits. For more than 31 bits, use arithmetic (Math.floor(x / 2), x % 2, 2 ** k) or BigInt (1n << 40n).
// Every bitwise operator first converts its operands to 32-bit signed integers.
console.log(1 << 30, 1 << 31, 1 << 32); // 1073741824 -2147483648 1: bit 31 is the sign; shift counts wrap at 32
console.log((2 ** 32 + 5) | 0, 3.9 | 0, -3.9 | 0); // 5 3 -3: high bits dropped, fractions truncated
console.log(~5, ~-1, ~~7.8); // -6 0 7: ~x equals -x - 1
// >> keeps the sign (fills with the sign bit); >>> fills with zeros.
console.log(-8 >> 1, -8 >>> 1); // -4 2147483644
console.log(-1 >>> 0, (1 << 31) >>> 0); // 4294967295 2147483648: >>> 0 reads the bits as unsigned
// Printing bits: pad to a fixed width, and go through >>> 0 for negatives.
console.log((5).toString(2).padStart(8, '0')); // 00000101
console.log((-5).toString(2), (-5 >>> 0).toString(2)); // -101 11111111111111111111111111111011
console.log(parseInt('1011', 2), 0b1011); // 11 11
// Past 31 bits, bitwise operators silently drop the high bits. Use arithmetic or BigInt.
const big = 2 ** 40 + 3;
console.log(big >> 1, Math.floor(big / 2)); // 1 549755813889: >> threw away bits 32 and up
console.log((big >> 40) & 1, Math.floor(big / 2 ** 40) % 2, (BigInt(big) >> 40n) & 1n); // 0 1 1n: is bit 40 set?Testing, setting and clearing bits
(x >> k) & 1 // 1 if bit k is set, else 0
(x & (1 << k)) !== 0 // same test as a boolean
x | (1 << k) // set bit k
x & ~(1 << k) // clear bit k
x ^ (1 << k) // toggle bit k
x & (x - 1) // clear the lowest set bit
x & -x // keep only the lowest set bit
x > 0 && (x & (x - 1)) === 0 // x is a power of two
(1 << n) - 1 // n ones: the mask of all n items (n up to 30)const bits = (x) => (x >>> 0).toString(2).padStart(8, '0');
const x = 0b10110; // 22
console.log((x >> 1) & 1, (x >> 3) & 1); // 1 0: is bit k set?
console.log(bits(x | (1 << 0))); // 00010111: set bit 0
console.log(bits(x & ~(1 << 2))); // 00010010: clear bit 2
console.log(bits(x ^ (1 << 4))); // 00000110: toggle bit 4
// x & (x - 1) clears the lowest set bit; x & -x keeps only the lowest set bit.
console.log(bits(x & (x - 1)), bits(x & -x)); // 00010100 00000010
// Power of two: exactly one bit set.
const isPowerOfTwo = (n) => n > 0 && (n & (n - 1)) === 0;
console.log(isPowerOfTwo(64), isPowerOfTwo(96), isPowerOfTwo(0)); // true false false
// Count set bits: each step removes the lowest one, so the loop runs once per set bit.
function popcount(n) {
let count = 0;
while (n !== 0) { // !== 0, not > 0: negatives have bit 31 set
n &= n - 1;
count++;
}
return count;
}
console.log(popcount(22), popcount(255), popcount(-1)); // 3 8 32
// Precedence trap: === binds tighter than &.
console.log(6 & 1 === 0, (6 & 1) === 0); // 0 trueXOR tricks
XOR is its own inverse: a ^ a is 0, a ^ 0 is a, and order doesn't matter. XOR a list together and every value that appears an even number of times cancels out. That solves "find the one value without a pair" and "find the missing number in 0..n" in O(n) time and O(1) space. a ^ b also marks exactly the bits where two numbers differ.
// a ^ a = 0 and a ^ 0 = a, in any order: equal values cancel out.
console.log(5 ^ 5, 5 ^ 0, 3 ^ 5 ^ 3); // 0 5 5
// The one value that appears once when every other value appears twice.
const singleNumber = (nums) => nums.reduce((acc, x) => acc ^ x, 0);
console.log(singleNumber([4, 1, 2, 1, 2])); // 4
// The missing number in 0..n: XOR every index and every value; the pairs cancel.
function missingNumber(nums) {
let acc = nums.length;
for (let i = 0; i < nums.length; i++) acc ^= i ^ nums[i];
return acc;
}
console.log(missingNumber([3, 0, 1])); // 2
// Hamming distance: XOR marks the differing bits, then count them.
let diff = 1 ^ 4;
let distance = 0;
for (; diff !== 0; diff &= diff - 1) distance++;
console.log((1 ^ 4).toString(2), distance); // 101 2
// XOR swap works, but zeroes the value when both sides are the same slot.
const arr = [6, 9];
const swapXor = (i, j) => { arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; };
swapXor(0, 1);
console.log(arr); // [9, 6]
swapXor(0, 0);
console.log(arr); // [0, 6]: prefer [a[i], a[j]] = [a[j], a[i]]Bitmasks for subsets
With n items, each integer from 0 to (1 << n) - 1 encodes one subset: bit i says whether item i is in it. Looping over those integers enumerates all 2^n subsets without recursion, and a single integer can stand in for a visited set in DP over subsets (traveling salesman, assigning tasks to workers). Keep n small: 2^20 is about a million.
// Every mask from 0 to 2^n - 1 is one subset: bit i says whether items[i] is in it.
const items = ['a', 'b', 'c'];
const n = items.length;
const subsets = [];
for (let mask = 0; mask < 1 << n; mask++) {
const subset = [];
for (let i = 0; i < n; i++) if (mask & (1 << i)) subset.push(items[i]);
subsets.push(subset.join('') || '-');
}
console.log(subsets); // ['-', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']
// A mask as a tiny "visited" set (state compression in DP over subsets, n up to about 20).
let visited = 0;
visited |= 1 << 3;
visited |= 1 << 0;
console.log((visited & (1 << 3)) !== 0, (visited & (1 << 2)) !== 0); // true false
const ALL = (1 << 4) - 1; // 0b1111: every one of 4 nodes
console.log(visited === ALL, (visited | 0b0110) === ALL); // false true
// Every non-empty submask of a mask, largest first.
const mask = 0b1011;
const subs = [];
for (let s = mask; s > 0; s = (s - 1) & mask) subs.push(s.toString(2));
console.log(subs); // ['1011', '1010', '1001', '1000', '11', '10', '1']| Operation | Cost |
|---|---|
| Any single bitwise operator | O(1) |
Popcount with x &= x - 1 | O(number of set bits), at most 32 |
| Enumerating all subsets of n items | O(2^n · n) |
| Enumerating every submask of every mask | O(3^n) |
x.toString(2) | O(number of bits) |
Used in: Bit Manipulation
Big-O of built-in operations
What each Array, String, Map and Set method costs, so a hidden O(n) never turns your O(n) into O(n²).
Your algorithm's Big-O is only as good as the built-ins inside its loops. One includes, shift or spread copy inside a loop silently multiplies the work by n, and a solution you analysed as O(n) times out as O(n²). Use these tables as the reference when you count.
Array method costs
| Operation | Cost | Note |
|---|---|---|
arr[i], arr.at(i), arr.length | O(1) | |
push(x), pop() | O(1) amortized | the array occasionally reallocates |
shift(), unshift(x) | O(n) | moves every element; V8 hides it below about 16k items |
splice(i, k, …items) | O(n − i + items) | shifts everything after i |
slice(a, b) | O(b − a) | a new array |
[...arr], Array.from(arr) | O(n) | a new array |
a.concat(b), [...a, ...b] | O(n + m) | a new array |
indexOf, includes, find, findIndex, some, every | O(n) | linear scan, stops early when it can |
map, filter, forEach, reduce, reverse, fill | O(n) | |
join(sep) | O(total length) | |
sort(cmp), toSorted(cmp) | O(n log n) comparisons | stable (TimSort in V8) |
flat() | O(total elements) | |
new Array(n).fill(0), Array.from({ length: n }, f) | O(n) | |
a === b | O(1) | compares references, never contents |
String method costs
Strings are immutable: every method that "changes" a string returns a new one.
| Operation | Cost | Note |
|---|---|---|
s[i], s.charCodeAt(i), s.length | O(1) | |
s + t, template literals | O(n + m) | engines may defer the copy (ropes) |
s += ch in a loop | O(n) total in V8 if you never read s in between | O(n²) when reads force copies; build an array and join('') |
slice, substring | O(k) | count it as a copy |
split(''), [...s] | O(n) | a new array |
indexOf(t), includes(t) | O(n · m) worst case | fast in practice; still a scan |
startsWith(t), endsWith(t) | O(m) | |
s === t, s < t | O(length) | compared character by character |
toLowerCase, trim, replace, replaceAll | O(n) | |
repeat(k) | O(n · k) | |
parseInt(s), Number(s), String(x) | O(length) | |
Using a string as a Map/Set key | O(length) to build and hash | number keys are cheaper |
Map, Set and object operation costs
| Operation | Cost | Note |
|---|---|---|
map.get, set, has, delete; set.add, has, delete | O(1) average | |
map.size, set.size | O(1) | a property |
new Set(arr), new Map(entries) | O(n) | |
for...of, [...map], [...map.keys()] | O(n) | |
obj[key], obj[key] = v, key in obj | O(1) average | |
delete obj[key] | O(1) | can switch the object to a slower dictionary mode |
Object.keys, values, entries | O(n) | builds a new array on every call |
Object.keys(obj).length | O(n) | keep a counter, or use a Map and size |
{ ...obj }, Object.assign({}, obj) | O(n) | shallow copy |
Hidden costs of copying and helper functions
| Operation | Cost | Note |
|---|---|---|
structuredClone(x) | O(size of x) | deep copy of nested arrays, Maps and Sets |
JSON.stringify(x), JSON.parse(s) | O(size) | loses Maps, Sets and undefined values |
JSON.stringify(a) === JSON.stringify(b) | O(n) | compares arrays by content; fine once, slow in a loop |
Math.max(...arr), Math.min(...arr) | O(n) | throws RangeError beyond roughly 100k items |
f(...arr), arr.push(...other) | O(n) | same argument-count limit for huge arrays |
console.log inside a hot loop | slow I/O per call | remove it before submitting |
Hidden O(n) traps inside loops
Each line below is O(1)-looking code that actually scans or copies, which turns an O(n) loop into O(n²):
| Trap | Fix |
|---|---|
if (!out.includes(x)) | keep a Set alongside: seen.has(x) |
queue.shift() in BFS | a head index: queue[head++] |
out = [...out, x] or out = out.concat([x]) | out.push(x) |
solve(arr.slice(1)) in recursion | pass an index: solve(arr, i + 1) |
s += ch while also reading s | push into an array, join('') once |
arr.splice(i, 1) to delete many items | filter, or a read/write pointer pass |
arr.indexOf(x) to find a position again and again | build a value → index Map once |
Object.keys(obj).length to count | a counter variable or map.size |
| sorting inside a loop to keep data ordered | sort once, or use a heap |
// Time a function. Exact numbers depend on the machine; the ratios are the point.
function time(label, fn) {
const start = performance.now();
fn();
console.log(label.padEnd(28), Math.round(performance.now() - start), 'ms');
}
const n = 20000;
const nums = Array.from({ length: n }, (_, i) => (i * 7919) % n); // n distinct values, shuffled
// 1. includes() inside a loop is a hidden inner loop: O(n²).
time('dedupe with includes', () => {
const out = [];
for (const x of nums) if (!out.includes(x)) out.push(x);
});
time('dedupe with a Set', () => {
const seen = new Set();
for (const x of nums) seen.add(x);
});
// 2. Spreading into a new array each step copies everything so far: O(n²).
time('grow with [...out, x]', () => {
let out = [];
for (const x of nums) out = [...out, x];
});
time('grow with push', () => {
const out = [];
for (const x of nums) out.push(x);
});
// 3. A string you append to AND read from (here: its last character) is copied again and again.
time('s += ch, reading s.at(-1)', () => {
let s = '';
let repeats = 0;
for (let i = 0; i < n * 5; i++) {
if (s.at(-1) === 'a') repeats++; // reading forces V8 to flatten (copy) the string
s += 'a';
}
});
time('chars array, join once', () => {
const chars = [];
let repeats = 0;
for (let i = 0; i < n * 5; i++) {
if (chars.at(-1) === 'a') repeats++;
chars.push('a');
}
chars.join('');
});
// Node 24 on a laptop:
// dedupe with includes ~30 ms
// dedupe with a Set ~1 ms
// grow with [...out, x] ~270 ms
// grow with push ~0 ms
// s += ch, reading s.at(-1) ~140 ms
// chars array, join once ~1 msAt n = 20,000 the quadratic versions already cost tens to hundreds of milliseconds; at n = 10^5 they take seconds, which is exactly where hidden tests sit. s += ch deserves a note: V8 builds such strings as ropes, so a plain append loop is often fast, but that is an engine optimisation, not a guarantee, and reading from the string between appends forces repeated copies.
Operation budgets: what n allows
// Roughly how many operations per second does this engine manage? Run a few kinds of work.
function rate(label, n, work) {
work(1000); // warm up so the JIT compiles the loop first
const start = performance.now();
work(n);
const seconds = (performance.now() - start) / 1000;
console.log(label.padEnd(26), (n / seconds).toExponential(0), 'per second');
}
rate('arithmetic in a loop', 2e7, (n) => {
let s = 0;
for (let i = 0; i < n; i++) s += i % 7;
return s;
});
rate('array reads and writes', 2e6, (n) => {
const a = new Array(n).fill(0);
for (let i = 1; i < n; i++) a[i] = a[i - 1] + 1;
return a;
});
rate('Map get + set, number keys', 1e6, (n) => {
const m = new Map();
for (let i = 0; i < n; i++) m.set(i, (m.get(i) ?? 0) + 1); // a million distinct keys
return m;
});
rate('Set add, string keys', 3e5, (n) => {
const s = new Set();
for (let i = 0; i < n; i++) s.add(`${i},${i + 1}`);
return s;
});
// Node 24 on a laptop (your numbers will differ, the ordering won't):
// arithmetic in a loop 2e+9 per second
// array reads and writes 5e+8 per second
// Map get + set, number keys 3e+7 per second
// Set add, string keys 7e+6 per secondA tight arithmetic loop runs around 10^9 iterations per second, but real algorithm steps compare, index, branch and allocate. A rule of thumb that holds up: about 10^8 simple steps per second, and 10^7 when each step touches a Map, a Set or builds a string. Judges usually allow 1–2 seconds; this site's editor stops a test after 3. Read the constraints and work backwards:
| Largest n | Complexity that fits | Typical approach |
|---|---|---|
| 10–12 | O(n!) | permutations, brute force |
| 20–25 | O(2^n), O(n · 2^n) | subsets, bitmask DP |
| 100–500 | O(n³) | Floyd-Warshall, interval DP |
| 1,000–5,000 | O(n²) | 2D DP, all pairs |
| 10^5–10^6 | O(n log n) | sorting, heaps, binary search |
| 10^7–10^8 | O(n) | one pass with O(1) work per step |
| beyond | O(log n) or O(1) | math, binary search on the answer |
Gotchas and debugging
The bugs that fail hidden tests: shared rows in 2D arrays, sort() without a comparator, floating point, and more.
Most wrong answers on hidden tests aren't wrong algorithms. They are JavaScript behaving exactly as specified in a way you didn't expect: a shared row, a string sort, a float that is almost equal. Here are the classics, grouped, each with its fix. Run the snippets to see every one happen.
Array traps: shared rows, sorting and comparisons
| Trap | What happens | Fix |
|---|---|---|
new Array(n).fill([]) | every row is the same array | Array.from({ length: n }, () => []) |
nums.sort() | numbers sorted as strings: [1, 10, 100, 9] | nums.sort((a, b) => a - b) |
a === b on arrays | compares references: [1] === [1] is false | compare lengths and elements, or JSON.stringify once |
Math.max(...[]) | -Infinity (and Math.min gives Infinity) | handle the empty case first |
strs.map(parseInt) | the index is passed as the radix: [1, NaN, NaN] | strs.map(Number) or (s) => parseInt(s, 10) |
const arr = [] | still mutable: const only blocks reassignment | copy ([...arr]) when you need a snapshot |
// 1. fill([]) puts ONE array in every row.
const bad = new Array(3).fill([]);
bad[0].push('x');
console.log(bad); // [['x'], ['x'], ['x']]
const good = Array.from({ length: 3 }, () => []); // a new row per slot
good[0].push('x');
console.log(good); // [['x'], [], []]
// 2. sort() without a comparator compares numbers as strings.
console.log([10, 9, 1, 100].sort()); // [1, 10, 100, 9]
console.log([10, 9, 1, 100].sort((a, b) => a - b)); // [1, 9, 10, 100]
// 3. Arrays compare by reference.
console.log([1, 2] === [1, 2]); // false
const same = (a, b) => a.length === b.length && a.every((x, i) => x === b[i]);
console.log(same([1, 2], [1, 2])); // true
// 4. Math.max of nothing is -Infinity (and Math.min is Infinity).
const empty = [];
console.log(Math.max(...empty), empty.length ? Math.max(...empty) : 0); // -Infinity 0
// 5. map(parseInt) passes the index as the radix.
console.log(['1', '2', '3'].map(parseInt)); // [1, NaN, NaN]
console.log(['1', '2', '3'].map(Number)); // [1, 2, 3]
// 6. const stops reassignment, not mutation.
const fixed = [1, 2];
fixed.push(3); // allowed
console.log(fixed); // [1, 2, 3]Number and equality traps
| Trap | What happens | Fix |
|---|---|---|
== | converts types: 0 == '' and '1' == 1 are true | always === and !== |
x === NaN | always false: NaN equals nothing | Number.isNaN(x) |
0.1 + 0.2 === 0.3 | false: binary floats can't store most decimals | compare Math.abs(a - b) < 1e-9, or work in integers (cents) |
7 / 2 | 3.5: there is no integer division | Math.floor(a / b) for non-negatives, Math.trunc to round toward zero |
-7 % 3 | -1: the result keeps the sign of the left side | ((a % m) + m) % m |
obj[3] = … | keys become strings: Object.keys gives '3' | a Map keeps number keys as numbers |
// 1. == converts types before comparing. Use === everywhere.
console.log(0 == '', '1' == 1, null == undefined, 0 === ''); // true true true false
// 2. NaN is not equal to anything, itself included.
const x = NaN;
console.log(x === NaN, Number.isNaN(x)); // false true
// 3. Decimal fractions are not exact in binary floating point.
console.log(0.1 + 0.2 === 0.3, 0.1 + 0.2); // false 0.30000000000000004
console.log(Math.abs(0.1 + 0.2 - 0.3) < 1e-9); // true: compare with a tolerance
// 4. / is real division. Truncate or floor explicitly.
console.log(7 / 2, Math.floor(7 / 2), Math.trunc(-7 / 2), Math.floor(-7 / 2)); // 3.5 3 -3 -4
// 5. % keeps the sign of the left operand.
console.log(-7 % 3, ((-7 % 3) + 3) % 3); // -1 2: the second form is always in 0 .. 2
// 6. Object keys are strings, so numbers come back as strings.
const counts = {};
for (const n of [3, 1, 3]) counts[n] = (counts[n] ?? 0) + 1;
console.log(Object.keys(counts), Object.keys(counts)[0] + 1); // ['1', '3'] 11
const freq = new Map();
for (const n of [3, 1, 3]) freq.set(n, (freq.get(n) ?? 0) + 1);
console.log([...freq.keys()], [...freq.keys()][0] + 1); // [3, 1] 4See Numbers, Math and integer tricks and Objects for the details.
Mutation, iteration and off-by-one traps
| Trap | What happens | Fix |
|---|---|---|
splice while looping forward | the next element slides into i and is skipped | loop backwards, or build a new array with filter |
sort, reverse, splice, fill on the input | the caller's array changes too | copy first ([...nums]) or use toSorted, toReversed |
arr[arr.length] | undefined: the last index is length - 1 | arr.at(-1) |
comparing a[i] with a[i + 1] | reads past the end on the last step | loop while i + 1 < a.length |
for (let i = 1; i < n; i++) vs i <= n | one element missed or one extra | dry-run the loop on n = 1 and n = 2 |
adding to a Set/Map while iterating it | new items are visited too | collect changes, apply after the loop |
// 1. Removing while looping forward skips the element that slides into place.
const nums = [2, 4, 4, 5];
for (let i = 0; i < nums.length; i++) if (nums[i] % 2 === 0) nums.splice(i, 1);
console.log(nums); // [4, 5]: one 4 survived
const fixed = [2, 4, 4, 5];
for (let i = fixed.length - 1; i >= 0; i--) if (fixed[i] % 2 === 0) fixed.splice(i, 1);
console.log(fixed, [2, 4, 4, 5].filter((n) => n % 2 !== 0)); // [5] [5]: loop backwards, or filter
// 2. sort, reverse and splice change the caller's array. Copy first if you need the original.
function median(values) {
const sorted = [...values].sort((a, b) => a - b); // or values.toSorted(...)
return sorted[sorted.length >> 1];
}
const input = [9, 1, 5];
console.log(median(input), input); // 5 [9, 1, 5]: input untouched
// 3. Off-by-one: the last index is length - 1, and pairs stop one early.
const a = [1, 2, 3];
let pairs = 0;
for (let i = 0; i + 1 < a.length; i++) pairs++; // compares a[i] with a[i + 1]
console.log(a[a.length], a.at(-1), pairs); // undefined 3 2Mutating the input is sometimes allowed (it saves memory), but if your solution needs the original order later, or a test reuses the same array, a sneaky sort() fails the next step.
Function, class and recursion traps
| Trap | What happens | Fix |
|---|---|---|
(x) => { x * 2 } | braces make a block: returns undefined | drop the braces or add return |
helper(next) instead of return helper(next) | the recursive answer is discarded | return it (or combine it) |
Trie() without new | TypeError: Class constructor … cannot be invoked without 'new' | new Trie() |
| recursion 10^5 levels deep | RangeError: Maximum call stack size exceeded | loop or explicit stack (Recursion) |
| a memo or counter declared outside the function | carries values over between test cases | create state inside the function |
result.push(path) in backtracking | every entry is the same array, emptied at the end | result.push([...path]) |
// 1. Braces after => start a block: no return, no value.
const broken = [1, 2].map((x) => { x * 2; });
console.log(broken[0], broken[1]); // undefined undefined
console.log([1, 2].map((x) => x * 2)); // [2, 4]: no braces returns the expression
// 2. A recursive helper whose result is not returned.
function contains(node, target) {
if (!node) return false;
if (node.val === target) return true;
contains(node.next, target); // bug: the answer is thrown away
}
function containsFixed(node, target) {
if (!node) return false;
return node.val === target || containsFixed(node.next, target);
}
const list = { val: 1, next: { val: 2, next: null } };
console.log(contains(list, 2), containsFixed(list, 2)); // undefined true
// 3. Classes need new.
class Counter {
count = 0;
}
try {
Counter();
} catch (e) {
console.log(e.name); // TypeError
}
// 4. Deep recursion overflows the stack around 10^4 levels.
const depth = (n) => (n === 0 ? 0 : 1 + depth(n - 1));
try {
depth(1e5);
} catch (e) {
console.log(e.message); // Maximum call stack size exceeded
}Debugging in the editor
When a hidden test fails, shrink it: copy the failing input into a sample, then print what your code sees.
- Label your logs.
console.log({ i, sum })prints{ i: 0, sum: 4 }, so you never mix up which number is which. - Maps and Sets print their contents directly. Spread them (
[...freq]) to see entries as arrays. JSON.stringify(grid)prints a nested array on one compact line, androw.join(' ')per row lays a grid out.JSON.stringifyturns Maps and Sets into{}, so don't use it on them.- Log a few iterations, not all of them. Thousands of lines slow the run and bury the one that matters (the editor keeps the first 200).
- Check invariants loudly:
if (lo > hi) console.log('crossed', lo, hi)beats staring at output.
const nums = [4, 1, 3];
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
console.log({ i, sum }); // an object literal labels every value
}
// { i: 0, sum: 4 } { i: 1, sum: 5 } { i: 2, sum: 8 }
// Maps and Sets print their contents directly; spread them to see entries as arrays.
const freq = new Map([['a', 2], ['b', 1]]);
console.log('freq', freq, [...freq]); // freq Map(2) { 'a' => 2, 'b' => 1 } [['a', 2], ['b', 1]]
// JSON.stringify gives one compact line for nested arrays (great for grids and DP tables)...
const grid = [[1, 0], [0, 1]];
console.log(JSON.stringify(grid)); // [[1,0],[0,1]]
grid.forEach((row) => console.log(row.join(' '))); // one row per line: 1 0, then 0 1
// ...but it loses Maps and Sets, which come out as {}.
console.log(JSON.stringify({ freq, seen: new Set([1]) })); // {"freq":{},"seen":{}}
// Logging is slow: print a few iterations, not all 10^5.
for (let i = 0; i < 100000; i++) if (i < 2) console.log('iteration', i); // iteration 0, iteration 1Used in: Dynamic Programming II: Grids, Strings and KnapsackMatrix and Grid Simulation