TypeScript Built-in Time Complexity: The Interview Cheat Sheet
Array.shift()costs O(n) and turns BFS into O(V² + E) — use a head-pointer index instead- TypeScript's runtime is JavaScript — all types are erased at compile time, so complexity lives in V8, not the type system
Mapgives O(1) get/set/has/delete with any key type; prefer it over plain objects for dynamic keys to avoid prototype footgunsSet.has()is O(1) vsArray.includes()which is O(n) — swap the structure, not the algorithm- String concatenation in a loop is O(n²) because every
+=allocates a new string; collect into an array and call.join("") Array.sort()without a comparator sorts lexicographically — always pass(a, b) => a - bfor numbers- No built-in heap, deque, or sorted map in TypeScript; know the workarounds before your 45-minute clock starts
You know Array.push() is O(1). You know Array.sort() is O(n log n). But do you know what Array.shift() costs? Most TypeScript engineers don't, and it shows up in interviews when they queue with an array and wonder why their BFS is slower than it should be. The answer is not subtle. It's O(n). Every call.
Arrays, Map, Set, strings, plain objects. Every TypeScript time complexity, every trap, and when to reach for something else.
The Runtime Is JavaScript. Types Disappear.
TypeScript compiles to JavaScript. All generic type parameters, type annotations, and as casts are erased before your code touches V8. The runtime complexity of TypeScript code is identical to JavaScript. There is no TypeScript overhead, no type-checking at runtime, no secret fast paths for typed arrays. You are writing JavaScript in a trench coat. The full complexity picture lives in the V8 engine executing the compiled output.
Good news: V8 is well-studied and the behavior is predictable. Bad news: most tutorials lie by omission about which operations are expensive.
Arrays: One Trap Will End Your BFS
The JavaScript Array is a dynamic array backed by native C++ in V8. Index access is O(1). Appending is O(1) amortized via the standard doubling strategy (see dynamic array internals).
| Operation | Time | Notes |
|---|---|---|
arr[i] | O(1) | Direct index read or write |
push(...items) | O(1) amortized | Doubling realloc at capacity |
pop() | O(1) | Removes last element |
shift() | O(n) | Moves every element left |
unshift(...items) | O(n) | Moves every element right |
splice(i, k) | O(n) | Shifts elements after index |
slice(i, j) | O(j - i) | Copies the slice |
concat(other) | O(n + m) | Copies both arrays |
indexOf(val) | O(n) | Linear scan |
includes(val) | O(n) | Linear scan |
find(pred) | O(n) | Stops at first match |
filter(pred) | O(n) | New array, full pass |
map(fn) | O(n) | New array, full pass |
reduce(fn) | O(n) | Single pass |
forEach(fn) | O(n) | Single pass, no return |
sort(cmp) | O(n log n) | Timsort, stable since ES2019 |
reverse() | O(n) | In-place |
flat(depth) | O(n) | Total elements in output |
fill(val) | O(n) | |
[...arr] spread | O(n) | Full copy |
.length | O(1) | Stored as a property |
shift() is the trap that ends interviews. Using an array as a queue with shift() for dequeue turns BFS from O(V + E) into O(V² + E) on a dense graph. The code looks fine. It produces the right answer. It just does it in quadratic time, quietly, while you explain to the interviewer that your solution is "basically linear."
Use a head-pointer index instead. Two extra characters. Entirely different complexity class.
// Wrong: O(n²) BFS queue const queue: number[] = [start]; while (queue.length > 0) { const node = queue.shift(); // O(n) every iteration } // Right: O(1) dequeue with head pointer let head = 0; const queue: number[] = [start]; while (head < queue.length) { const node = queue[head++]; // O(1) }
One more: sort() with no comparator sorts lexicographically. [10, 9, 2].sort() gives [10, 2, 9]. Always pass (a, b) => a - b for numbers. This one is famous enough that most engineers know it. They still forget it under pressure.
Map: Use This Instead of Objects
Map is what you actually want for key-value in an interview, not a plain object. It accepts any key type, preserves insertion order, exposes a .size property, and has semantics that won't surprise you.
| Operation | Time | Notes |
|---|---|---|
map.get(key) | O(1) avg | Hash lookup |
map.set(key, val) | O(1) amortized | Rehash is O(n) but amortized O(1) |
map.has(key) | O(1) avg | |
map.delete(key) | O(1) avg | |
map.size | O(1) | Stored integer |
map.clear() | O(n) | Deallocates all buckets |
| Iteration | O(n) | for...of, .keys(), .values(), .entries() |
V8's Map uses a hash table with a linear probe scheme and rehashes when the load factor gets too high. Worst-case for a single operation is O(n) during a rehash, but amortized across all insertions it stays O(1). The full analysis is at HashMap time complexity.
For interview purposes, treat Map as O(1) get/set/has/delete. If an interviewer asks you to prove it, that's a different conversation.
const freq = new Map<string, number>(); for (const ch of s) { freq.set(ch, (freq.get(ch) ?? 0) + 1); }
The ?? 0 pattern uses nullish coalescing rather than || 0, which correctly handles a stored value of 0 without overwriting it. Small thing. Costs you nothing to get right.
Set: Membership Checks for Free
Set is your constant-time membership check. Same hash table internals as Map.
| Operation | Time |
|---|---|
set.add(val) | O(1) amortized |
set.has(val) | O(1) avg |
set.delete(val) | O(1) avg |
set.size | O(1) |
set.clear() | O(n) |
| Iteration | O(n) |
Set is strictly better than an array for membership checks. arr.includes(val) is O(n); set.has(val) is O(1). This is one of those places where swapping the data structure, not the algorithm, drops you a complexity class.
// Deduplicate and check membership: O(n) total const seen = new Set<number>(nums); for (const n of nums) { if (seen.has(n + 1) && !seen.has(n - 1)) { // start of a sequence } }
ES2025 adds Set.prototype.union(), intersection(), and difference(). These are not available on LeetCode's Node 18 runtime. Don't reach for them and then spend ten minutes confused about why your code throws.
String: Every Operation Is a Copy
TypeScript strings are immutable UTF-16 sequences. This is one of those facts that sounds boring and then becomes extremely relevant at 2AM when you're wondering why your string-building loop is quadratic.
| Operation | Time | Notes |
|---|---|---|
s.length | O(1) | Stored property |
s[i] / s.charAt(i) | O(1) | |
s.charCodeAt(i) | O(1) | UTF-16 code unit |
s + t | O(n + m) | Allocates a new string |
Template literal `${s}${t}` | O(n + m) | Same allocation cost |
s.slice(i, j) | O(j - i) | |
s.substring(i, j) | O(j - i) | |
s.indexOf(sub) | O(n * m) | Naive; V8 uses optimized algorithms |
s.includes(sub) | O(n * m) | Same |
s.split(sep) | O(n) | |
s.toLowerCase() | O(n) | |
s.replace(pat, rep) | O(n) | Single replacement |
s.replaceAll(pat, rep) | O(n) | |
s.trim() | O(n) | |
s.repeat(k) | O(n * k) |
Every operation that produces a new string allocates. String concatenation in a loop is O(n²), and it looks completely fine while doing it. The classic disaster:
// Wrong: O(n²) total let result = ""; for (const ch of chars) { result += ch; // new string every iteration } // Right: O(n) total const parts: string[] = []; for (const ch of chars) { parts.push(ch); } const result = parts.join("");
Collect into an array, call .join("") at the end. The interviewer will notice either way. Might as well let them notice the right thing.
Object: Fast to Read, Surprising to Enumerate
Plain objects are fine for fixed-key records. They have two interview gotchas that come up more than they should.
| Operation | Time | Notes |
|---|---|---|
obj[key] (read) | O(1) amortized | Optimized by V8's hidden classes |
obj[key] = val (write) | O(1) amortized | May trigger hidden-class transition |
key in obj | O(1) avg | Checks prototype chain too |
obj.hasOwnProperty(key) | O(1) avg | Own properties only |
Object.keys(obj) | O(n) | n = number of own enumerable keys |
Object.values(obj) | O(n) | |
Object.entries(obj) | O(n) | |
{ ...obj } spread | O(n) | Shallow copy |
Object.assign(target, src) | O(n) |
Map is safer than a plain object for dynamic keys in interviews because it avoids the prototype footgun. "__proto__" and "constructor" are valid Map keys. In a plain object, they're landmines. When in doubt, use Map.
The second gotcha is enumeration cost. If your frequency table has k distinct keys and you call Object.keys(freq).sort(), you're paying O(k log k), not O(1). Easy to forget when freq looks like a simple lookup table.
What TypeScript Is Missing
JavaScript's standard library is famously minimal. Three structures you will need to implement yourself if you're using TypeScript in an interview:
Min-Heap / Priority Queue. No built-in. For Dijkstra, k-way merge, or any top-k problem, write a 30-line MinHeap class or fall back to a sorted array (O(n) insert, O(1) min). See heap internals. A sorted array is fine for small n; anything larger needs the real thing. Yes, Python has heapq. TypeScript does not. That's the world we live in.
O(1) Deque. No ArrayDeque. Array.shift() is O(n), as shown above. The standard workaround is a head-pointer index on a plain array. For sliding window monotonic deque problems requiring O(1) front operations, simulate with a number[] and careful indexing.
Sorted Map / TreeMap. No equivalent. When a problem needs ordered key iteration with O(log n) inserts, maintain a sorted array with binary search: O(log n) lookup, O(n) insert. Writing a balanced BST from scratch in 45 minutes is a choice you can make, but it is a very ambitious choice.
Quick Reference
| Structure | Get | Insert | Delete | Has | Iterate |
|---|---|---|---|---|---|
Array (by index) | O(1) | O(1) amort (end) | O(n) | O(n) | O(n) |
Map | O(1) avg | O(1) amort | O(1) avg | O(1) avg | O(n) |
Set | N/A | O(1) amort | O(1) avg | O(1) avg | O(n) |
Object | O(1) avg | O(1) avg | O(1) avg | O(1) avg | O(n) |
string | O(1) | N/A (immutable) | N/A | O(n) | O(n) |
Practice Under Pressure
Knowing the complexities is half the work. The other half is calling them out to your interviewer mid-solution, defending your choice of Map over Object, and catching your own O(n²) string concatenation before they do. A cheat sheet helps. An interviewer who pushes back on your complexity claims in real time helps more. SpaceComplexity runs voice-based mock interviews where the AI does exactly that, which is the kind of pressure that reveals whether you actually know this or just recognize it when you see it written down.