On this page

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

ContainerBuilt onOrdered?Typical use
listdynamic array of object pointersby indexsequences, stacks, the default
tuplefixed array of object pointersby indeximmutable records, dict keys
dictcompact open-addressing hash tableinsertion order (3.7+)maps, memo tables, counting
set / frozensetopen-addressing hash tablearbitrarymembership, dedup, set algebra
collections.dequedoubly linked list of 64-slot blocksby positionqueues, sliding windows, BFS
heapqfunctions over a listheap orderpriority queues
bisectfunctions over a sorted listsortedbinary search, "sorted list"
collections.Counter, defaultdict, OrderedDictdict subclassesinsertion ordercounting, grouping, LRU
array.array, bytes, bytearraycontiguous raw valuesby indexcompact numeric/byte storage
strimmutable compact array of code pointsby indextext

list

OperationComplexityNotes
a[i], a[i] = x, len(a)address arithmetic on the pointer array
a.append(x) amortisedover-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] = bshift the tail
a.extend(b), a += b amortiseda = a + b is because it builds a new list
a.sort(), sorted(a), stableTimsort; on already-sorted or reverse-sorted input
a.reverse()in place; reversed(a) is a lazy iterator
min(a), max(a), sum(a)
a * kcopies pointers; [[0] * m] * n aliases the same inner list times
a == belement-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

OperationAverageAmortised worstNotes
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, itemssequential scan of the entries array, insertion order
d.copy(), dict(d)
d.update(e), d | e3.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

OperationAverageWorstNotes
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 worstiterates the smaller, probes the larger
s - titerates s, probes t
s ^ t
s <= t, s.issubset(t)
s.pop() amortisedarbitrary element
iterationarbitrary 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

OperationComplexityNotes
append, appendleft, pop, popleftthe whole point
d[0], d[-1]
d[i] in the middlewalks 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

OperationComplexityNotes
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), nsmallestkey= supported; for near , sorted is faster
heapq.merge(*its) lazy sorted inputs, total items
decrease-keynot availablepush 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

OperationComplexityNotes
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= parameter3.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

OperationComplexityNotes
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 | c2multiset 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

ContainerBuilt onOrdered?Typical use
ArrayList<E>Object[] with 1.5x growthby indexthe default list
LinkedList<E>doubly linked nodesby positionalmost never — see ArrayDeque
ArrayDeque<E>circular Object[]by positionstacks and queues
HashMap<K,V>Node[] chaining, treeified binsnothe default map
LinkedHashMap<K,V>HashMap + doubly linked entriesinsertion or accesspredictable iteration, LRU
TreeMap<K,V>red-black treesorted by keyfloor/ceiling/range queries
HashSet, LinkedHashSet, TreeSetthe corresponding map with dummy valuesas abovemembership
PriorityQueue<E>binary heap in Object[]heap ordermin-heap by default
String / StringBuilderbyte[] (Latin-1 or UTF-16)by indextext
int[], long[], …raw primitive arraysby indexwhen boxing is unaffordable

ArrayList, LinkedList, ArrayDeque

OperationArrayListLinkedListArrayDeque
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 linknot 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 viewnot supported
toArray()
null elementsallowedallowednot 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

OperationHashMapLinkedHashMapTreeMap
get, put, remove, containsKey average, worst in a treeified binsame 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 averagesame
null keysone allowedone allowednot 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

OperationComplexityNotes
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 orderarray order
decrease-keynot availablere-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

CallAlgorithmStable?Complexity
Arrays.sort(int[]), other primitivesDual-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 backyes
Arrays.parallelSortparallel merge sort over sortyes 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

ContainerBuilt onOrdered?Typical use
vector<T>contiguous dynamic array (2x libstdc++, 1.5x MSVC)by indexthe default
array<T, N>fixed-size contiguousby indexsmall fixed buffers, no heap
deque<T>blocks + index mapby indexqueues, both-end growth
list<T>, forward_list<T>doubly / singly linked nodesby positionsplicing, stable addresses
set, map, multiset, multimapred-black treesortedordered queries
unordered_set, unordered_map (+ multi)chaining, node per elementnohashing
priority_queue<T>heap over a vectorheap ordermax-heap by default
stack<T>, queue<T>adaptors over deque by defaultLIFO / FIFO
stringcontiguous char with SSOby indextext
bitset<N>fixed array of wordsby indexflags, subsets

vector, array, deque, list, forward_list

Operationvectordequelistforward_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()yesnonono
splice—— whole list or one element; for a range from another listsimilar
sortstd::sort std::sortmember sort() merge sort, stablemember sort()
iterator/reference stability on push_backinvalidated on reallocationiterators invalidated, references stablestablestable

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

OperationComplexityNotes
insert, emplace, erase(key), find, counterase(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 nodemove nodes between containers without reallocation
iterationsorted 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

OperationAverageWorstNotes
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

AlgorithmWhat it doesComplexityStable?
std::sortintrosort (quicksort + heapsort fallback + insertion sort for small ranges) worst case (guaranteed since C++11)no
std::stable_sortmerge sort with a buffer with memory; if allocation failsyes
std::nth_elementplaces the -th smallest at index , partitions around it average (introselect)—
std::partial_sortsorts the first of no
std::is_sorted, std::binary_search, std::lower_bound, std::upper_boundon sorted ranges / —
std::ranges::sort etc. (C++20)same algorithms with projectionssamesame

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

Containerinsert / push_back / emplaceerase
vectorall iterators, pointers and references invalidated if capacity is exceeded; otherwise only those at or after the insertion pointat and after the erased element (including end())
dequeall iterators invalidated; references stay valid for push_front/push_back; an insert in the middle invalidates references tooat the ends: only the erased; in the middle: all
list, forward_listnothingonly the erased
set, map, multi*nothingonly the erased
unordered_*all iterators if a rehash occurs; references and pointers to elements stay validonly the erased
stringlike vectorlike 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

ContainerBuilt on (V8)Ordered?Typical use
Arraycontiguous elements store with elements kinds, or a dictionary when sparseby indexeverything sequential
Map, Setinsertion-ordered hash table (OrderedHashTable)insertionkeyed lookup, dedup
WeakMap, WeakSetephemeron table, object keys onlynot iterablecaches keyed by objects
Int32Array, Float64Array, …raw ArrayBufferby indexnumeric work, binary data
plain object {}hidden classes + optional dictionary modestring keys, mostly insertion orderrecords; avoid as a general map
stringimmutable; flat or rope (ConsString)by index (UTF-16 code units)text

Array

OperationComplexityNotes
a[i], a[i] = x, a.lengthfor packed arrays; dictionary-mode arrays are hash lookups
push, pop amortisedgrowth 1.5x + 16 (source)
shift, unshiftV8 can sometimes "left-trim" to make shift cheap; never rely on it
indexOf, includes, find, findIndexincludes 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
reversein place
map, filter, forEach, reduceallocate a new array except forEach/reduce
flat(depth)
at(-1)ES2022
delete a[i] but leaves a holethe 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

OperationComplexityNotes
map.get, set, has, delete averagekeys compared with SameValueZero: NaN equals NaN, +0 equals -0, objects by identity
map.sizea 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, differenceES2025 set methods; check runtime support
WeakMap.get/set/has/delete averageobject 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

PythonJavaC++JavaScript
Min-heap typelist + heapqPriorityQueue<T>priority_queue<T, vector<T>, greater<T>>write a class
Push / popheappush, heappopoffer, pollpush, pop (+ top)push, pop
Max-heapnegate keysCollections.reverseOrder()default priority_queue<T>flip comparator
Heapify heapify(a)new PriorityQueue<>(coll)make_heap / range constructorbuild then sift down
Tie-break(prio, counter, item)thenComparingLong(seq)tuple<int, long, T>comparator on seq
Decrease-keynone: lazy deletionnonenonenone
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

PythonJavaC++JavaScript
Structuresorted list + bisect (insert )TreeMapstd::mapsorted array + binary search
Ceiling (first key )bisect_leftceilingKey(k)lower_bound(k)hand-written lowerBound
Floor (last key )bisect_right(k) - 1floorKey(k)prev(upper_bound(k))upperBound(k) - 1
Strict versionsbisect_right / bisect_left - 1higherKey, lowerKeyupper_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 / maxa[0], a[-1]firstKey, lastKeybegin(), 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

PythonJavaC++JavaScript
Dequecollections.dequeArrayDequestd::dequenone; ring buffer or two stacks
Push / pop frontappendleft, popleftaddFirst, pollFirstpush_front, pop_frontunshift, shift ()
Frequency countCounter(it)map.merge(k, 1, Integer::sum)++freq[k]m.set(k, (m.get(k) ?? 0) + 1)
Stable sort by keysorted(a, key=f)list.sort(Comparator.comparing(f))std::stable_sort with a lambdaa.sort((x, y) => ...)
Sort descending stablyreverse=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

OperationPythonJavaC++JavaScript
Index into sequencelist[i] ArrayList.get ; LinkedList.get vector[i] ; deque[i] arr[i] (packed)
Append at endappend am.add am.push_back am.push am.
Insert / remove at frontinsert(0), pop(0) ; deque add(0) ; ArrayDeque.addFirst vector.insert(begin) ; deque.push_front unshift, shift
Insert / remove in middle; list with iteratorsplice
Membership in sequencein contains std::find includes
Membership in hash setin set HashSet.contains unordered_set.count Set.has
Hash map get / put avg avg, treeified worst avg, worst avg
Ordered map get / putbisect / insort TreeMap map sorted array /
Floor / ceiling keybisect_right - 1 / bisect_leftfloorKey / ceilingKeyprev(upper_bound) / lower_boundhand-written
Heap push / popheapq PriorityQueue priority_queue hand-written
Heapifyheapify constructor make_heap hand-written
Remove arbitrary from heap (no API)remove(Object) nonenone
SortTimsort stableTimSort stable (objects); dual-pivot quicksort (primitives)introsort unstable; stable_sortTimSort stable (ES2019)
Min / max of sequencemin/max Collections.min min_element Math.min(...a) , arg limit
Slice / sub-list copya[i:j] subList viewvector(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; use acc=None and create inside. The same applies to {} and to any mutable default in dataclass fields (use field(default_factory=list)).
  • list.remove(x) and list.pop(0) are (Python). In a loop they are . Use a set for removal, a deque for queues, or a two-pointer compaction.
  • in on a list versus a set (Python). if x in big_list inside a loop is the most common accidental quadratic in the language. Build a set once.
  • [[0] * m] * n (Python) aliases one inner list; mutate grid[0][0] and every row changes. Use [[0] * m for _ in range(n)].
  • List.remove(int) vs remove(Object) (Java). On a List<Integer>, remove(3) removes index 3. Use remove(Integer.valueOf(3)) for the value.
  • == on boxed Integer (Java). True for −128..127 (cached), false above. Use equals or unbox.
  • Arrays.asList and List.of (Java) are fixed-size and immutable respectively; add throws UnsupportedOperationException.
  • HashMap iteration order (Java) is unspecified and changes on resize; tests that pass on insertion order break later. Use LinkedHashMap when order matters.
  • map[key] inserts (C++). Reading m[k] on a std::map or unordered_map creates k with a default value. Use find, count, contains or at for lookups.
  • unordered_map worst case (C++). Adversarial keys make it per operation; use a seeded custom hash or std::map when inputs are hostile.
  • Erasing while iterating (C++). v.erase(it) invalidates it; write it = v.erase(it) or use std::erase_if. Holding a reference into a vector across push_back is the same bug.
  • std::sort is not stable (C++). Use std::stable_sort when equal keys must keep their order, and never use <= in a comparator.
  • vector<bool> (C++) is not a container of bool; operator[] returns a proxy and you cannot take a bool&.
  • sort() without a comparator (JavaScript). [1, 10, 2].sort() gives [1, 10, 2]. Always (a, b) => a - b for numbers.
  • Array(n) holes and delete arr[i] (JavaScript). Both create holes that slow every access and make map/forEach skip indices; use fill, Array.from, or splice.
  • shift() and unshift() in loops (JavaScript) are ; a BFS queue built on shift is 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 into in. Use Map.
  • 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 BigInt for big arithmetic and avoid >> on sums that can exceed .
  • Hash iteration order is not sorted, in any language. dict, HashMap, unordered_map and Map give 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); the heapq, bisect, collections and array module documentation; Objects/listsort.txt and Objects/dictobject.c in 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, PriorityQueue and Arrays (algorithm notes for sort verified against the live Javadoc); OpenJDK source for ArrayList.grow and the HashMap treeify constants.
  • C++: cppreference.com container pages (complexity and iterator-invalidation tables), the C++20 standard's container requirements tables; libstdc++ stl_vector.h and Microsoft STL vector for 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.sort stability requirement, Map iteration 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.h for 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 set load factor and probing details; deque block size of 64; V8 shift left-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