cheatsheet · before you code
Which data structure?
Use it when: You know what must be fast (lookup, min, order, undo…) and need the right container.
- Look something up by a key, or count things
HashMapO(1) avg per get / putlearn → - "Have I seen this before?"
HashSetO(1) avg per add / containslearn → - Count letters a–z (or digits)
int[26](orint[10])O(1) per update, O(1) spacelearn → - Keep a list that grows, read by index
ArrayListO(1) get, amortized O(1) add at the endlearn → - Build a string inside a loop
StringBuilderamortized O(1) per character appendedlearn → - Last in, first out: undo, brackets, "go back"
ArrayDequeas a stack (push/pop)O(1) amortizedlearn → - First in, first out: process in arrival order, BFS
ArrayDequeas a queue (offer/poll)O(1) amortizedlearn → - Next greater / next smaller elementMonotonic stackO(n) total: each item pushed and popped oncelearn →
- Max or min of every sliding windowMonotonic dequeO(n) totallearn →
- Take the smallest (or largest) again and again
PriorityQueueO(log n) offer / poll, O(1) peeklearn → - The k largest of n itemsMin-heap kept at size kO(n log k)learn →
- Keys in sorted order, or the nearest key (floor / ceiling)
TreeMap/TreeSetO(log n) per operationlearn → - Sum of a range, the array never changesPrefix-sum arrayO(n) to build, O(1) per querylearn →
- Sum of a range, the array also changesFenwick tree or segment treeO(log n) per update and querylearn →
- "Are these two connected?" while groups keep mergingUnion-findalmost O(1) amortized (path compression + union by size or rank)learn →
- Search by prefix, autocompleteTrieO(word length) per insert / searchlearn →
- Most-recently-used order with O(1) updates (LRU)
HashMap+ doubly linked list (orLinkedHashMap)O(1) avg per get / putlearn → - Fewest steps, every move costs the sameBFS with a queueO(V + E)learn →
- Cheapest path, costs are never negativeDijkstra with a
PriorityQueueO((V + E) log V)learn → - An order that respects dependenciesTopological sort (Kahn: in-degrees + queue)O(V + E)learn →