| Two Pointers |
Làm việc với mảng đã sort, tìm cặp giá trị thỏa điều kiện |
O(n) |
O(1) |
Two Sum II, 3Sum, Container With Most Water |
| Sliding Window |
Tìm đoạn liên tiếp (subarray/substring) thỏa điều kiện |
O(n) |
O(k) (tuỳ cache/hashset) |
Longest Substring Without Repeating Characters, Min Size Subarray Sum |
| Prefix Sum |
Tính nhanh tổng đoạn con |
O(n) tiền xử lý, O(1) mỗi query |
O(n) |
Subarray Sum Equals K, Range Sum Query |
| Binary Search |
Mảng đã sort, hoặc khi tìm ngưỡng (threshold) |
O(log n) |
O(1) |
Binary Search, Search in Rotated Array, Find Minimum in Rotated Sorted Array |
| Depth-First Search (DFS) |
Duyệt cây, đồ thị, sinh tổ hợp |
O(n) đến O(2^n) tùy bài |
O(h) (đệ quy theo chiều sâu) |
Permutations, Subsets, Graph Traversal |
| Breadth-First Search (BFS) |
Tìm đường ngắn nhất trong đồ thị/cây |
O(n) |
O(n) (queue) |
Binary Tree Level Order, Word Ladder |
| Dynamic Programming (DP) |
Bài toán có lặp lại, chia nhỏ, tối ưu hóa |
O(n), O(n²)… tùy bài |
O(n) hoặc O(n²) |
House Robber, Climbing Stairs, Longest Increasing Subsequence |
| Greedy |
Tối ưu bài toán theo bước từng phần, không quay lại |
O(n log n) hoặc O(n) |
O(1) |
Jump Game, Interval Scheduling, Greedy Coin Change |
| Backtracking |
Sinh tổ hợp/phân nhánh toàn bộ (brute-force có kiểm soát) |
O(2^n) hoặc O(n!) |
O(n) |
N-Queens, Sudoku Solver, Generate Parentheses |
| Heap / Priority Queue |
Cần lấy phần tử lớn nhất/nhỏ nhất nhanh chóng |
O(n log k) |
O(k) |
Top K Elements, Merge K Sorted Lists |
| Union-Find (DSU) |
Kiểm tra kết nối thành phần trong đồ thị |
O(α(n)) (gần như hằng số) |
O(n) |
Number of Connected Components, Kruskal MST |
O(n)O(1)O(n)O(k)(tuỳ cache/hashset)O(n)tiền xử lý,O(1)mỗi queryO(n)O(log n)O(1)O(n)đếnO(2^n)tùy bàiO(h)(đệ quy theo chiều sâu)O(n)O(n)(queue)O(n),O(n²)… tùy bàiO(n)hoặcO(n²)O(n log n)hoặcO(n)O(1)O(2^n)hoặcO(n!)O(n)O(n log k)O(k)O(α(n))(gần như hằng số)O(n)