General — Cheat Sheet
DSA · 10 topics. Download the PDF or the Instagram carousel and share it.
Cheat Sheet · AiCanCode.org
General
DSA10 topicsQuick revision reference
1
Arrays
- ✓Use the two-pointer technique to solve problems in O(n) that naive solutions solve in O(n²)
- ✓Sliding window pattern handles subarray/substring problems efficiently
- ✓Prefix sum arrays reduce range query time from O(n) to O(1)
- ✓In Java, prefer int[] for primitives over Integer[] — avoids autoboxing overhead
- ✓Arrays.sort() uses dual-pivot quicksort for primitives, merge sort for objects
2
Linked List
- ✓Floyd's cycle detection (slow/fast pointer) detects cycles in O(n) with O(1) space
- ✓Always handle the null/head edge cases first — they cause most bugs
- ✓Reversing a linked list in-place uses three pointers: prev, current, next
- ✓Use a dummy head node to simplify insertion/deletion at the head
- ✓Finding the middle: slow pointer moves 1 step, fast pointer moves 2 steps
3
Stack
- ✓Use ArrayDeque<Integer> in Java — faster than Stack and Deque-compliant
- ✓Monotonic stack solves "next greater/smaller element" problems in O(n)
- ✓Valid parentheses checking is the classic stack interview question
- ✓Stack can simulate recursion iteratively — push children instead of calling recursively
- ✓Two stacks can implement a queue (interview classic)
4
Queue
- ✓BFS always uses a queue — this is how you explore level by level in a tree/graph
- ✓PriorityQueue in Java is a min-heap by default; use Collections.reverseOrder() for max-heap
- ✓Sliding window maximum uses a monotonic deque — O(n) solution
- ✓Two queues can implement a stack — push to one, rotate elements to keep LIFO order
- ✓For "top K frequent elements", use a min-heap of size K
5
Trees & Binary Search Trees
- ✓Inorder traversal of a BST gives elements in sorted order
- ✓Height of a balanced tree is O(log n); a skewed tree degrades to O(n) — like a linked list
- ✓LCA (Lowest Common Ancestor) is a very common interview pattern
- ✓Serialization/deserialization tests deep understanding — you must reconstruct the exact tree from a string
- ✓AVL and Red-Black trees self-balance to keep O(log n); Java's TreeMap uses Red-Black internally
6
Graphs
- ✓BFS finds shortest path in unweighted graphs; Dijkstra handles weighted graphs
- ✓DFS is better for cycle detection, topological sort, and exploring all paths
- ✓Union-Find (Disjoint Set Union) efficiently answers "are these two nodes connected?"
- ✓Topological sort only works on DAGs (Directed Acyclic Graphs) — cycles break it
- ✓For grid problems, treat each cell as a node with 4 neighbours
7
Sorting Algorithms
- ✓Merge sort is stable and guaranteed O(n log n) — preferred when order of equal elements matters
- ✓Quicksort is fastest in practice due to cache locality, but a bad pivot causes O(n²) worst case
- ✓Java's Arrays.sort() uses dual-pivot quicksort for primitives, TimSort (merge+insertion) for objects
- ✓Insertion sort is O(n) on nearly-sorted data — ideal when input is already mostly in order
- ✓Custom Comparator: return negative to place a before b, positive to place b before a
8
Searching Algorithms
- ✓Always use mid = left + (right - left) / 2 to avoid integer overflow
- ✓Three templates: find exact value, find leftmost occurrence, find rightmost occurrence
- ✓Binary search on answer: if you can define a monotonic yes/no function, you can binary search
- ✓Works on any monotonic condition, not just sorted arrays — the key is a clear yes/no boundary
- ✓Rotated sorted array: one half is always sorted, use that to decide which half to search
9
Dynamic Programming
- ✓Pattern 1 — Linear DP: each cell depends on previous cells (Fibonacci, climbing stairs, house robber)
- ✓Pattern 2 — Grid DP: move through a 2D grid, each cell depends on neighbours above/left
- ✓Pattern 3 — Interval DP: solve for ranges, combine sub-range answers (burst balloons, matrix chain)
- ✓Pattern 4 — Knapsack: pick items with weight/value constraints (coin change, subset sum)
- ✓Pattern 5 — String DP: compare two strings character by character (LCS, edit distance)
10
Hashing
- ✓HashMap allows one null key; HashSet is just a HashMap where you only care about keys, not values
- ✓Use getOrDefault(), merge(), and computeIfAbsent() to write cleaner, null-safe code
- ✓LinkedHashMap maintains insertion order; TreeMap maintains sorted key order
- ✓For counting frequencies, Map.merge(key, 1, Integer::sum) is the idiomatic Java one-liner
- ✓To check if two strings are anagrams, sort them or use a 26-element frequency array
Learn this free with Aria, your AI tutor → AiCanCode.org/learn/dsa