One page
Algorithms and Data Structures cheat sheet
What to keep at hand. If a line is not clear, go back to the matching lesson in the course.
Open the course: Algorithms and Data StructuresCost of operations
| What | How |
|---|---|
| Array: index access | arr[i] // O(1) |
| Array: push and pop | arr.push(x); arr.pop() // O(1) |
| Array: shift and unshift | arr.shift() // O(n) |
| Array: search by value | arr.includes(x) // O(n) |
| Sorting | arr.sort((a, b) => a - b) // O(n log n) |
| Map and Set: get, set, has | map.has(k) // O(1) on average |
| Binary search | O(log n), sorted data only |
Patterns and when to use them
| What | How |
|---|---|
| Search inside a loop | Map or Set: O(n²) -> O(n) |
| Pair in a sorted array | two pointers toward each other |
| Contiguous subarray or substring | sliding window |
| Brackets, undo, nesting | stack |
| Shortest path without weights | BFS on a queue |
| Search in sorted data or over the answer | binary search |
Recursion, sorting, trees
| What | How |
|---|---|
| Recursion | base case + step toward a smaller problem |
| Memoization | if (memo.has(n)) return memo.get(n) |
| Merge sort | O(n log n) always, O(n) memory, stable |
| Quick sort | O(n log n) on average, O(n²) in the worst case |
| Sorting numbers | arr.toSorted((a, b) => a - b) |
| Tree height | 1 + Math.max(height(node.left), height(node.right)) |
| Inorder in a BST | values in ascending order |
| BST search | O(h): O(log n) balanced, O(n) chain |
JavaScript templates
| What | How |
|---|---|
| Frequencies | counts.set(x, (counts.get(x) ?? 0) + 1) |
| Two sum | if (seen.has(t - x)) return [seen.get(t - x), i]; seen.set(x, i) |
| Fixed size window | sum += nums[i] - nums[i - k] |
| Middle of the range | const mid = Math.floor((left + right) / 2) |
| Top of the stack | stack.at(-1) |