DSA Cheat Sheet

Complexity, use cases, and when to reach for each algorithm. Print-friendly.

Searching

Algorithm	Difficulty	Time	Space	When to use
Linear Search	Beginner	O(n)	O(1)	· Search an unsorted array or linked list where sorting is not possible · Find an element in a small list where simplicity matters more than speed · Verify an element exists before more expensive processing + 1 more
Binary Search	Beginner	O(log n)	O(1)	· Search a sorted array for a target value in O(log n) · Find the first/last occurrence of a value in a sorted array · Find the insertion position for a value (lower_bound / upper_bound) + 2 more
BFS: Level-Order Traversal	Intermediate	O(n)	O(n)	· Shortest path in an unweighted graph · Level-order traversal of a binary tree · Finding all nodes at distance k from root + 2 more
DFS: Pre-order Traversal	Intermediate	O(n)	O(h)	· Tree traversals (pre/in/post-order) · Detecting cycles in a graph · Topological sort of a DAG + 3 more
BST: Search	Intermediate	O(h)	O(h)	· Ordered key-value lookup (database indexes use B-trees, a generalization) · Range queries — find all values between A and B · Floor/ceiling operations — find the largest value ≤ target + 1 more
BST: Insert	Intermediate	O(h)	O(h)	· Building a BST from an array of values · Maintaining a sorted dynamic set with fast insert/delete/search · Implementing a sorted map / ordered dictionary + 1 more

Algorithm	Difficulty	Time	Space	When to use
Bubble Sort	Beginner	O(n²)	O(1)	· Teaching how sorting works — clearest algorithm to visualize · Detecting nearly-sorted data (early-exit variant is O(n) best case) · Rarely used in production — prefer merge sort or quick sort for real data
Selection Sort	Beginner	O(n²)	O(1)	· When the number of writes (swaps) must be minimized — selection sort does at most n swaps · Sorting small arrays where simplicity is preferred over speed · Memory-constrained environments — sorts in place with O(1) extra space
Insertion Sort	Beginner	O(n²)	O(1)	· Nearly-sorted arrays — runs in O(n) when data is almost in order · Online sorting — can sort a stream of incoming elements one at a time · Small arrays (n < ~20) — often faster than O(n log n) sorts due to low overhead + 1 more
Merge Sort	Intermediate	O(n log n)	O(n)	· General-purpose stable sort — guaranteed O(n log n) on all inputs · Sorting linked lists — merge sort works naturally without random access · External sorting — merging sorted chunks from disk when data doesn't fit in RAM + 2 more
Quick Sort	Intermediate	O(n log n) avg	O(log n)	· General-purpose in-place sorting — used inside Array.prototype.sort in most JS engines · Cache-friendly sorting of large arrays where memory locality matters · When average-case O(n log n) is acceptable and in-place is required + 1 more

Algorithm	Difficulty	Time	Space	When to use
Two Pointers: Pair Sum	Beginner	O(n)	O(1)	· Pair sum / pair with given difference in a sorted array · Three-sum and k-sum problems (outer loop + two-pointer inner loop) · Remove duplicates from a sorted array in place + 3 more

Algorithm	Difficulty	Time	Space	When to use
Sliding Window: Max Sum	Intermediate	O(n)	O(1)	· Maximum/minimum sum of k consecutive elements · Longest substring without repeating characters (variable-size window) · Minimum window substring containing all required characters + 2 more

Algorithm	Difficulty	Time	Space	When to use
Stack: Push, Pop, Peek	Beginner	O(1) per op	O(n)	· Balanced brackets / parentheses validation (LC 20) · Undo / redo in text editors and applications · Browser back/forward navigation history + 3 more
Queue: Enqueue, Dequeue, Front	Beginner	O(1) per op	O(n)	· BFS (Breadth-First Search) — level-by-level graph / tree traversal · Task scheduling — OS process queues, job queues in web servers · Message passing — Kafka, RabbitMQ, SQS are all queues at their core + 3 more

O(1)Constant — best possible

O(log n)Logarithmic — halves each step

O(n)Linear — visits each element once

O(n log n)Log-linear — most efficient sorts

O(n²)Quadratic — nested loops, avoid on large n