Your Language's Data Structures: Python, Java, C++, JavaScript
Why this exists
Every algorithm in this course is written on top of a standard library, and the standard library is where most real complexity bugs live. The algorithm is on paper; the implementation calls list.insert(0, x) inside the loop and becomes . The two-pointer solution is linear; arr.shift() in JavaScript makes it quadratic. The BFS is correct; LinkedList.get(i) in Java turns it into a crawl. Interviewers see this constantly, and so do code reviewers in production. Knowing the cost of every method you call is not trivia — it is the difference between an analysis and a guess.
This is a reference lesson. It is organised by language, then by container, then by operation, with the complexity of each operation, a few paragraphs on how the container is built (which is what makes the complexities obvious rather than memorised), and the gotchas that actually bite. After the four language sections come translation tables — the same operation written idiomatically in all four languages, with runnable code — a cross-language complexity cheat table, and a pitfalls section that collects the classic traps.
Read it once end to end for your main language, skim the other three, then come back whenever a later lesson says "use a heap" or "use an ordered map" and you need to know what that means in your language. The previous lesson, How Data Structures Live in Memory, explains why these costs are what they are; this one tells you what they are. The capstone has you measure them.
How to read the tables
- is the number of elements in the container; is the size of the argument (a slice, a second collection, the number of items requested).
- "Amortised" means the average over a sequence of operations; a single call can be slower (a reallocation). "Average" means expected over hash functions or random inputs; the worst case is usually .
- Complexities come from the official documentation where it states them — the Python wiki's TimeComplexity page, the Java API documentation, cppreference and the C++ standard, the ECMAScript specification and V8's engineering blog — and otherwise from the implementation source. Where documentation is silent and the claim rests on reading the source or on measurement, the text says so.
Choosing a container
flowchart TD
Q1{"Need key lookup?"} -->|"no"| Q2{"Insert/remove where?"}
Q1 -->|"yes"| Q3{"Need keys in sorted order,<br/>floor/ceiling, ranges?"}
Q3 -->|"no"| H["Hash map / set<br/>dict, HashMap, unordered_map, Map"]
Q3 -->|"yes"| T["Ordered map<br/>TreeMap, std::map, bisect on a sorted list"]
Q2 -->|"end only"| A["Dynamic array<br/>list, ArrayList, vector, Array"]
Q2 -->|"both ends"| D["Deque<br/>deque, ArrayDeque, std::deque"]
Q2 -->|"always the min or max"| P["Priority queue<br/>heapq, PriorityQueue, priority_queue"]
Q2 -->|"middle, with a held position"| L["Linked list<br/>only when you already hold the node"]
Python
Python's containers are few, well documented and uniformly built on two ideas: a dynamic array of pointers (list, tuple, the entries array of dict) and an open-addressing hash table (dict, set). Everything else in the standard library is a thin layer over these. Python 3.12+ is assumed; measured numbers in this section are from CPython 3.14.6.
Containers at a glance
| Container | Built on | Ordered? | Typical use |
|---|---|---|---|
list | dynamic array of object pointers | by index | sequences, stacks, the default |
tuple | fixed array of object pointers | by index | immutable records, dict keys |
dict | compact open-addressing hash table | insertion order (3.7+) | maps, memo tables, counting |
set / frozenset | open-addressing hash table | arbitrary | membership, dedup, set algebra |
collections.deque | doubly linked list of 64-slot blocks | by position | queues, sliding windows, BFS |
heapq | functions over a list | heap order | priority queues |
bisect | functions over a sorted list | sorted | binary search, "sorted list" |
collections.Counter, defaultdict, OrderedDict | dict subclasses | insertion order | counting, grouping, LRU |
array.array, bytes, bytearray | contiguous raw values | by index | compact numeric/byte storage |
str | immutable compact array of code points | by index | text |
list
| Operation | Complexity | Notes |
|---|---|---|
a[i], a[i] = x, len(a) | address arithmetic on the pointer array | |
a.append(x) | amortised | over-allocation about 12.5% (why) |
a.pop() | from the end | |
a.pop(0), a.pop(i) | shifts everything after i | |
a.insert(i, x) | insert(0, x) is the classic queue mistake; measured 44x slower than append at | |
del a[i], a.remove(x) | remove searches () then shifts () | |
x in a, a.index(x), a.count(x) | linear scan with == on every element | |
a[i:j] | copies pointers; a[:] is | |
del a[i:j], a[i:j] = b | shift the tail | |
a.extend(b), a += b | amortised | a = a + b is because it builds a new list |
a.sort(), sorted(a) | , stable | Timsort; on already-sorted or reverse-sorted input |
a.reverse() | in place; reversed(a) is a lazy iterator | |
min(a), max(a), sum(a) | ||
a * k | copies pointers; [[0] * m] * n aliases the same inner list times | |
a == b | element-wise | |
| iteration |
A list is a struct of 56 bytes holding its length, its allocated capacity and a pointer to a separate buffer of 8-byte object pointers. Every element is a pointer to a heap object, so a list of a million ints is 8 MB of pointers plus 28 MB of int objects. pop(0) is because the buffer always starts at index 0 — CPython does not keep a head offset the way deque does.
Timsort, the sort behind list.sort and sorted, is a stable adaptive merge sort: it finds already-ordered runs, extends short ones to a minimum length (32–64) with binary insertion sort, and merges runs with a galloping mode that skips ahead when one run dominates. The practical consequences: sorting nearly-sorted data is nearly linear; key= is called exactly once per element (the keys are precomputed, so an expensive key function costs calls, not ); reverse=True keeps stability, unlike reversing the result; and multi-key sorts can be done as successive stable sorts, least significant key first.
Gotchas. A list as a queue (pop(0)) is per dequeue — use deque. x in list inside a loop is the most common accidental in Python; convert to a set first. [[0] * m] * n creates references to one inner list; use a comprehension. list.remove(x) removes the first match by equality, not identity, and raises ValueError when absent.
tuple
Same index, slice and in costs as list; no mutation. A tuple stores its item pointers inline in the object (48 bytes + 8 per item), so it is slightly smaller than an equivalent list and is hashable when all its items are, which makes it the natural dict key and set element. Tuples of up to a modest size are cached by CPython's free lists, so creating and discarding small tuples is cheap. namedtuple and typing.NamedTuple add field names at no runtime cost.
dict
| Operation | Average | Amortised worst | Notes |
|---|---|---|---|
d[k], d[k] = v, k in d, d.get(k) | worst case is adversarial collisions | ||
del d[k], d.pop(k) | leaves a dummy entry; compacted on resize | ||
d.popitem() | removes the last inserted (LIFO) since 3.7 | ||
len(d) | |||
| iteration over keys, values, items | sequential scan of the entries array, insertion order | ||
d.copy(), dict(d) | |||
d.update(e), d | e | 3.9+ for the operator | ||
d.setdefault(k, v) | one lookup, not two | ||
next(iter(d)) | if many entries at the front were deleted |
CPython's dict is the compact dict described in the memory lesson: a sparse indices array probed with open addressing (random probing with a perturbation of the hash) and a dense entries array of (hash, key, value) in insertion order. Insertion order has been a language guarantee since Python 3.7. The table resizes when it is two-thirds full; deletions leave a dummy in indices and a hole in entries, which is why iteration after many deletions can be slower than until the next resize. Hashes of str and bytes are randomised per process (SipHash) since 3.3 to defeat hash-flooding attacks; int hashes are not (hash(x) == x for small ints, hash(-1) == -2).
Keys must be hashable: immutable built-ins, tuples of hashables, frozensets, and user objects (hashed by identity unless __hash__ and __eq__ are defined). 1, 1.0 and True are the same key because they are equal and hash equally.
Gotchas. Mutating a dict while iterating it raises RuntimeError; iterate over list(d) instead. d[k] on a missing key raises KeyError — use get, setdefault or defaultdict. Dict iteration is insertion order, not sorted order; sorted(d) is .
set and frozenset
| Operation | Average | Worst | Notes |
|---|---|---|---|
x in s, s.add(x), s.discard(x) | |||
s.remove(x) | raises KeyError if absent | ||
s | t, s.union(t) | |||
s & t | listed as worst | iterates the smaller, probes the larger | |
s - t | iterates s, probes t | ||
s ^ t | |||
s <= t, s.issubset(t) | |||
s.pop() | amortised | arbitrary element | |
| iteration | arbitrary order (hash order) |
A set is an open-addressing table of (hash, key) slots — not the compact two-array layout of dict — with a load factor of 3/5 and a probing sequence that first scans a few adjacent slots (linear probing within a cache line) before jumping. Measured: set(range(1000)) is 32,984 bytes, about 33 bytes per element. frozenset is the immutable, hashable twin; use it as a dict key or set element.
Gotchas. Sets are unordered: the iteration order of a set of ints is predictable (hash order) but the iteration order of a set of strings changes between runs because of hash randomisation. set of lists fails (unhashable) — convert inner lists to tuples. The membership is why "in on a list vs in on a set" is the single most valuable Python optimisation to know.
collections.deque
| Operation | Complexity | Notes |
|---|---|---|
append, appendleft, pop, popleft | the whole point | |
d[0], d[-1] | ||
d[i] in the middle | walks block by block; steps but still linear | |
len(d) | ||
x in d, d.remove(x), d.count(x) | ||
d.rotate(k) | ||
d.extend(it), d.extendleft(it) | extendleft reverses the order of the argument | |
deque(it, maxlen=m) | bounded; appending to a full deque discards from the other end |
A deque is a doubly linked list of fixed-size blocks (64 pointers each), with the two ends possibly partially filled. It is the correct queue for BFS and the correct bounded window (maxlen) for sliding-window problems. It is not a replacement for list when you need random access.
heapq
| Operation | Complexity | Notes |
|---|---|---|
heapq.heappush(h, x) | ||
heapq.heappop(h) | returns the smallest | |
h[0] | peek the smallest | |
heapq.heapify(a) | in place; faster than pushes () | |
heapq.heappushpop(h, x), heapq.heapreplace(h, x) | one sift instead of two | |
heapq.nlargest(k, it), nsmallest | key= supported; for near , sorted is faster | |
heapq.merge(*its) | lazy | sorted inputs, total items |
| decrease-key | not available | push a new entry and skip stale ones on pop |
heapq is a set of functions over a plain list kept in binary min-heap order (children of i at 2i + 1 and 2i + 2, no pointers at all). There is no max-heap: negate the priorities or wrap items in a class with a reversed __lt__. Items are compared with <, so pushing tuples compares them lexicographically. The standard tie-break idiom is to push (priority, counter, item) with an itertools.count() counter: it makes equal priorities pop in FIFO order and, more importantly, prevents the comparison from ever reaching item, which might not be orderable (two dicts, two Nones). Since there is no decrease-key, Dijkstra's algorithm in Python pushes duplicates and skips entries whose stored distance is stale — the "lazy deletion" pattern that appears again in Heaps & Priority Queues.
bisect
| Operation | Complexity | Notes |
|---|---|---|
bisect.bisect_left(a, x) | first index i with a[i] >= x; the C++ lower_bound | |
bisect.bisect_right(a, x) (alias bisect) | first index with a[i] > x; the C++ upper_bound | |
bisect.insort(a, x) | search then an list.insert shift | |
key= parameter | 3.10+; the key is applied to the array elements, not to x |
bisect turns a sorted list into a poor man's ordered set: lookup, floor (bisect_right(a, x) - 1), ceiling (bisect_left(a, x)) and range counting (bisect_right(hi) - bisect_left(lo)), with insertion because of the shift. For up to tens of thousands of elements that shift is a fast memmove and this beats anything you could write in pure Python; past that, a balanced tree is needed and the standard library does not have one. There is no built-in balanced BST or sorted map in Python. The third-party sortedcontainers package (SortedList, SortedDict, SortedSet) provides them — implemented, tellingly, as a list of sorted lists with bisect, not as a tree — and is what most people reach for; it is not available in most interview environments, so know the bisect idioms and the heap-based alternatives.
Counter, defaultdict, OrderedDict
| Operation | Complexity | Notes |
|---|---|---|
Counter(it) | a dict subclass; missing keys read as 0 | |
c.most_common(k) | uses heapq.nlargest; most_common() with no sorts, | |
c.update(it), c.subtract(it) | ||
c1 + c2, c1 - c2, c1 & c2, c1 | c2 | multiset algebra; drops non-positive counts | |
c.total() | 3.10+ | |
defaultdict(f)[k] | calls f() and inserts on a miss — reading a key inserts it | |
OrderedDict.move_to_end(k, last=True) | the LRU primitive | |
OrderedDict.popitem(last=False) | FIFO pop; plain dict.popitem is LIFO only |
Since plain dict became ordered, OrderedDict survives for move_to_end, popitem(last=False), and order-sensitive equality (OrderedDict equality compares order; dict equality does not). defaultdict(list) is the grouping idiom; defaultdict(int) the counting idiom when you do not need most_common.
array, bytes, bytearray
array.array('i') stores machine integers contiguously, 4 bytes each instead of 8 bytes of pointer plus 28 bytes of object; same operation costs as list. bytes is an immutable array of 8-bit values; bytearray is its mutable twin with list-like costs, including insert at the front. These are the right tools when memory is the bottleneck or when interfacing with binary protocols; for numeric work NumPy supersedes them.
str
Strings are immutable arrays of code points stored compactly (1, 2 or 4 bytes per character depending on the widest character). Indexing and len are ; slicing is ; s in t is worst case with a fast average (a two-way/Crochemore-Perrin search in recent versions); s + t allocates a new string of length . Building a string with += in a loop is in principle — CPython has an optimisation that mutates in place when the reference count is 1, but it is an implementation detail that PyPy does not share. Use ''.join(parts), which is , or io.StringIO.
sorted, key functions, functools.lru_cache
sorted(it, key=f, reverse=False) works on any iterable, returns a new list, calls f once per element and is stable. For sorting by several keys with mixed directions, either build a tuple key with negated numeric fields or sort twice, least-significant key first. functools.lru_cache(maxsize=128) memoises a function with a dict plus a circular doubly linked list for recency: per hit and per eviction; maxsize=None (or functools.cache) drops the list and is a plain dict. Arguments must be hashable — a list argument raises TypeError, so memoised recursions pass tuples or indices.
Java
Java's java.util collections are interface-driven: List, Deque, Queue, Set, Map, SortedMap/NavigableMap, each with two or three implementations that differ in exactly the ways this lesson is about. Everything stores object references, so primitives are boxed (int → Integer) on the way in, which costs a 16-byte object per element and dominates many measurements. Java 21 is assumed.
flowchart LR
subgraph LISTS["List / Deque"]
AL["ArrayList<br/>array"] ~~~ LL["LinkedList<br/>doubly linked"] ~~~ AD["ArrayDeque<br/>ring buffer"]
end
subgraph MAPS["Map"]
HM["HashMap<br/>chaining + treeify"] ~~~ LHM["LinkedHashMap<br/>+ order list"] ~~~ TM["TreeMap<br/>red-black tree"]
end
subgraph SETS["Set"]
HS["HashSet<br/>wraps HashMap"] ~~~ LHS["LinkedHashSet"] ~~~ TS["TreeSet<br/>wraps TreeMap"]
end
PQ["PriorityQueue<br/>binary heap in Object[]"]
Containers at a glance
| Container | Built on | Ordered? | Typical use |
|---|---|---|---|
ArrayList<E> | Object[] with 1.5x growth | by index | the default list |
LinkedList<E> | doubly linked nodes | by position | almost never — see ArrayDeque |
ArrayDeque<E> | circular Object[] | by position | stacks and queues |
HashMap<K,V> | Node[] chaining, treeified bins | no | the default map |
LinkedHashMap<K,V> | HashMap + doubly linked entries | insertion or access | predictable iteration, LRU |
TreeMap<K,V> | red-black tree | sorted by key | floor/ceiling/range queries |
HashSet, LinkedHashSet, TreeSet | the corresponding map with dummy values | as above | membership |
PriorityQueue<E> | binary heap in Object[] | heap order | min-heap by default |
String / StringBuilder | byte[] (Latin-1 or UTF-16) | by index | text |
int[], long[], … | raw primitive arrays | by index | when boxing is unaffordable |
ArrayList, LinkedList, ArrayDeque
| Operation | ArrayList | LinkedList | ArrayDeque |
|---|---|---|---|
get(i), set(i, x) | (walks from the nearer end) | not supported | |
add(x) at the end | amortised | amortised (addLast) | |
add(0, x) / addFirst(x) | amortised | ||
add(i, x), remove(int i) | to find + to link | not supported | |
remove(Object o), contains, indexOf | |||
removeFirst() / pollFirst() | via remove(0) | ||
removeLast() / pollLast() | |||
size() | |||
| iteration | , pointer chasing | ||
sort(cmp) | stable | (copies to array) | not a List |
subList(a, b) | view | view | not supported |
toArray() | |||
null elements | allowed | allowed | not allowed |
ArrayList grows by 50% (oldCapacity >> 1, verified in OpenJDK's grow), starting from a default capacity of 10 on first add; new ArrayList<>(n) pre-sizes. LinkedList implements both List and Deque but pays a 24-byte-plus-header node per element and a pointer chase per step. The Javadoc of ArrayDeque says it plainly: it "is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue". ArrayDeque is a power-of-two ring buffer with head and tail indices; it rejects null because null is the return value of poll and peek on an empty deque.
Gotchas. list.remove(int index) and list.remove(Object o) are different overloads: on a List<Integer>, remove(1) removes index 1 and remove(Integer.valueOf(1)) removes the value 1. Arrays.asList(arr) is a fixed-size view backed by the array — add throws. List.of(...) is immutable and rejects null. subList views throw ConcurrentModificationException if the parent changes. Modifying a list while iterating it with a for-each loop throws; use an explicit Iterator and it.remove(), or removeIf.
HashMap, LinkedHashMap, TreeMap
| Operation | HashMap | LinkedHashMap | TreeMap |
|---|---|---|---|
get, put, remove, containsKey | average, worst in a treeified bin | same as HashMap | guaranteed |
containsValue | |||
| iteration | in key order | ||
firstKey, lastKey | — | — | |
floorKey, ceilingKey, lowerKey, higherKey | — | — | |
headMap, tailMap, subMap | — | — | to create the view; iteration |
pollFirstEntry, pollLastEntry | — | — | |
getOrDefault, merge, compute, computeIfAbsent | average | same | |
null keys | one allowed | one allowed | not allowed (natural ordering) |
HashMap is a power-of-two Node[] table with separate chaining; default initial capacity 16, load factor 0.75; a bin whose chain reaches 8 is converted to a red-black tree when the table has at least 64 slots and converts back below 6 (constants verified in OpenJDK HashMap.java). The treeification bounds the worst case under hash flooding at if keys are Comparable; otherwise tie-breaking falls back to identity hash codes. Iteration order is unspecified and changes when the table resizes — never depend on it.
LinkedHashMap threads a doubly linked list through the entries for insertion-order iteration; the constructor new LinkedHashMap<>(cap, 0.75f, true) switches to access order, and overriding removeEldestEntry makes it a complete LRU cache in about five lines. TreeMap is a red-black tree with the full NavigableMap API; keys are compared with compareTo or the supplied Comparator, and two keys that compare equal are the same key even if equals says otherwise.
Gotchas. Mutable keys: if you mutate an object after using it as a HashMap key, its hash changes and the entry is lost. Overriding equals without hashCode breaks HashMap and HashSet. TreeMap with a Comparator that is inconsistent with equals (e.g. comparing only one field) silently merges distinct keys. map.get(k) == null cannot distinguish "absent" from "mapped to null" — use containsKey or getOrDefault.
HashSet, LinkedHashSet, TreeSet
Each is the corresponding map with a shared dummy value, so the costs are identical: average add/contains/remove for HashSet, insertion-order iteration for LinkedHashSet, and add/contains/remove/floor/ceiling/lower/higher/first/last/pollFirst plus headSet/tailSet/subSet views for TreeSet. Bulk operations (addAll, retainAll, removeAll) are probes for hash sets — except removeAll(c) on a set larger than c iterates the set and calls c.contains, which is if c is a List.
PriorityQueue
| Operation | Complexity | Notes |
|---|---|---|
offer(x) / add(x) | ||
poll() | removes the least element | |
peek() | ||
new PriorityQueue<>(collection) | heapify | |
remove(Object o), contains(o) | linear scan of the array | |
size() | ||
| iteration | , not in sorted order | array order |
| decrease-key | not available | re-insert and skip stale entries, or use a TreeSet of (key, id) |
A binary min-heap in an Object[] with 1.5x–2x growth. Max-heap: new PriorityQueue<>(Collections.reverseOrder()) or Comparator.reverseOrder(). Elements must be mutually comparable; null is rejected. Because remove(Object) is , "update a task's priority" is done by inserting a fresh entry and ignoring the old one when it surfaces, or by using a TreeSet with a composite comparator when you really need deletion.
Arrays.sort, Collections.sort, List.sort
| Call | Algorithm | Stable? | Complexity |
|---|---|---|---|
Arrays.sort(int[]), other primitives | Dual-Pivot Quicksort (Yaroslavskiy, Bentley, Bloch) | not applicable | "on all data sets" per the Javadoc (heap-sort fallback since JDK 14) |
Arrays.sort(Object[]), Arrays.sort(T[], Comparator) | TimSort (adapted from Python's) | yes | ; about compares on nearly sorted input |
Collections.sort(list), list.sort(cmp) | copies to an array, TimSort, writes back | yes | |
Arrays.parallelSort | parallel merge sort over sort | yes for objects | work |
The stability consequence: you can sort an Integer[] or a list of records by one key and then by another and get a correct multi-key order, but you cannot do that with an int[] — primitives have no identity, so stability is meaningless, and to sort indices by a key you must box or sort an Integer[] of indices with a comparator. A classic contest gotcha: Arrays.sort(int[]) on adversarial input was before JDK 14; since then the fallback to heap sort removes the worst case. Sorting an int[] is several times faster than sorting an Integer[] because of boxing and pointer chasing.
String, StringBuilder, boxing, Integer cache, comparators
String is immutable; s + t allocates; s += t in a loop is (the compiler turns a single expression's + chain into one StringBuilder or invokedynamic concat, but not a loop). StringBuilder.append is amortised with the same 2x-ish growth as any dynamic array; toString() copies once. s.charAt(i) is ; s.substring(a, b) copies since Java 7u6 (); s.contains/indexOf is worst case; String.hashCode is cached after the first call.
Autoboxing turns int into Integer whenever a primitive meets a generic: List<Integer>, Map<Integer, Integer>, PriorityQueue<Integer>. Each box is a heap allocation (unless cached), and each unbox a pointer chase; collections of a million boxed ints are typically 3–5x slower than primitive arrays, which is why hot loops in competitive Java use int[] and hand-rolled structures. Integer.valueOf caches −128 to 127, so Integer a = 127, b = 127; a == b is true while the same with 128 is false — always equals boxed values.
Comparator.comparing(Person::score), .thenComparing(Person::name), .reversed() and Comparator.comparingInt build comparators declaratively; comparingInt avoids boxing the key. A comparator must be a consistent total order, or sort may throw IllegalArgumentException: Comparison method violates its general contract. Never implement compare as a - b on ints that can overflow; use Integer.compare(a, b).
C++ STL
The C++ standard specifies the complexity of every container operation and, in effect, the data structure behind it: vector must be contiguous, map must offer logarithmic ordered operations with stable iterators (a balanced tree), unordered_map must expose buckets with stable element references (node-based chaining). Zero overhead is the design goal: an std::vector<int> is 24 bytes of header and exactly 4 bytes per element. The flip side is that the costs are yours to manage: iterator invalidation, copies versus moves, and the fact that std::sort is not stable. C++20 is assumed.
Containers at a glance
| Container | Built on | Ordered? | Typical use |
|---|---|---|---|
vector<T> | contiguous dynamic array (2x libstdc++, 1.5x MSVC) | by index | the default |
array<T, N> | fixed-size contiguous | by index | small fixed buffers, no heap |
deque<T> | blocks + index map | by index | queues, both-end growth |
list<T>, forward_list<T> | doubly / singly linked nodes | by position | splicing, stable addresses |
set, map, multiset, multimap | red-black tree | sorted | ordered queries |
unordered_set, unordered_map (+ multi) | chaining, node per element | no | hashing |
priority_queue<T> | heap over a vector | heap order | max-heap by default |
stack<T>, queue<T> | adaptors over deque by default | LIFO / FIFO | |
string | contiguous char with SSO | by index | text |
bitset<N> | fixed array of words | by index | flags, subsets |
vector, array, deque, list, forward_list
| Operation | vector | deque | list | forward_list |
|---|---|---|---|---|
v[i], at(i) | (two indirections) | — | — | |
push_back, emplace_back | amortised | amortised | — | |
push_front | — (insert(begin()) is ) | amortised | ||
pop_back, pop_front | / — | — / | ||
insert(it, x), erase(it) | (distance to end) | after a given position | ||
size() | not provided | |||
find (via std::find) | ||||
reserve(n), capacity() | yes | no | no | no |
splice | — | — | whole list or one element; for a range from another list | similar |
sort | std::sort | std::sort | member sort() merge sort, stable | member sort() |
| iterator/reference stability on push_back | invalidated on reallocation | iterators invalidated, references stable | stable | stable |
vector is the answer unless you have a specific reason. reserve(n) when you know the size; emplace_back(args...) constructs in place and avoids a temporary; v.erase(std::remove_if(...), v.end()) (or C++20 std::erase_if) removes elements in one pass instead of repeated erases. vector<bool> is a bit-packed specialisation whose operator[] returns a proxy, not a bool&; use vector<char> or bitset when you need references. deque gives indexing and growth at both ends by storing fixed-size blocks and a map of block pointers, at the cost of worse locality than vector. list exists for splicing and address stability; Stroustrup's experiment is why it is rarely the right choice for anything else.
set, map, multiset, multimap
| Operation | Complexity | Notes |
|---|---|---|
insert, emplace, erase(key), find, count | erase(key) on a multiset removes all equal keys | |
lower_bound(k) | first element — the ceiling | |
upper_bound(k) | first element ; floor is --upper_bound(k) if not begin() | |
equal_range(k) | pair of the two above | |
begin(), rbegin() | min and max; *rbegin() is the max | |
erase(iterator) | amortised | the iterator is already the node |
m[k] | inserts a default-constructed value if absent | |
m.at(k) | throws out_of_range if absent | |
extract, merge (C++17) | per node | move nodes between containers without reallocation |
| iteration | sorted order | |
insert(hint, x) | amortised if the hint is right |
A red-black tree in every major implementation (the standard requires balanced-tree complexities and stable iterators). Comparison uses < or a supplied comparator; equivalence is !(a < b) && !(b < a), so a comparator that ignores a field merges keys. std::set::find is while std::find(s.begin(), s.end(), x) is — a frequent mistake. Use multiset as a sorted multiset with removal of one copy via erase(find(x)) — a common sliding-window-median tool.
unordered_set, unordered_map
| Operation | Average | Worst | Notes |
|---|---|---|---|
insert, emplace, erase(key), find, count, contains (C++20) | |||
m[k] | inserts default value if absent | ||
reserve(n), rehash(b) | call reserve up front to avoid repeated rehashing | ||
bucket_count(), load_factor(), max_load_factor(f) | default max load factor 1.0 | ||
| iteration |
Node-based chaining with a bucket array, as the standard effectively requires. Each element is a heap allocation, so it is slower per lookup than a flat open-addressing table (measured: 6–60 ns per lookup across – on the test machine, versus 80–900 ns for std::map — still a 13x–20x win over the tree). For user-defined keys you supply a hash as a functor type (struct Hash { size_t operator()(const Key&) const; }) and an equality; std::hash exists for arithmetic types, pointers, string and a few others but not for pair or tuple.
The anti-hash caveat
std::hash<int> in libstdc++ is the identity function and the bucket count follows a known sequence of primes. Competitive programming judges contain tests that make every key land in one bucket, turning unordered_map into an -per-operation list and a TLE. Use a custom hash with a random seed (the well-known splitmix64 "custom hash" from the Codeforces blog "Blowing up unordered_map"), or use std::map, or sort and binary-search. In production, keys from untrusted input deserve the same thought.
priority_queue, stack, queue
std::priority_queue<T> is a max-heap by default (it uses std::less); for a min-heap write std::priority_queue<T, std::vector<T>, std::greater<T>>. push/emplace/pop are , top is , construction from a range is (make_heap). There is no decrease-key and no iteration; the lazy-deletion idiom applies. std::stack and std::queue are adaptors over std::deque by default (you can supply vector for stack), with push/pop/top/front/back. The underlying std::make_heap/push_heap/pop_heap algorithms are available directly if you want to keep the heap in your own vector.
string and bitset
std::string is a contiguous, mutable, null-terminated byte array with small-string optimisation: strings up to 15 characters (libstdc++ and MSVC; 22 in libc++) live inside the 32-byte object with no heap allocation. operator[] and size are ; += and push_back are amortised; s + t is ; substr copies ; find is worst case; std::string_view gives substrings without copying. std::bitset<N> is a fixed-size array of words with count, any, bitwise operators and shifts, and test/set/flip — the tool for subset DP and bit-parallel tricks (Bit Manipulation).
Algorithms: sort, stable_sort, nth_element, partial_sort
| Algorithm | What it does | Complexity | Stable? |
|---|---|---|---|
std::sort | introsort (quicksort + heapsort fallback + insertion sort for small ranges) | worst case (guaranteed since C++11) | no |
std::stable_sort | merge sort with a buffer | with memory; if allocation fails | yes |
std::nth_element | places the -th smallest at index , partitions around it | average (introselect) | — |
std::partial_sort | sorts the first of | no | |
std::is_sorted, std::binary_search, std::lower_bound, std::upper_bound | on sorted ranges | / | — |
std::ranges::sort etc. (C++20) | same algorithms with projections | same | same |
std::sort requires random-access iterators (so not list — use list::sort). Sorting pairs or tuples uses their lexicographic <, which is often exactly the multi-key sort you want; for anything else pass a lambda. Comparators must be a strict weak ordering — <= instead of < is undefined behaviour and does crash in practice.
Iterator invalidation
| Container | insert / push_back / emplace | erase |
|---|---|---|
vector | all iterators, pointers and references invalidated if capacity is exceeded; otherwise only those at or after the insertion point | at and after the erased element (including end()) |
deque | all iterators invalidated; references stay valid for push_front/push_back; an insert in the middle invalidates references too | at the ends: only the erased; in the middle: all |
list, forward_list | nothing | only the erased |
set, map, multi* | nothing | only the erased |
unordered_* | all iterators if a rehash occurs; references and pointers to elements stay valid | only the erased |
string | like vector | like vector |
The canonical bug: for (auto it = v.begin(); it != v.end(); ++it) if (cond) v.erase(it); skips an element and eventually runs off the end. Write it = v.erase(it) and do not increment on that branch, or use std::erase_if. The other one: keeping a reference into a vector across a push_back.
pair, tuple, emplace_back, reserve
std::pair<A, B> and std::tuple<...> compare lexicographically, hash nowhere by default (write your own or combine std::hash of the parts), and unpack with structured bindings: auto& [k, v] = *it;. emplace_back(a, b) constructs the element in place from its constructor arguments; push_back({a, b}) constructs a temporary and moves it — the difference matters for large or non-movable types. reserve(n) on a vector is the single cheapest optimisation in C++ when you know the final size, and it also pins element addresses for the lifetime of the fill.
JavaScript and TypeScript
JavaScript has one sequence type (Array), two keyed collections (Map, Set), their weak variants, typed arrays, and nothing else: no heap, no deque, no sorted map. The ECMAScript specification defines behaviour but mostly not complexity; the costs below are what V8 (Node, Chrome) delivers, and where the spec requires something (stable sort, insertion-order Map), the text says so. TypeScript adds types, not data structures, so everything here applies to both.
Containers at a glance
| Container | Built on (V8) | Ordered? | Typical use |
|---|---|---|---|
Array | contiguous elements store with elements kinds, or a dictionary when sparse | by index | everything sequential |
Map, Set | insertion-ordered hash table (OrderedHashTable) | insertion | keyed lookup, dedup |
WeakMap, WeakSet | ephemeron table, object keys only | not iterable | caches keyed by objects |
Int32Array, Float64Array, … | raw ArrayBuffer | by index | numeric work, binary data |
plain object {} | hidden classes + optional dictionary mode | string keys, mostly insertion order | records; avoid as a general map |
string | immutable; flat or rope (ConsString) | by index (UTF-16 code units) | text |
Array
| Operation | Complexity | Notes |
|---|---|---|
a[i], a[i] = x, a.length | for packed arrays; dictionary-mode arrays are hash lookups | |
push, pop | amortised | growth 1.5x + 16 (source) |
shift, unshift | V8 can sometimes "left-trim" to make shift cheap; never rely on it | |
indexOf, includes, find, findIndex | includes uses SameValueZero (finds NaN); indexOf does not | |
splice(i, k, ...items) | shifts the tail | |
slice(i, j) | copy | |
concat, spread [...a, ...b] | ||
sort(cmp) | , stable (required since ES2019; V8 7.0 uses TimSort) | default comparator converts to strings |
reverse | in place | |
map, filter, forEach, reduce | allocate a new array except forEach/reduce | |
flat(depth) | ||
at(-1) | ES2022 | |
delete a[i] | but leaves a hole | the array becomes holey / dictionary mode |
new Array(n) | creates a holey array of length |
Arrays in V8 are contiguous stores tagged with an elements kind (packed or holey; Smi, double or generic), which the JIT uses to emit fast code. Holes (new Array(n), delete, writing past length) and very sparse indices push an array toward slower representations, including a hash-table "dictionary mode". Keep arrays dense and type-homogeneous; create them with Array.from({ length: n }, () => 0), new Array(n).fill(0), or a typed array.
The default sort compares strings
[1, 10, 2].sort() returns [1, 10, 2], because without a comparator every element is converted to a string and compared lexicographically — "10" < "2". Always pass (a, b) => a - b for numbers (safe when no difference overflows; otherwise use explicit comparisons). This single trap has failed more JavaScript interviews than any algorithm.
Map, Set, WeakMap, objects as maps
| Operation | Complexity | Notes |
|---|---|---|
map.get, set, has, delete | average | keys compared with SameValueZero: NaN equals NaN, +0 equals -0, objects by identity |
map.size | a property, not a method | |
iteration (for…of, keys(), values(), entries()) | insertion order, guaranteed by the spec | |
new Map(iterable) | ||
set.has, add, delete | average | |
set.union, intersection, difference | ES2025 set methods; check runtime support | |
WeakMap.get/set/has/delete | average | object keys only, not iterable, no size; entries vanish when the key is collected |
Map and Set are the correct general-purpose hash containers. A plain object used as a map has string-and-symbol keys only (numbers are stringified: obj[1] and obj["1"] collide), inherits toString, constructor and friends from its prototype (so "constructor" in obj is true), and can be poisoned by a key named __proto__. Objects win only for small fixed-shape records, where V8's hidden classes make property access a single offset load. Object.keys order is: integer-like keys ascending, then string keys in insertion order, then symbols — not pure insertion order.
Typed arrays
Int8Array … Float64Array, BigInt64Array are fixed-length views over an ArrayBuffer of raw bytes: index, no holes, no boxing, no push. subarray(i, j) is an view sharing memory; slice(i, j) is an copy. They are the right tool for numeric algorithms, sieves, DP tables and anything measured in millions of numbers: an Int32Array of a million elements is 4 MB, a plain array of the same Smis is 4–8 MB and a plain array of doubles that have become heap numbers is far more. Sorting a typed array with .sort() and no comparator sorts numerically — unlike Array.
What is missing: heap, deque, sorted map
There is no built-in priority queue, deque or sorted map. In interviews you are expected to write a binary heap in about 40 lines (the TypeScript tab of the heap translation below is a complete one), to implement a deque as a ring buffer or as two stacks when shift would be in a hot loop, and to keep a sorted array with binary search when you need floor/ceiling (insertion is via splice, acceptable up to tens of thousands of elements). For production, small libraries exist; for contests, know the idioms.
Strings, join, numbers and BigInt
Strings are immutable sequences of UTF-16 code units; s.length counts code units, so an emoji is 2. s[i] and charCodeAt are ; slice/substring are ; indexOf/includes are worst case. Repeated s += piece is not quadratic in V8 because concatenation builds a rope (ConsString) that is flattened lazily — but it is engine-specific, and parts.push(piece); parts.join("") is the portable idiom that is everywhere.
Numbers are IEEE-754 doubles: integers are exact only up to (Number.MAX_SAFE_INTEGER); past that, a + 1 === a can be true and hash-style arithmetic silently breaks. BigInt (123n) is arbitrary precision but slower, cannot mix with Number in arithmetic, and JSON.stringify rejects it. Bitwise operators coerce to 32-bit signed integers: (a + b) >> 1 overflows for large sums — use Math.floor((a + b) / 2) or lo + ((hi - lo) >> 1); x | 0 truncates to int32; x >>> 0 to uint32. Math.max(...arr) spreads the array as arguments and throws RangeError for arrays of a few hundred thousand elements — use a loop or reduce.
Translation tables
The same operation in all four languages. Each code group is a complete, runnable program with asserts, and the four tabs use the same test data.
Priority queue: push, pop, FIFO tie-break, max-heap
| Python | Java | C++ | JavaScript | |
|---|---|---|---|---|
| Min-heap type | list + heapq | PriorityQueue<T> | priority_queue<T, vector<T>, greater<T>> | write a class |
| Push / pop | heappush, heappop | offer, poll | push, pop (+ top) | push, pop |
| Max-heap | negate keys | Collections.reverseOrder() | default priority_queue<T> | flip comparator |
| Heapify | heapify(a) | new PriorityQueue<>(coll) | make_heap / range constructor | build then sift down |
| Tie-break | (prio, counter, item) | thenComparingLong(seq) | tuple<int, long, T> | comparator on seq |
| Decrease-key | none: lazy deletion | none | none | none |
import heapq
from itertools import count
def main() -> None:
tasks = [("write", 3), ("read", 1), ("exec", 2), ("read-again", 1)]
heap: list[tuple[int, int, str]] = []
tie = count() # FIFO among equal priorities
for name, priority in tasks:
heapq.heappush(heap, (priority, next(tie), name))
order = [heapq.heappop(heap)[2] for _ in range(len(heap))]
assert order == ["read", "read-again", "exec", "write"], order
nums = [5, 1, 9, 3, 7]
heapq.heapify(nums) # O(n), in place
assert nums[0] == 1
assert heapq.nlargest(2, [5, 1, 9, 3, 7]) == [9, 7]
# max-heap idiom: negate priorities
mx = [-x for x in [5, 1, 9]]
heapq.heapify(mx)
assert -heapq.heappop(mx) == 9
print("heap ok")
if __name__ == "__main__":
main()
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class HeapDemo {
record Task(int priority, long seq, String name) {}
public static void main(String[] args) {
String[][] tasks = {{"write", "3"}, {"read", "1"}, {"exec", "2"}, {"read-again", "1"}};
PriorityQueue<Task> pq = new PriorityQueue<>(
Comparator.comparingInt(Task::priority).thenComparingLong(Task::seq)); // FIFO among ties
long seq = 0;
for (String[] t : tasks) pq.add(new Task(Integer.parseInt(t[1]), seq++, t[0]));
List<String> order = new ArrayList<>();
while (!pq.isEmpty()) order.add(pq.poll().name());
if (!order.equals(List.of("read", "read-again", "exec", "write"))) throw new AssertionError(order);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.addAll(List.of(5, 1, 9));
if (maxHeap.poll() != 9) throw new AssertionError();
// PriorityQueue(Collection) heapifies in O(n); remove(Object) is O(n), there is no decrease-key
PriorityQueue<Integer> fromList = new PriorityQueue<>(List.of(5, 1, 9, 3, 7));
if (fromList.peek() != 1) throw new AssertionError();
System.out.println("heap ok");
}
}
#include <cassert>
#include <functional>
#include <queue>
#include <string>
#include <tuple>
#include <vector>
#include <cstdio>
int main() {
using Task = std::tuple<int, long, std::string>; // (priority, seq, name)
std::priority_queue<Task, std::vector<Task>, std::greater<Task>> pq; // min-heap
std::vector<std::pair<std::string, int>> tasks = {{"write", 3}, {"read", 1}, {"exec", 2}, {"read-again", 1}};
long seq = 0;
for (auto& [name, prio] : tasks) pq.emplace(prio, seq++, name);
std::vector<std::string> order;
while (!pq.empty()) { order.push_back(std::get<2>(pq.top())); pq.pop(); }
assert((order == std::vector<std::string>{"read", "read-again", "exec", "write"}));
std::priority_queue<int> max_heap; // max-heap by default
for (int x : {5, 1, 9}) max_heap.push(x);
assert(max_heap.top() == 9);
std::vector<int> v = {5, 1, 9, 3, 7};
std::make_heap(v.begin(), v.end(), std::greater<int>()); // O(n) heapify, min-heap
assert(v.front() == 1);
std::printf("heap ok\n");
return 0;
}
import assert from "node:assert/strict";
class MinHeap<T> {
private a: T[] = [];
private readonly less: (x: T, y: T) => boolean;
constructor(less: (x: T, y: T) => boolean) { this.less = less; } // no parameter properties: Node strips types only
get size(): number { return this.a.length; }
peek(): T | undefined { return this.a[0]; }
push(x: T): void {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) { // sift up
const p = (i - 1) >> 1;
if (!this.less(a[i], a[p])) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop(): T | undefined {
const a = this.a;
if (a.length === 0) return undefined;
const top = a[0];
const last = a.pop() as T;
if (a.length > 0) {
a[0] = last;
let i = 0;
for (;;) { // sift down
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(a[l], a[m])) m = l;
if (r < a.length && this.less(a[r], a[m])) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
function main(): void {
type Task = { priority: number; seq: number; name: string };
const tasks: [string, number][] = [["write", 3], ["read", 1], ["exec", 2], ["read-again", 1]];
const pq = new MinHeap<Task>((x, y) => x.priority !== y.priority ? x.priority < y.priority : x.seq < y.seq);
tasks.forEach(([name, priority], seq) => pq.push({ priority, seq, name }));
const order: string[] = [];
while (pq.size > 0) order.push(pq.pop()!.name);
assert.deepEqual(order, ["read", "read-again", "exec", "write"]);
const maxHeap = new MinHeap<number>((x, y) => x > y); // flip the comparator for a max-heap
[5, 1, 9].forEach((x) => maxHeap.push(x));
assert.equal(maxHeap.pop(), 9);
console.log("heap ok");
}
main();
Ordered map: floor, ceiling, range
| Python | Java | C++ | JavaScript | |
|---|---|---|---|---|
| Structure | sorted list + bisect (insert ) | TreeMap | std::map | sorted array + binary search |
| Ceiling (first key ) | bisect_left | ceilingKey(k) | lower_bound(k) | hand-written lowerBound |
| Floor (last key ) | bisect_right(k) - 1 | floorKey(k) | prev(upper_bound(k)) | upperBound(k) - 1 |
| Strict versions | bisect_right / bisect_left - 1 | higherKey, lowerKey | upper_bound, prev(lower_bound) | same idea |
| Range | a[bisect_left(lo):bisect_right(hi)] | subMap(lo, true, hi, true) | lower_bound(lo) … upper_bound(hi) | slice(lowerBound(lo), upperBound(hi)) |
| Min / max | a[0], a[-1] | firstKey, lastKey | begin(), rbegin() | a[0], a.at(-1) |
import bisect
class SortedDict:
"""Sorted keys in a list + parallel values. Lookup O(log n); insert O(n) because of the shift."""
def __init__(self) -> None:
self.keys: list[int] = []
self.vals: list[str] = []
def put(self, k: int, v: str) -> None:
i = bisect.bisect_left(self.keys, k)
if i < len(self.keys) and self.keys[i] == k:
self.vals[i] = v
else:
self.keys.insert(i, k)
self.vals.insert(i, v)
def floor_key(self, k: int) -> int | None: # largest key <= k
i = bisect.bisect_right(self.keys, k) - 1
return self.keys[i] if i >= 0 else None
def ceiling_key(self, k: int) -> int | None: # smallest key >= k
i = bisect.bisect_left(self.keys, k)
return self.keys[i] if i < len(self.keys) else None
def range_keys(self, lo: int, hi: int) -> list[int]: # keys in [lo, hi]
return self.keys[bisect.bisect_left(self.keys, lo):bisect.bisect_right(self.keys, hi)]
def main() -> None:
m = SortedDict()
for k, v in [(30, "c"), (10, "a"), (40, "d"), (20, "b")]:
m.put(k, v)
assert m.keys == [10, 20, 30, 40]
assert m.floor_key(25) == 20 and m.ceiling_key(25) == 30
assert m.floor_key(30) == 30 and m.ceiling_key(30) == 30
assert m.floor_key(5) is None and m.ceiling_key(45) is None
assert m.range_keys(15, 35) == [20, 30]
print("ordered map ok")
if __name__ == "__main__":
main()
import java.util.List;
import java.util.TreeMap;
public class OrderedMapDemo {
public static void main(String[] args) {
TreeMap<Integer, String> m = new TreeMap<>(); // red-black tree, O(log n) everything
m.put(30, "c"); m.put(10, "a"); m.put(40, "d"); m.put(20, "b");
if (!m.keySet().stream().toList().equals(List.of(10, 20, 30, 40))) throw new AssertionError();
if (m.floorKey(25) != 20 || m.ceilingKey(25) != 30) throw new AssertionError();
if (m.floorKey(30) != 30 || m.ceilingKey(30) != 30) throw new AssertionError();
if (m.floorKey(5) != null || m.ceilingKey(45) != null) throw new AssertionError();
// subMap(lo, inclusive, hi, inclusive) is a live view, O(log n) to build
if (!m.subMap(15, true, 35, true).keySet().stream().toList().equals(List.of(20, 30))) throw new AssertionError();
// lowerKey/higherKey are the strict versions; firstKey/lastKey/pollFirstEntry are O(log n)
if (m.lowerKey(30) != 20 || m.higherKey(30) != 40) throw new AssertionError();
System.out.println("ordered map ok");
}
}
#include <cassert>
#include <cstdio>
#include <map>
#include <optional>
#include <string>
#include <vector>
std::optional<int> floor_key(const std::map<int, std::string>& m, int k) { // largest key <= k
auto it = m.upper_bound(k); // first key > k
if (it == m.begin()) return std::nullopt;
return std::prev(it)->first;
}
std::optional<int> ceiling_key(const std::map<int, std::string>& m, int k) { // smallest key >= k
auto it = m.lower_bound(k); // first key >= k
if (it == m.end()) return std::nullopt;
return it->first;
}
int main() {
std::map<int, std::string> m{{30, "c"}, {10, "a"}, {40, "d"}, {20, "b"}}; // red-black tree
std::vector<int> keys;
for (auto& [k, v] : m) keys.push_back(k);
assert((keys == std::vector<int>{10, 20, 30, 40}));
assert(floor_key(m, 25) == 20 && ceiling_key(m, 25) == 30);
assert(floor_key(m, 30) == 30 && ceiling_key(m, 30) == 30);
assert(!floor_key(m, 5).has_value() && !ceiling_key(m, 45).has_value());
std::vector<int> in_range; // keys in [15, 35]
for (auto it = m.lower_bound(15); it != m.upper_bound(35); ++it) in_range.push_back(it->first);
assert((in_range == std::vector<int>{20, 30}));
std::printf("ordered map ok\n");
return 0;
}
import assert from "node:assert/strict";
/** Sorted parallel arrays. get/floor/ceiling O(log n); set of a new key O(n) because of the splice. */
class SortedMap<V> {
private keys: number[] = [];
private vals: V[] = [];
private lowerBound(k: number): number { // first index with keys[i] >= k
let lo = 0, hi = this.keys.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (this.keys[mid] < k) lo = mid + 1; else hi = mid;
}
return lo;
}
private upperBound(k: number): number { // first index with keys[i] > k
let lo = 0, hi = this.keys.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (this.keys[mid] <= k) lo = mid + 1; else hi = mid;
}
return lo;
}
set(k: number, v: V): void {
const i = this.lowerBound(k);
if (this.keys[i] === k) { this.vals[i] = v; return; }
this.keys.splice(i, 0, k);
this.vals.splice(i, 0, v);
}
floorKey(k: number): number | undefined {
const i = this.upperBound(k) - 1;
return i >= 0 ? this.keys[i] : undefined;
}
ceilingKey(k: number): number | undefined {
const i = this.lowerBound(k);
return i < this.keys.length ? this.keys[i] : undefined;
}
rangeKeys(lo: number, hi: number): number[] {
return this.keys.slice(this.lowerBound(lo), this.upperBound(hi));
}
allKeys(): number[] { return this.keys.slice(); }
}
function main(): void {
const m = new SortedMap<string>();
for (const [k, v] of [[30, "c"], [10, "a"], [40, "d"], [20, "b"]] as [number, string][]) m.set(k, v);
assert.deepEqual(m.allKeys(), [10, 20, 30, 40]);
assert.equal(m.floorKey(25), 20);
assert.equal(m.ceilingKey(25), 30);
assert.equal(m.floorKey(30), 30);
assert.equal(m.ceilingKey(30), 30);
assert.equal(m.floorKey(5), undefined);
assert.equal(m.ceilingKey(45), undefined);
assert.deepEqual(m.rangeKeys(15, 35), [20, 30]);
console.log("ordered map ok");
}
main();
Deque at both ends, frequency count, stable sort by key
| Python | Java | C++ | JavaScript | |
|---|---|---|---|---|
| Deque | collections.deque | ArrayDeque | std::deque | none; ring buffer or two stacks |
| Push / pop front | appendleft, popleft | addFirst, pollFirst | push_front, pop_front | unshift, shift () |
| Frequency count | Counter(it) | map.merge(k, 1, Integer::sum) | ++freq[k] | m.set(k, (m.get(k) ?? 0) + 1) |
| Stable sort by key | sorted(a, key=f) | list.sort(Comparator.comparing(f)) | std::stable_sort with a lambda | a.sort((x, y) => ...) |
| Sort descending stably | reverse=True | .reversed() | comparator with > | y - x |
from collections import Counter, deque
def main() -> None:
dq: deque[int] = deque()
dq.append(1); dq.append(2); dq.appendleft(0) # O(1) at both ends
assert list(dq) == [0, 1, 2]
assert dq.popleft() == 0 and dq.pop() == 2
words = ["b", "a", "c", "a", "b", "a"]
freq = Counter(words) # dict subclass, O(n)
assert freq["a"] == 3 and freq["b"] == 2 and freq["c"] == 1
assert freq.most_common(1) == [("a", 3)]
people = [("ann", 90), ("bob", 85), ("cat", 90), ("dan", 85)]
by_score = sorted(people, key=lambda p: -p[1]) # Timsort is stable: ann before cat, bob before dan
assert [p[0] for p in by_score] == ["ann", "cat", "bob", "dan"]
print("translation ok")
if __name__ == "__main__":
main()
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class TranslationDemo {
record Person(String name, int score) {}
public static void main(String[] args) {
ArrayDeque<Integer> dq = new ArrayDeque<>(); // ring buffer, O(1) both ends, no nulls
dq.addLast(1); dq.addLast(2); dq.addFirst(0);
if (!new ArrayList<>(dq).equals(List.of(0, 1, 2))) throw new AssertionError();
if (dq.pollFirst() != 0 || dq.pollLast() != 2) throw new AssertionError();
Map<String, Integer> freq = new HashMap<>();
for (String w : List.of("b", "a", "c", "a", "b", "a")) freq.merge(w, 1, Integer::sum);
if (freq.get("a") != 3 || freq.get("b") != 2 || freq.get("c") != 1) throw new AssertionError();
List<Person> people = new ArrayList<>(List.of(new Person("ann", 90), new Person("bob", 85),
new Person("cat", 90), new Person("dan", 85)));
people.sort(Comparator.comparingInt(Person::score).reversed()); // List.sort is stable (TimSort)
List<String> names = people.stream().map(Person::name).toList();
if (!names.equals(List.of("ann", "cat", "bob", "dan"))) throw new AssertionError(names);
System.out.println("translation ok");
}
}
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <deque>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
int main() {
std::deque<int> dq; // blocks + index map, O(1) both ends
dq.push_back(1); dq.push_back(2); dq.push_front(0);
assert((std::vector<int>(dq.begin(), dq.end()) == std::vector<int>{0, 1, 2}));
assert(dq.front() == 0 && dq.back() == 2);
dq.pop_front(); dq.pop_back();
assert(dq.size() == 1);
std::unordered_map<std::string, int> freq;
for (const char* w : {"b", "a", "c", "a", "b", "a"}) ++freq[w]; // operator[] default-inserts 0
assert(freq["a"] == 3 && freq["b"] == 2 && freq["c"] == 1);
std::vector<std::pair<std::string, int>> people = {{"ann", 90}, {"bob", 85}, {"cat", 90}, {"dan", 85}};
std::stable_sort(people.begin(), people.end(),
[](const auto& x, const auto& y) { return x.second > y.second; }); // std::sort is NOT stable
std::vector<std::string> names;
for (auto& p : people) names.push_back(p.first);
assert((names == std::vector<std::string>{"ann", "cat", "bob", "dan"}));
std::printf("translation ok\n");
return 0;
}
import assert from "node:assert/strict";
function main(): void {
// No built-in deque: a plain array has O(1) push/pop at the back but O(n) shift/unshift at the front.
// For a real deque use two stacks or a ring buffer; here we just show the array API and its cost.
const dq: number[] = [];
dq.push(1); dq.push(2); dq.unshift(0); // unshift is O(n)
assert.deepEqual(dq, [0, 1, 2]);
assert.equal(dq.shift(), 0); // shift is O(n)
assert.equal(dq.pop(), 2);
const freq = new Map<string, number>();
for (const w of ["b", "a", "c", "a", "b", "a"]) freq.set(w, (freq.get(w) ?? 0) + 1);
assert.equal(freq.get("a"), 3);
assert.equal(freq.get("b"), 2);
assert.equal(freq.get("c"), 1);
const people: [string, number][] = [["ann", 90], ["bob", 85], ["cat", 90], ["dan", 85]];
const byScore = [...people].sort((x, y) => y[1] - x[1]); // stable since ES2019; numeric comparator!
assert.deepEqual(byScore.map((p) => p[0]), ["ann", "cat", "bob", "dan"]);
assert.deepEqual([1, 10, 2].sort(), [1, 10, 2]); // default sort compares as strings
assert.deepEqual([1, 10, 2].sort((a, b) => a - b), [1, 2, 10]);
console.log("translation ok");
}
main();
Complexity cheat table across languages
| Operation | Python | Java | C++ | JavaScript |
|---|---|---|---|---|
| Index into sequence | list[i] | ArrayList.get ; LinkedList.get | vector[i] ; deque[i] | arr[i] (packed) |
| Append at end | append am. | add am. | push_back am. | push am. |
| Insert / remove at front | insert(0), pop(0) ; deque | add(0) ; ArrayDeque.addFirst | vector.insert(begin) ; deque.push_front | unshift, shift |
| Insert / remove in middle | ; list with iterator | splice | ||
| Membership in sequence | in | contains | std::find | includes |
| Membership in hash set | in set | HashSet.contains | unordered_set.count | Set.has |
| Hash map get / put | avg | avg, treeified worst | avg, worst | avg |
| Ordered map get / put | bisect / insort | TreeMap | map | sorted array / |
| Floor / ceiling key | bisect_right - 1 / bisect_left | floorKey / ceilingKey | prev(upper_bound) / lower_bound | hand-written |
| Heap push / pop | heapq | PriorityQueue | priority_queue | hand-written |
| Heapify | heapify | constructor | make_heap | hand-written |
| Remove arbitrary from heap | (no API) | remove(Object) | none | none |
| Sort | Timsort stable | TimSort stable (objects); dual-pivot quicksort (primitives) | introsort unstable; stable_sort | TimSort stable (ES2019) |
| Min / max of sequence | min/max | Collections.min | min_element | Math.min(...a) , arg limit |
| Slice / sub-list copy | a[i:j] | subList view | vector(b, e) | slice |
| String build from parts | ''.join | StringBuilder | string += am. | join (rope += in V8) |
| Length / size | everywhere | (forward_list has none) |
Pitfalls
- Mutable default arguments (Python).
def f(x, acc=[])creates one list shared by every call; useacc=Noneand create inside. The same applies to{}and to any mutable default indataclassfields (usefield(default_factory=list)). list.remove(x)andlist.pop(0)are (Python). In a loop they are . Use asetfor removal, adequefor queues, or a two-pointer compaction.inon a list versus a set (Python).if x in big_listinside a loop is the most common accidental quadratic in the language. Build a set once.[[0] * m] * n(Python) aliases one inner list; mutategrid[0][0]and every row changes. Use[[0] * m for _ in range(n)].List.remove(int)vsremove(Object)(Java). On aList<Integer>,remove(3)removes index 3. Useremove(Integer.valueOf(3))for the value.==on boxedInteger(Java). True for −128..127 (cached), false above. Useequalsor unbox.Arrays.asListandList.of(Java) are fixed-size and immutable respectively;addthrowsUnsupportedOperationException.HashMapiteration order (Java) is unspecified and changes on resize; tests that pass on insertion order break later. UseLinkedHashMapwhen order matters.map[key]inserts (C++). Readingm[k]on astd::maporunordered_mapcreateskwith a default value. Usefind,count,containsoratfor lookups.unordered_mapworst case (C++). Adversarial keys make it per operation; use a seeded custom hash orstd::mapwhen inputs are hostile.- Erasing while iterating (C++).
v.erase(it)invalidatesit; writeit = v.erase(it)or usestd::erase_if. Holding a reference into avectoracrosspush_backis the same bug. std::sortis not stable (C++). Usestd::stable_sortwhen equal keys must keep their order, and never use<=in a comparator.vector<bool>(C++) is not a container ofbool;operator[]returns a proxy and you cannot take abool&.sort()without a comparator (JavaScript).[1, 10, 2].sort()gives[1, 10, 2]. Always(a, b) => a - bfor numbers.Array(n)holes anddelete arr[i](JavaScript). Both create holes that slow every access and makemap/forEachskip indices; usefill,Array.from, orsplice.shift()andunshift()in loops (JavaScript) are ; a BFS queue built onshiftis quadratic. Use an index pointer into the array, a ring buffer, or two stacks.- Objects as maps (JavaScript). Numeric keys become strings,
__proto__is a live key, and inherited properties leak intoin. UseMap. Math.max(...arr)(JavaScript) throws for arrays beyond the argument limit (around depending on engine); loop instead.- Integer precision (JavaScript). Beyond integers lose precision silently; bitwise operators truncate to 32 bits. Use
BigIntfor big arithmetic and avoid>>on sums that can exceed . - Hash iteration order is not sorted, in any language.
dict,HashMap,unordered_mapandMapgive insertion order (or no order), never key order; sort explicitly.
Practice: know your library
Problems where picking the right container is the solution. Descriptions are in our own words.
1. Top K Frequent Elements (LeetCode 347) — medium. Return the most frequent values of an array. Teaches Counter / HashMap.merge plus a heap of size or bucket sort by frequency.
Hint
Count in , then either heapq.nlargest(k, counts, key=counts.get) for or put values into buckets indexed by frequency for .
Solution
from collections import Counter
import heapq
def top_k_frequent(nums: list[int], k: int) -> list[int]:
counts = Counter(nums) # O(n)
return heapq.nlargest(k, counts.keys(), key=counts.get) # O(n log k)
def top_k_frequent_buckets(nums: list[int], k: int) -> list[int]:
counts = Counter(nums)
buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
for v, c in counts.items():
buckets[c].append(v)
out: list[int] = []
for c in range(len(buckets) - 1, 0, -1): # highest frequency first
out.extend(buckets[c])
if len(out) >= k:
return out[:k]
return out
assert sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
assert top_k_frequent([1], 1) == [1]
assert sorted(top_k_frequent_buckets([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
assert sorted(top_k_frequent_buckets([4, 4, 5, 5, 6], 2)) == [4, 5]
print("top k ok")
Heap version time, space; bucket version time and space.
2. Kth Largest Element in a Stream (LeetCode 703) — easy. Maintain the -th largest value as numbers arrive. Teaches the bounded min-heap: keep only elements, the root is the answer.
Hint
Push every value; when the heap exceeds , pop the smallest. The root is the -th largest. heapq.heappushpop does both in one sift once the heap is full.
Solution
import heapq
class KthLargest:
def __init__(self, k: int, nums: list[int]) -> None:
self.k = k
self.heap = nums[:]
heapq.heapify(self.heap) # O(n)
while len(self.heap) > k:
heapq.heappop(self.heap)
def add(self, val: int) -> int:
if len(self.heap) < self.k:
heapq.heappush(self.heap, val)
elif val > self.heap[0]:
heapq.heapreplace(self.heap, val) # one sift instead of pop + push
return self.heap[0]
kl = KthLargest(3, [4, 5, 8, 2])
assert [kl.add(3), kl.add(5), kl.add(10), kl.add(9), kl.add(4)] == [4, 5, 5, 8, 8]
kl2 = KthLargest(1, [])
assert kl2.add(-3) == -3 and kl2.add(-2) == -2
print("kth largest ok")
per add, space. Java: PriorityQueue<Integer> with poll when size() > k; C++: priority_queue<int, vector<int>, greater<int>>.
3. Sliding Window Maximum (LeetCode 239) — hard. Maximum of every window of size . Teaches the monotonic deque — and that it must be a real deque (collections.deque, ArrayDeque, std::deque), not a list with pop(0).
Hint
Keep indices in a deque with values decreasing from front to back. Pop the back while its value is less than or equal to the new one; pop the front when it falls out of the window. The front is the maximum.
Solution
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
dq: deque[int] = deque() # indices, values decreasing front to back
out: list[int] = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x: # smaller elements can never be a future max
dq.pop()
dq.append(i)
if dq[0] <= i - k: # front left the window
dq.popleft()
if i >= k - 1:
out.append(nums[dq[0]])
return out
assert max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert max_sliding_window([1], 1) == [1]
assert max_sliding_window([9, 8, 7, 6], 2) == [9, 8, 7]
assert max_sliding_window([1, 2, 3, 4], 4) == [4]
print("sliding max ok")
time — every index is appended and popped at most once — and space. With list.pop(0) instead of deque.popleft the same code is .
4. Merge k Sorted Lists (LeetCode 23) — hard. Merge sorted linked lists into one. Teaches the heap of heads and the tie-break idiom: nodes are not comparable, so push (value, list_index, node).
Hint
Push the head of each list as (val, i, node). Pop the smallest, append it to the output, push its successor from the same list. heapq.merge does the same lazily for iterables.
5. Time Based Key-Value Store (LeetCode 981) — medium. set(key, value, timestamp) with increasing timestamps; get(key, timestamp) returns the value with the largest timestamp the query. Teaches floor lookup: bisect_right - 1 in Python, TreeMap.floorEntry in Java, upper_bound then prev in C++.
Hint
Per key, keep parallel lists of timestamps and values (timestamps arrive sorted, so append is ). get is a bisect_right on the timestamps.
Solution
import bisect
from collections import defaultdict
class TimeMap:
def __init__(self) -> None:
self.times: dict[str, list[int]] = defaultdict(list)
self.vals: dict[str, list[str]] = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.times[key].append(timestamp) # timestamps strictly increase per the problem
self.vals[key].append(value)
def get(self, key: str, timestamp: int) -> str:
i = bisect.bisect_right(self.times[key], timestamp) - 1 # floor
return self.vals[key][i] if i >= 0 else ""
tm = TimeMap()
tm.set("foo", "bar", 1)
assert tm.get("foo", 1) == "bar" and tm.get("foo", 3) == "bar"
tm.set("foo", "bar2", 4)
assert tm.get("foo", 4) == "bar2" and tm.get("foo", 5) == "bar2"
assert tm.get("foo", 0) == "" and tm.get("nope", 9) == ""
print("timemap ok")
set , get per key. If timestamps could arrive out of order, insort would make set and a TreeMap/std::map would be the right structure.
6. My Calendar I (LeetCode 729) — medium. Book half-open intervals, rejecting any that overlaps an existing one. Teaches ordered-map neighbour queries: the only candidates for overlap are the floor and ceiling of the new start.
Hint
Keep starts sorted (with their ends). For a new [s, e), find the previous interval (floor(s)) and the next (ceiling(s)); the booking is valid if prev.end <= s and e <= next.start. Java: TreeMap.floorKey/ceilingKey; Python: bisect on a sorted list, insert.
7. Sort Characters By Frequency (LeetCode 451) — medium. Reorder a string so that characters appear in decreasing frequency. Teaches Counter.most_common and the key= idiom, and the cost model of building strings (join, StringBuilder).
Hint
Counter(s).most_common() then ''.join(ch * c for ch, c in ...). In Java, count in an int[128] or HashMap, sort the keys with Comparator.comparingInt(counts::get).reversed(), and build with StringBuilder.
8. LFU Cache (LeetCode 460) — hard. Least-frequently-used eviction with LRU tie-break, all in . Teaches combining containers: a map from key to node, a map from frequency to an insertion-ordered structure (OrderedDict in Python, LinkedHashSet in Java), and a running minimum frequency.
Hint
freq -> OrderedDict(key -> value) plus key -> freq. On access, move the key from its frequency bucket to freq + 1 (popitem(last=False) evicts the LRU of the minimum frequency). Track min_freq; it resets to 1 on insert and increments only when the current minimum bucket empties.
9. Snapshot Array (LeetCode 1146) — medium. An array with snap() and get(index, snap_id). Teaches per-index history lists with floor lookup — the same bisect_right - 1 pattern as the time-based store, with TreeMap.floorEntry in Java.
Hint
For each index keep a list of (snap_id, value) pairs, appended only when the value changes. get is a binary search for the last pair with snap_id <= query.
Common mistakes and interview follow-ups
"What is the complexity of that call?" The question behind every solution review. Know pop(0), shift, LinkedList.get, remove(Object), in on a list, map[key], insort, splice and unshift cold — they are the usual culprits when a correct algorithm is "too slow".
"Is your sort stable? Does it matter here?" Timsort (Python, Java objects, JavaScript) is stable; std::sort and Arrays.sort(int[]) are not. It matters whenever you sort by a secondary key after a primary one, or when the problem says "preserve the original order among ties".
"Why a deque and not a list?" Because a list's front operations shift the whole buffer; a deque's are . Name the structure in your language: collections.deque, ArrayDeque, std::deque, or a ring buffer in JavaScript.
"How would you do decrease-key?" None of the four standard heaps support it. Push a new entry and skip stale ones on pop (lazy deletion), or use an ordered set of (key, id) pairs (TreeSet, std::set) where removal is .
"You used a hash map; what is the worst case and does it matter?" per operation under collisions. Python randomises string hashes; Java treeifies bins to ; C++ unordered_map has no protection, so hostile input needs a seeded hash or std::map; V8's Map is not hardened against deliberate collisions either, as far as public documentation states.
"Why Map instead of an object?" Key types, prototype pollution, size, insertion-order iteration, and performance on many keys.
"What does Array(n) do?" Creates a holey array of length , slower than a packed one. new Array(n).fill(0) or a typed array.
"Where does Python keep a sorted set?" Nowhere in the standard library — bisect on a list ( insert), heapq when only the minimum is needed, or sortedcontainers when available. Say this out loud; interviewers know.
"Which is faster to sort: int[] or Integer[]?" int[], several times over, because of boxing and pointer chasing — and it uses a different algorithm (dual-pivot quicksort versus TimSort).
"What happens to a vector iterator after push_back?" It may be invalid if the capacity was exceeded. reserve first, or use indices.
Quick quiz
1. In Python, what is the complexity of heapq.heapify(a) versus for x in a: heapq.heappush(h, x), and when does the difference matter?
Answer
heapify is ; pushes are . It matters when you build a heap from a large existing list once — heapify is both asymptotically and practically faster. For a streaming workload you push anyway.
2. A Java List<Integer> xs = new ArrayList<>(List.of(5, 6, 7)). What do xs.remove(1) and xs.remove(Integer.valueOf(1)) each do?
Answer
remove(1) calls remove(int index) and deletes the element at index 1 (the 6), leaving [5, 7]. remove(Integer.valueOf(1)) calls remove(Object) and looks for the value 1, which is absent, so it returns false and changes nothing.
3. What does [1, 10, 2].sort() return in JavaScript and why? How do you fix it?
Answer
[1, 10, 2]. Without a comparator, elements are converted to strings and compared lexicographically, and "10" < "2". Pass (a, b) => a - b (or Int32Array.from(arr).sort() which sorts numerically).
4. In C++, std::map<std::string, int> m; if (m["x"] == 0) … — what happened to m.size()?
Answer
It is now 1: operator[] inserts "x" with a default-constructed int (0) when the key is absent. Use m.find("x") == m.end(), m.count("x") or C++20 m.contains("x") for a lookup that does not insert.
5. Which of Python's sorted, Java's Arrays.sort(int[]), C++'s std::sort and JavaScript's Array.prototype.sort are stable?
Answer
Python's sorted and JavaScript's sort (since ES2019) are stable. C++ std::sort is not (use std::stable_sort). Java Arrays.sort(int[]) uses dual-pivot quicksort, where stability is meaningless for primitives; Arrays.sort(Object[]) and List.sort use TimSort and are stable.
Further reading, sources and verification notes
- Python: TimeComplexity on the Python wiki (the canonical table for
list,deque,set,dict); theheapq,bisect,collectionsandarraymodule documentation;Objects/listsort.txtandObjects/dictobject.cin the CPython source. The wiki page was unreachable from the author's network at the time of writing (redirect loop), so its entries were checked against the module documentation, the CPython source and measurement rather than against the live page. - Java: the Java 21 API documentation for
ArrayList,LinkedList,ArrayDeque,HashMap,TreeMap,PriorityQueueandArrays(algorithm notes forsortverified against the live Javadoc); OpenJDK source forArrayList.growand theHashMaptreeify constants. - C++: cppreference.com container pages (complexity and iterator-invalidation tables), the C++20 standard's container requirements tables; libstdc++
stl_vector.hand Microsoft STLvectorfor growth factors; the Codeforces blog "Blowing up unordered_map, and how to stop getting hacked on it" for the anti-hash discussion. - JavaScript: the ECMAScript specification (
Array.prototype.sortstability requirement,Mapiteration order); V8 blog posts "Getting things sorted in V8" (TimSort, stable since V8 7.0 — verified against the post), "Elements kinds in V8", "Fast properties in V8";src/objects/js-objects.hfor the array growth formula. - Books: CLRS Chapters 6 (heaps), 10–13 (elementary structures, hashing, balanced trees); Sedgewick & Wayne, Algorithms, Chapters 1.3 and 3; Scott Meyers, Effective STL, Items 1–7 and 23 ("Consider replacing associative containers with sorted vectors").
- Claims that rest on implementation rather than documentation and could change: Python
setload factor and probing details;dequeblock size of 64; V8shiftleft-trimming and rope strings; SSO sizes (15 in libstdc++/MSVC, 22 in libc++); the per-lookup nanosecond figures, which are from one machine.
Module 0: Module overview · How to Use This Course · Complexity Analysis · Recursion & Induction · How Data Structures Live in Memory · Your Language's Data Structures · How to Solve Any Problem · Testing & Debugging Algorithms · Capstone · Course home
Previous: How Data Structures Live in Memory · Next: How to Solve Any Problem: The Method
Related: Hash Tables · Heaps & Priority Queues · Sorting & Searching · Linked Lists · Trees · Python cheat sheet · TypeScript cheat sheet · JavaScript interview