Complete DSA quick reference — time/space complexities, Java implementations, sorting, searching, graph algorithms, dynamic programming, and backtracking patterns.
| Operation | Array (Static) | ArrayList (Dynamic) | Notes |
|---|---|---|---|
| Access by index | O(1) | O(1) | Direct memory address |
| Search (unsorted) | O(n) | O(n) | Linear scan |
| Search (sorted) | O(log n) | O(log n) | Binary search |
| Insertion at end | n/a | O(1) amortised | Resize doubles capacity |
| Insertion at index | n/a | O(n) | Shifts right elements |
| Deletion at index | n/a | O(n) | Shifts left elements |
| Arrays.sort(arr) | O(n log n) | O(n log n) | Dual-pivot quicksort |
| Collections.sort(list) | O(n log n) | O(n log n) | Timsort (stable) |
| Task | Java Code | Result |
|---|---|---|
| Declare array | int[] arr = {1, 2, 3} | — |
| Sort array | Arrays.sort(arr) | O(n log n) |
| Sort list | Collections.sort(list) | O(n log n) |
| Char digit to int | int d = '4' - '0' | d = 4 |
| Char to String | String s = String.valueOf('e') | "e" |
| Char to ASCII | (int) 'a' | 97 |
| Char array to String | new String(new char[]{'a','e'}) | "ae" |
| Increment char | (char)('a' + 1) | 'b' |
| Is letter or digit | Character.isLetterOrDigit(c) | true/false |
| Copy list | new ArrayList<>(anotherList) | New list with same items |
| Append to StringBuilder | sb.append(char or String) | — |
| String to char array | str.toCharArray() | char[] |
| Substring | str.substring(i, j) | chars i to j-1 |
| String contains | str.contains("abc") | true/false |
| Operation | Singly Linked | Doubly Linked | Notes |
|---|---|---|---|
| Access by index | O(n) | O(n) | Must traverse from head |
| Search | O(n) | O(n) | Linear scan |
| Insert at head | O(1) | O(1) | Adjust head pointer |
| Insert at tail | O(1)* | O(1) | *Only if tail pointer kept |
| Insert at index | O(n) | O(n) | Traverse then insert |
| Delete at head | O(1) | O(1) | Adjust head pointer |
| Delete at index | O(n) | O(n) | Traverse then delete |
| Operation | Average | Worst Case | Notes |
|---|---|---|---|
| get(key) | O(1) | O(n) | Worst = all keys same bucket |
| put(key, val) | O(1) | O(n) | Hash collision degrades |
| containsKey(key) | O(1) | O(n) | — |
| remove(key) | O(1) | O(n) | — |
| Iteration | O(n) | O(n) | Visits all entries |
| HashMap order | ❌ No order | — | Use LinkedHashMap for insertion order |
| LinkedHashMap order | ✅ Insertion order | — | Slightly slower than HashMap |
| TreeMap order | ✅ Sorted by key | O(log n) ops | Red-black tree underneath |
| HashSet duplicates | ❌ No duplicates | — | Uses HashMap internally |
| Structure | Order | Key Methods (Java) | Use Case |
|---|---|---|---|
| Stack | LIFO | push(v), pop(), peek() | DFS, undo history, balanced brackets |
| Queue | FIFO | offer(v), poll(), peek() | BFS, task scheduling |
| Deque | Both ends | offerFirst/Last, pollFirst/Last, peekFirst/Last | Sliding window, monotonic deque |
| PriorityQueue | Min-heap default | offer(v), poll(), peek() | Dijkstra, top-K problems |
| PriorityQueue (max) | Max-heap | new PriorityQueue<>(Comparator.reverseOrder()) | Top-K largest elements |
| ArrayDeque | Both ends, faster | push, pop, offer, poll | Prefer over Stack and LinkedList |
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ No |
| Tim Sort (Java default) | O(n) | O(n log n) | O(n log n) | O(n) | ✅ Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ No |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Yes |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅ Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | ✅ Yes |
| Pattern | When to Use | Template Key Line | Complexity |
|---|---|---|---|
| Exact match | Find index of target in sorted array | if arr[mid] == target return mid | O(log n) time, O(1) space |
| Left boundary | First position ≥ target | if arr[mid] < target: lo = mid+1 | O(log n) time, O(1) space |
| Right boundary | Last position ≤ target | if arr[mid] > target: hi = mid-1 | O(log n) time, O(1) space |
| Search on answer | Min/max satisfying a condition | Binary search on result space, not array | O(n log n) time |
| Rotated array | Array rotated at pivot point | Check which half is sorted first | O(log n) time |
| 2D matrix search | Sorted matrix, find element | Treat as flattened 1D array | O(log(m×n)) time |
| Algorithm | Time | Space | Use Case |
|---|---|---|---|
| BFS | O(V+E) | O(V) — queue | Shortest path (unweighted), level order |
| DFS | O(V+E) | O(H) — call stack | Cycle detection, topological sort, connected components |
| Dijkstra (min-heap) | O((V+E) log V) | O(V) | Shortest path (non-negative weights) |
| Bellman-Ford | O(V·E) | O(V) | Shortest path (negative weights allowed) |
| Floyd-Warshall | O(V³) | O(V²) | All-pairs shortest path |
| Topological Sort (Kahn) | O(V+E) | O(V) | DAG ordering (build deps, course schedule) |
| Union-Find | O(α(n)) ≈ O(1) | O(V) | Connected components, Kruskal's MST |
| Prim's MST | O(E log V) | O(V) | Minimum spanning tree (dense graphs) |
| Kruskal's MST | O(E log E) | O(V) | Minimum spanning tree (sparse graphs) |
| A* Search | O(E log V) | O(V) | Heuristic shortest path (grid/map) |
| Property | DFS | BFS |
|---|---|---|
| Data structure | Stack (or recursion) | Queue |
| Order | LIFO | FIFO |
| Space complexity | O(H) — tree height | O(W) — max width of level |
| Best when target is | Deep in the tree/graph | Close to the source |
| Tree traversals | Preorder, Inorder, Postorder | Level-order |
| Shortest path | ❌ Not guaranteed | ✅ Guaranteed (unweighted) |
| Cycle detection | ✅ Easy with visited set | ✅ Possible |
| Topological sort | ✅ Natural fit | ✅ Kahn's algorithm |
| Connected components | ✅ Yes | ✅ Yes |
| Memory on wide graphs | ✅ Better | ❌ Can explode |
| Iterative DFS (explicit stack) | Avoids StackOverflowError on deep graphs | Deque as stack: push right, pop right |
| Tree Type | Key Property | Height | Use Case |
|---|---|---|---|
| Binary Tree | Each node ≤ 2 children | O(n) worst | General hierarchical data |
| Binary Search Tree | Left < Node < Right | O(log n) balanced | Ordered search/insert/delete |
| AVL Tree | Balance factor ∈ {-1,0,1} | O(log n) guaranteed | Frequent lookups, balanced BST |
| Red-Black Tree | Colour rules ensure balance | O(log n) guaranteed | Java TreeMap/TreeSet internals |
| Heap (Min/Max) | Parent ≤/≥ children | O(log n) | Priority Queue, Heap Sort |
| Trie | Each edge = one character | O(L) — word length | Autocomplete, prefix search |
| Segment Tree | Each node = range aggregate | O(log n) updates/queries | Range sum/min/max queries |
| Fenwick Tree | BIT — prefix sums | O(log n) updates/queries | Efficient prefix sum with updates |
| B-Tree | Balanced, multi-key nodes | Database indexing (MySQL InnoDB) | |
| B+ Tree | All data in leaves, linked leaf list | Range queries — faster sequential scan than B-Tree | |
| Suffix Tree | Compressed trie of all suffixes | String matching: find substring in O(m) |
| Pattern | Signal in Problem | Formula Shape | Example Problems |
|---|---|---|---|
| Min/Max path to target | "minimum cost/steps to reach" | dp[i] = min(dp[i-1], dp[i-2]…) + cost[i] | Climbing Stairs, Min Cost Path |
| Distinct ways (count) | "how many ways to reach" | dp[i] = dp[i-1] + dp[i-2] + … | Coin Change II, Unique Paths |
| 0/1 Knapsack | "pick or skip each item" | dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt]+val) | 0/1 Knapsack, Subset Sum |
| Unbounded Knapsack | "use item multiple times" | dp[i][w] = max(dp[i-1][w], dp[i][w-wt]+val) | Coin Change, Rod Cutting |
| Longest common substr | "two sequences, align chars" | if s1[i]==s2[j]: dp[i][j]=dp[i-1][j-1]+1 | LCS, Edit Distance |
| Interval DP | "merge/split subproblems" | dp[i][j] = dp[i][k] + dp[k+1][j] + cost | Matrix Chain, Burst Balloons |
| Decision making | "buy/sell or take/skip" | dp[i][0/1] = max(hold, sell/buy) | Best Time to Buy/Sell Stock |
| Palindrome DP | "substring is palindrome" | dp[i][j] = dp[i+1][j-1] if s[i]==s[j] | Palindrome Partitioning, LPS |
| State Compression (Bitmask DP) | Subset of n items (n ≤ 20) | dp[mask] — travelling salesman, assignment problems | |
| Digit DP | Count numbers in [L,R] with property | Process digit by digit, track tight constraint flag |
| Pattern | Key Idea | Pruning Condition | Example Problems |
|---|---|---|---|
| Subsets | Add current element or skip | Skip duplicate nums[i]==nums[i-1] | Subsets I & II |
| Permutations | Pick unused elements in any order | Skip if tempList.contains(nums[i]) | Permutations I & II |
| Combinations | Pick from remaining elements only | remain < 0 → prune branch | Combination Sum I & II |
| Palindrome partition | Check if substring is palindrome before adding | isPalindrome(s, start, i) | Palindrome Partitioning |
| N-Queens | Place queen if no row/col/diagonal conflict | Check column and diagonals | N-Queens, N-Queens II |
| Word Search | DFS on grid, mark visited, unmark on backtrack | Out of bounds or char mismatch | Word Search I & II |
| Sudoku Solver | Try 1-9 for each empty cell, backtrack on conflict | Row/col/box already has digit | Sudoku Solver |
| Memoize overlapping subproblems | Backtracking + cache = top-down DP | If same (index, state) recurs, cache result → avoid exponential blowup |
| Operation | Expression | Result / Use Case |
|---|---|---|
| Check if even/odd | n & 1 | 0 = even, 1 = odd |
| Multiply by 2 | n << 1 | n × 2 (left shift) |
| Divide by 2 | n >> 1 | n ÷ 2 (right shift, floor) |
| Clear last set bit | n & (n-1) | Removes lowest 1-bit — count set bits |
| Extract last set bit | n & (-n) | Isolates lowest 1-bit — Fenwick Tree |
| XOR same values | n ^ n | 0 — find single non-duplicate |
| XOR with zero | n ^ 0 | n — identity property |
| Toggle bit i | n ^ (1 << i) | Flips bit at position i |
| Set bit i | n | (1 << i) | Forces bit i to 1 |
| Clear bit i | n & ~(1 << i) | Forces bit i to 0 |
| Check bit i | (n >> i) & 1 | 1 if bit i is set, else 0 |
| Is power of 2 | n > 0 && (n & (n-1)) == 0 | true if exactly one bit set |
| Brian Kernighan — count set bits | n & (n-1) clears lowest set bit | while(n){ count++; n &= n-1; } → O(set bits) |
| Hamming distance | Number of differing bits between a and b | Integer.bitCount(a ^ b) — XOR then popcount |
| Technique | When to Use | Template Shape | Examples |
|---|---|---|---|
| Two pointers (opposite ends) | Sorted array, find pair with target sum | lo=0, hi=n-1, move inward | Two Sum II, Valid Palindrome |
| Two pointers (same dir) | Remove duplicates, merge sorted arrays | slow=0, fast iterates | Remove Duplicates, Move Zeroes |
| Fixed window | Subarray/substring of size k | Add right, remove left when size>k | Max Sum Subarray of Size K |
| Variable window (expand) | Longest subarray satisfying condition | Expand right, shrink left when violated | Longest Substring Without Repeat |
| Variable window (shrink) | Smallest subarray satisfying condition | Shrink left while condition holds | Minimum Window Substring |
| Fast & slow pointers | Cycle detection in linked list / array | slow moves 1 step, fast moves 2 | Linked List Cycle, Find Duplicate |
| Monotonic Stack | Next greater / smaller element | Maintain decreasing stack; pop when current > top | |
| Monotonic Deque | Sliding window maximum/minimum | Deque stores indices; evict out-of-window and smaller elements from back |
| Big O | Name | Example Operations | n=1M approx ops |
|---|---|---|---|
| O(1) | Constant | Hash lookup, array index, stack push | 1 |
| O(log n) | Logarithmic | Binary search, balanced BST ops | ~20 |
| O(n) | Linear | Linear scan, single loop | 1,000,000 |
| O(n log n) | Linearithmic | Merge sort, heap sort, most good sorts | ~20,000,000 |
| O(n²) | Quadratic | Bubble/insertion/selection sort, nested loops | 10¹² |
| O(2ⁿ) | Exponential | Subsets, recursive Fibonacci without memo | Huge — avoid |
| O(n!) | Factorial | Brute-force permutations | Astronomical — backtrack/prune |
| Pattern | Key Insight | Classic Problems |
|---|---|---|
| Activity Selection | Always pick earliest finish time | Interval scheduling, meeting rooms |
| Fractional Knapsack | Sort by value/weight ratio | Not applicable to 0/1 knapsack |
| Huffman Encoding | Merge two smallest frequencies first | Optimal prefix-free codes, file compression |
| Jump Game | Track max reachable index at each step | LeetCode 55 — greedy beats DP here |
| Interval Merging | Sort by start, merge overlapping | Merge Intervals (LeetCode 56) |
| Two-City Scheduling | Sort by cost difference (A-B) | Greedy assignment with constraint |
| Operation | Complexity | Notes |
|---|---|---|
| find(x) with path compression | O(α(n)) ≈ O(1) | Flatten tree on every find call |
| union(x, y) with rank | O(α(n)) ≈ O(1) | Attach smaller tree under larger |
| Connected components | O(E · α(V)) | Process all edges, count distinct roots |
| Cycle detection (undirected) | O(E · α(V)) | Union returns false if same component → cycle |
| Kruskal's MST | O(E log E + E · α(V)) | Sort edges by weight, union if different components |
| Template | parent[i]=i; rank[i]=0 | find: if parent[i]!=i: parent[i]=find(parent[i]); return parent[i] |
| Operation | Complexity | Use Case |
|---|---|---|
| insert(word) | O(m) — m = word length | Build dictionary, autocomplete index |
| search(word) | O(m) | Exact word lookup |
| startsWith(prefix) | O(m) | Autocomplete, IP routing |
| delete(word) | O(m) | Unmark isEnd; prune empty nodes |
| Word Search II | Trie + DFS on board | Prune branches early — far faster than brute force |
| Structure | TrieNode{ children[26], isEnd } | children = new TrieNode[26] or HashMap for Unicode |