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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |