JavaScript Built-In Time Complexity: The Interview Cheat Sheet
shift()andunshift()are O(n): use a head pointer for BFS queues or you turn an O(n) traversal into O(n²).Array.sort()is lexicographic by default: always pass(a, b) => a - bfor numeric sorting or the wrong answer leaves silently.- String concatenation in a loop is O(n²): collect characters into an array and call
.join('')once at the end. MapandSetgive O(1) average for get/set/has/delete: replaceArray.includes()withSet.has()inside any inner loop.Math.max(...largeArray)throwsRangeErrorabove roughly 500K elements: use a manual loop for safety.- JavaScript has no built-in heap, sorted map, or deque: know which data structure you need to implement before your interview starts.
You have a BFS. It's working. Probably.
Except shift() is your dequeue operation, and your O(n) solution is secretly O(n²). The algorithm is correct. The complexity analysis isn't. The interviewer is about to ask.
JavaScript makes it easy to write clean, readable code. It does not make it easy to know what that code costs. This cheat sheet covers JavaScript built-in time complexity for arrays, strings, Map, Set, and Object so nothing surprises you mid-interview.
arr.shift() looks like arr.pop(). One is O(1). The other is O(n). [3, 1, 10].sort() looks reasonable. It returns [1, 10, 3]. The comparator bug is silent and you won't catch it until the wrong answer leaves the judge. You can write the entire algorithm correctly and still get tripped up because you reached for the wrong built-in at the wrong moment.
Arrays: The One You'll Use for Everything
JavaScript arrays are dynamic arrays under the hood. V8 allocates extra capacity and resizes by doubling, so appending is amortized O(1). Everything that touches the beginning of the array involves shifting elements and costs O(n).
| Operation | Complexity | Notes |
|---|---|---|
arr[i] | O(1) | Random access |
arr.length | O(1) | Stored property |
push(val) | O(1) amortized | Append to end |
pop() | O(1) | Remove from end |
shift() | O(n) | Remove from front, shifts all elements |
unshift(val) | O(n) | Prepend, shifts all elements |
splice(i, n) | O(n) | Removes or inserts at index, shifts remainder |
slice(lo, hi) | O(k) | k = hi - lo, copies the slice |
indexOf(val) | O(n) | Linear scan from front |
includes(val) | O(n) | Linear scan from front |
find(fn) | O(n) | Stops at first match |
findIndex(fn) | O(n) | Stops at first match |
sort() | O(n log n) | Timsort since V8 7.0, stable, in-place |
reverse() | O(n) | In-place |
concat(other) | O(n + m) | Creates a new array |
map(fn) | O(n) | Creates a new array |
filter(fn) | O(n) | Creates a new array |
reduce(fn) | O(n) | Linear fold |
forEach(fn) | O(n) | No return value |
some(fn) / every(fn) | O(n) worst case | Short-circuits on match |
flat(depth) | O(n) | n = total elements across all levels |
fill(val, lo, hi) | O(k) | k = hi - lo |
join(sep) | O(n) | Builds a string |
[...arr] | O(n) | Full copy via spread |
shift() Will Ruin Your BFS and Your Day
The most common array mistake in interviews is using shift() as the dequeue operation in BFS. It looks correct. It is not.
Picture this: you're traversing a graph with 10,000 nodes. Every call to shift() moves every remaining element one index to the left. You're not doing 10,000 operations. You're doing 50 million. The algorithm passes on small test cases. It fails on large ones. You declared O(n). The interviewer knows it's O(n²).
Every shift() call moves every remaining element one index to the left. On a queue of 10,000 nodes that costs 50 million element moves across the full traversal, not 10,000. The fix is a head pointer:
const queue = [start]; let head = 0; while (head < queue.length) { const node = queue[head++]; // O(1), no shifting for (const neighbor of graph[node]) { queue.push(neighbor); } }
The array grows from the back, and head advances through it. Same result. O(n) total instead of O(n²).
sort() Is Lexicographic by Default
Here is a real thing that JavaScript does:
[1, 10, 2].sort() // → [1, 10, 2]
Not a bug. The ECMAScript specification. Array.prototype.sort() converts elements to strings before comparing unless you pass a comparator. "10" sorts before "2" because '1' < '2' in Unicode. The language made a choice in 1995 and here we are.
Always pass a comparator for numbers:
arr.sort((a, b) => a - b); // ascending arr.sort((a, b) => b - a); // descending
sort() mutates the original array. Clone first if you need the original intact:
const sorted = [...arr].sort((a, b) => a - b);
Strings: The Loop Trap
String primitives are immutable in JavaScript. Every operation that produces a new string allocates new memory for the full result.
| Operation | Complexity | Notes |
|---|---|---|
str[i] / charAt(i) | O(1) | Index access |
str.length | O(1) | Stored property |
charCodeAt(i) | O(1) | Code unit at index |
String.fromCharCode(n) | O(1) per character | |
slice(lo, hi) | O(k) | k = hi - lo |
indexOf(sub) | O(n · m) | n = str length, m = sub length |
includes(sub) | O(n · m) | Same internals |
startsWith(sub) | O(m) | m = sub length |
endsWith(sub) | O(m) | m = sub length |
split(delim) | O(n) | Returns array |
toLowerCase() / toUpperCase() | O(n) | Creates new string |
trim() | O(n) | Creates new string |
repeat(k) | O(n · k) | Creates new string |
str1 + str2 | O(n + m) | Per operation |
| String concat in a loop | O(n²) | The classic mistake |
String concatenation inside a loop is O(n²). Every + allocates a new string object and copies both operands into it. For n iterations building a string of total length n, you do 1 + 2 + ... + n = O(n²) character copies. This passes on short strings and times out at n = 10,000. You will not see the problem until it's too late.
// O(n²): never do this let result = ''; for (const ch of chars) { result += ch; } // O(n): collect, then join once const parts = []; for (const ch of chars) { parts.push(ch); } const result = parts.join('');
If you know Python, this is the same rule. Python's ''.join(parts) exists for the same reason. The Python built-in time complexity guide covers the equivalent traps for that language.
Map: Start Here for Key-Value Problems
Map is a hash map with O(1) average for every core operation. It should be your first reach for frequency counting, memoization, and association.
| Operation | Complexity |
|---|---|
map.get(key) | O(1) average |
map.set(key, val) | O(1) average |
map.has(key) | O(1) average |
map.delete(key) | O(1) average |
map.size | O(1) |
map.clear() | O(n) |
Iteration (forEach, for...of) | O(n) |
Map accepts any value as a key, including objects, arrays, and functions. Plain objects coerce every key to a string, which means coordinate pairs, node references, and anything non-primitive cannot be used safely as keys in a plain object. The bug is silent: obj[{x:1}] and obj[{x:2}] both write to the key "[object Object]". You've been tracking one bucket for everything. Use Map when key type matters.
const freq = new Map(); for (const ch of s) { freq.set(ch, (freq.get(ch) ?? 0) + 1); }
Use ?? 0 not || 0. The difference matters when stored values can be zero: || 0 resets a count back to zero every time it reaches zero. Exactly when you don't want that.
The hash map time complexity guide covers load factor, collision handling, and why the O(1) guarantee degrades under adversarial inputs.
Set: Your Array.includes() Is O(n)
Set is a hash set. Testing membership is O(1). Testing membership with Array.includes() is O(n). That's the difference between O(n) and O(n²) for a visited check in a graph traversal. Whenever you find yourself asking "have I seen this before?" in a loop, replace the array check with a Set.
| Operation | Complexity |
|---|---|
set.add(val) | O(1) average |
set.has(val) | O(1) average |
set.delete(val) | O(1) average |
set.size | O(1) |
new Set(arr) | O(n) |
Spread back to array [...set] | O(n) |
// O(n) deduplication const unique = [...new Set(arr)]; // O(1) per lookup in a visited check const visited = new Set(); for (const node of queue) { if (!visited.has(node)) { visited.add(node); // process } }
Object: Works, With Caveats
Plain objects are fine for string keys when you control them. Property access is O(1) average. The hazard is the prototype chain.
| Operation | Complexity |
|---|---|
obj[key] read/write | O(1) average |
key in obj | O(1) average (walks prototype chain) |
obj.hasOwnProperty(key) | O(1) average |
Object.keys(obj) | O(n) |
Object.values(obj) | O(n) |
Object.entries(obj) | O(n) |
{...obj} spread | O(n) |
Object.keys() is O(n) in the number of own enumerable properties, not O(1). Calling it inside a loop produces hidden O(n²) behavior. This is one of those bugs that's invisible until you're staring at a profiler wondering why your "O(n)" solution took 4 seconds on a 50,000-element input.
{} inherits from Object.prototype. Keys like "constructor", "toString", and "hasOwnProperty" shadow inherited methods. When keys come from user input or problem inputs you do not control, use Map. For a prototype-free dictionary, Object.create(null) creates one.
Math.max and the Spread Trap
Math.max(...arr) spreads the entire array as individual function arguments. For arrays larger than roughly 500,000 elements, this throws RangeError: Maximum call stack size exceeded because every element becomes a function argument on the call stack. In interview problems you usually won't hit this limit, but "what happens with a very large array?" is a fair follow-up and "it crashes" is not the answer you want to give.
// Throws for very large arrays const max = Math.max(...arr); // Safe for any size, O(n) let max = -Infinity; for (const x of arr) { if (x > max) max = x; }
What JavaScript Is Missing
JavaScript has no built-in heap, sorted map, or proper double-ended queue. This is a real gap compared to Java, Python, and C++ in a coding interview.
Python has heapq. Java has PriorityQueue. C++ has std::priority_queue. You have Array.prototype.sort(), which is O(n log n) every time, on a mutable array, in-place. If you need to repeatedly extract the minimum from a growing collection, you sort the whole thing again after every insertion. It's fine. It's definitely fine.
For top-k problems, Dijkstra's algorithm, and anything requiring repeated minimum or maximum extraction, you either roll a MinHeap class (roughly 35 lines with a comparator function) or accept O(n log n) sort-per-pop behavior. For sliding window maximum, you simulate a monotonic deque with an array and the head-pointer trick to avoid O(n) shifts.
The JavaScript for Coding Interviews guide breaks down the missing pieces and includes a working MinHeap implementation.
Practice What You Reach For
Knowing these costs as a list is the easy part. The hard part is catching yourself mid-solution when you've already written arr.shift() and realizing it invalidates your complexity claim before the interviewer asks.
That recognition, under pressure, while explaining your thinking out loud, is a skill you build by doing it. SpaceComplexity runs voice-based mock interviews where follow-up questions about complexity are standard: "What's the time complexity of your BFS?" "Would shift() change your answer?" The feedback comes immediately, not after the real interview.
JavaScript Built-In Time Complexity: Quick Reference
shift()andunshift()are O(n). Use a head pointer for BFS queues.Array.sort()is lexicographic by default. Always pass(a, b) => a - bfor numbers.- String concatenation in a loop is O(n²). Collect into an array, then
join('')once. MapandSetgive you O(1) average for all core operations. ReplaceArray.includes()withSet.has()in any inner loop.Math.max(...largeArray)can throw. Use a loop for safety.- JavaScript provides no heap, sorted map, or deque. Know what you're building before you start.