DSA and problem solving cheat sheet (C++)

1. 1Complexity and Big-OHow to say what code costs in time and memory before running it. Every later chapter trades one of these costs for another.7 concepts

   1. 1Big-O notationBig-O describes how the running time or memory of an algorithm grows as the input size n grows, keeping only the fastest-growing term and dropping constants.
   2. 2Common growth ratesFrom fastest to slowest: O(1) constant, O(log n) repeated halving, O(n) one pass, O(n log n) sorting, O(n^2) all pairs, O(2^n) all subsets, O(n!) all orderings.
   3. 3Counting operations in loopsMultiply the costs of nested loops and add the costs of loops in sequence.
   4. 4Best, worst and average caseWorst case is the most work on any input of size n, best case the least, and average case the expected work over typical or random inputs.
   5. 5Space complexity and the call stackThe extra memory an algorithm uses beyond its input, as a function of n.
   6. 6Amortised costThe average cost per operation over any long sequence of operations, even if a few single operations are expensive.
   7. 7Reading constraintsThe input limits in a problem hint at the expected complexity.

   7 in this chapterOpen this chapter
2. 2Arrays, strings and hashingContiguous sequences and hash-based lookup, the structures most problems are built on, and exactly what your language gives you for each.8 concepts

   1. 1Arrays and dynamic arraysAn array stores items side by side in memory, so reading or writing index i is O(1).
   2. 2StringsA string is a sequence of characters.
   3. 3Hash mapsA hash map stores key-value pairs in buckets chosen by a hash of the key, giving O(1) average insert, lookup and delete.
   4. 4Hash setsA hash set stores unique keys without values, with O(1) average add, remove and membership check.
   5. 5Composite and custom keysWhen a key is made of several values, like a grid cell or a sorted word, it must be hashable and compare by value.
   6. 6Prefix sumsA prefix sum array stores running totals, so prefix[i] is the sum of the first i items.
   7. 7Integer limits and overflowJava and C++ int holds up to about 2.1 billion (2^31 - 1); past that Java wraps around and C++ has undefined behaviour.
   8. 8C++ standard containersvector is the dynamic array, unordered_map and unordered_set are hash tables, deque, stack and queue cover the ends, priority_queue is a max-heap…

   8 in this chapterOpen this chapter
3. Linked lists, stacks and queuesPointer-based lists and the structures that control the order work is done in: last in first out, first in first out, and both ends.7 conceptsOpens with credits
4. Recursion, sorting and searchingTrusting recursion, the classic sorts and what they cost, and binary search with its boundary variants, including searching over the answer.10 conceptsOpens with credits
5. Trees and heapsHierarchical structures, the traversals that answer most questions about them, and heaps for anything that needs the smallest or largest item fast.7 conceptsOpens with credits
6. GraphsNodes and edges, and the algorithms that search, order and connect them. Grids, schedules and dependency lists are often graph problems in disguise.9 conceptsOpens with credits
7. Coding patternsRecognisable problem shapes that turn a brute force into an efficient solution. Name the pattern and the signal that told you before writing any code.10 conceptsOpens with credits
8. Dynamic programmingRecursion plus a cache, then the handful of problem families most DP questions belong to. Start from the state and the recursion, never from the table.10 conceptsOpens with credits
9. Timed practice and problem-solving habitsThe routine that makes you reliable under a clock, whether in a contest, an exam or a coding round: clarify, plan, code, test and review.8 conceptsOpens with credits
10. 10Glossary, A to ZEvery concept in the sheet and the smaller terms it uses, in one list.160 terms

Data structures and patterns.