Cheat SheetsDSAGeneral

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