20 LeetCode Patterns Chinh Phục FAANG: Từ 3000 Bài Toán Đến Hệ Thống Tư Duy “Nhìn Là Biết”

Bạn có bao giờ mở LeetCode, nhìn vào danh sách hơn 3000 bài toán, và tự hỏi: “Làm sao để học cho hết?”. Tin tốt là bạn không cần phải giải hết. Theo thống kê từ những người đã vượt qua vòng phỏng vấn của các công ty như Meta, Amazon, Apple, Netflix, Google (FAANG), khoảng 80% bài toán thuộc về 18-20 pattern cốt lõi. Chỉ cần làm chủ các khuôn mẫu này, bạn có thể nhận diện bài toán trong vòng 60 giây và áp dụng template giải quyết chính xác.

Trong bài viết này, tôi sẽ dẫn bạn đi qua từng pattern một cách có hệ thống: từ tín hiệu nhận biết, mô hình tư duy, bộ khung code, cho đến những bài tập điển hình. Bài viết đóng vai trò như một lộ trình 8-12 tuần, giúp bạn xây dựng năng lực giải thuật vững chắc cho kỳ phỏng vấn FAANG.

Tại Sao Học Theo Pattern Là Chìa Khóa?

Khi mới làm quen với LeetCode, nhiều người mắc kẹt trong vòng lặp: làm bài, không làm được, xem lời giải, chép lại, rồi quên. Nguyên nhân là họ không trừu tượng hóa được mẫu số chung giữa các bài toán. Học theo pattern giống như học võ công: mỗi chiêu thức (pattern) có một bộ khung cử động (template), khi đối thủ (đề bài) ra đòn, bạn nhận ra ngay nên dùng chiêu nào để phản công thay vì suy nghĩ từng động tác riêng lẻ.

Cách học hiệu quả nhất là:

Đọc từng pattern một, hiểu tín hiệu (signal) và nguyên lý hoạt động (mental model).
Luyện tập 5-7 bài cho mỗi pattern để bộ não ghi nhớ.
Ôn tập luân phiên: mỗi tuần học pattern mới, đồng thời quay lại pattern cũ với 2-3 bài mới.
Mô phỏng phỏng vấn để kiểm tra tốc độ nhận diện pattern trong vòng 60 giây.

Cấu Trúc Của Một Pattern Trong Bài Viết

Mỗi phần dưới đây sẽ được tổ chức theo khung:

Tín hiệu nhận diện (Signal): Những cụm từ khóa trong đề bài gợi ý pattern nào.
Mô hình tư duy (Mental Model): Cơ chế hoạt động cốt lõi, bất biến (invariant) cần duy trì.
Bộ khung code (Template): Code skeleton bằng Java (dễ chuyển sang ngôn ngữ khác).
Bài toán minh họa: Walkthrough một bài kinh điển (thường kèm UMPIRE: Understand, Match, Plan, Implement, Review, Evaluate).
Danh sách bài luyện tập và những lỗi thường gặp.

PHẦN 1: ARRAY & HASHING (Mảng và Băm)

Pattern 1: Hash Map Tần Suất / Tra Cứu (HashMap Frequency / Lookup)

Tín hiệu:

“Tìm cặp/bộ ba có tổng bằng X” (Two Sum, Three Sum)
“Phần tử đầu tiên không lặp lại”
“Nhóm các anagram”
“Kiểm tra phần tử trùng lặp”

Mental Model:
Hãy đánh đổi không gian bộ nhớ để lấy thời gian. Thay vì duyệt lặp O(n²), ta lưu các phần tử đã thấy vào HashMap với chi phí tra cứu O(1). Nguyên lý cốt lõi: cái gì cần tìm kiếm nhiều lần, hãy ghi nhớ nó.

Template (Two Sum):

Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (seen.containsKey(complement)) {
        return new int[]{seen.get(complement), i};
    }
    seen.put(nums[i], i);
}

Ví dụ: LC 1 – Two Sum. Dùng HashMap lưu giá trị và chỉ số, mỗi lần kiểm tra target – nums[i] đã gặp chưa. Độ phức tạp O(n) thay vì O(n²).

Bài luyện thêm: LC 49 (Group Anagrams), LC 217 (Contains Duplicate), LC 347 (Top K Frequent Elements), LC 128 (Longest Consecutive Sequence), LC 36 (Valid Sudoku).

Lỗi thường gặp:

So sánh Integer == Integer dẫn đến lỗi với giá trị > 127. Luôn dùng .equals().
Quên override equals/hashCode khi dùng class tự định nghĩa làm key.

Pattern 2: Mảng Tiền Tố (Prefix Sum)

Tín hiệu:

“Tính tổng đoạn con từ i đến j”
“Số lượng đoạn con có tổng bằng K”
“Tổng lớn nhất/nhỏ nhất của đoạn con”

Mental Model:
Xây dựng mảng prefix trong đó prefix[i] là tổng các phần tử từ 0 đến i-1. Khi đó, tổng đoạn [l, r] tính trong O(1): prefix[r+1] - prefix[l].
Bất biến: prefix[0] = 0 (đoạn rỗng).

Template:

int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
// Range sum [l..r] = prefix[r+1] - prefix[l]

Ví dụ: LC 560 – Subarray Sum Equals K. Thay vì duyệt tất cả các cặp, ta lưu tần suất xuất hiện của từng giá trị prefix đã thấy. Khi gặp prefix[j], kiểm tra xem prefix[j] - k đã xuất hiện bao nhiêu lần.

Bài luyện tập: LC 303, LC 304, LC 238 (Product of Array Except Self), LC 525.

PHẦN 2: CON TRỎ KÉP (Two Pointers)

Pattern 3: Kỹ Thuật Hai Con Trỏ

Tín hiệu:

“Mảng đã sắp xếp” + “tìm cặp”
“Kiểm tra palindrome”
“Loại bỏ phần tử trùng lặp tại chỗ”
“Đảo chuỗi/mảng”
“Container chứa nước nhiều nhất”

Mental Model:
Sử dụng hai con trỏ left và right, di chuyển chúng dựa trên một điều kiện nào đó để thu hẹp không gian tìm kiếm. Mỗi bước loại bỏ một phần không gian, giảm từ O(n²) xuống O(n).

Biến thể:

Đối đầu: left bắt đầu từ 0, right từ n-1, tiến dần vào giữa.
Nhanh & chậm: Cả hai cùng xuất phát, nhưng khác tốc độ (dùng trong linked list).
Cùng chiều: Duy trì một cửa sổ.

Template (đối đầu):

int left = 0, right = nums.length - 1;
while (left < right) {
    if (condition_met) return ...;
    if (need_smaller) right--;
    else left++;
}

Ví dụ: LC 167 – Two Sum II (mảng đã sắp xếp). Di chuyển left và right dựa trên tổng so với target. Không dùng thêm bộ nhớ phụ, O(n) time, O(1) space.
LC 15 – 3Sum: Cố định một phần tử, dùng two pointers cho hai phần tử còn lại, cẩn thận bỏ qua các giá trị trùng lặp.

Bài luyện tập: LC 125, LC 11 (Container With Most Water), LC 42 (Trapping Rain Water – Hard), LC 26, LC 283.

PHẦN 3: CỬA SỔ TRƯỢT (Sliding Window)

Pattern 4: Sliding Window (Cửa Sổ Trượt)

Tín hiệu:

“Dãy con dài nhất/ngắn nhất thỏa mãn tính chất X”
“Tổng lớn nhất của dãy con có độ dài K”
“Số lượng dãy con có K phần tử phân biệt”
“Chuỗi con nhỏ nhất chứa tất cả ký tự của T”

Mental Model:
Duy trì một cửa sổ [left, right] thỏa mãn ràng buộc. Mở rộng right qua mỗi vòng lặp; nếu vi phạm điều kiện, co left cho đến khi hợp lệ trở lại. Kết quả tốt nhất được cập nhật liên tục.

Hai biến thể:

Cửa sổ cố định: Độ dài luôn bằng K.
Cửa sổ động: Co giãn theo ràng buộc.

Template (động):

int left = 0, result = 0;
WindowState state = ...; // HashMap, count[], sum...
for (int right = 0; right < n; right++) {
    state.add(arr[right]);   // mở rộng
    while (state.violatesConstraint()) {
        state.remove(arr[left]);  // thu hẹp
        left++;
    }
    result = Math.max(result, right - left + 1); // ghi nhận
}

Ví dụ: LC 3 – Longest Substring Without Repeating Characters. Sử dụng HashMap lưu chỉ số cuối cùng của từng ký tự. Khi gặp ký tự đã tồn tại và nằm trong cửa sổ, di chuyển left đến sau vị trí trùng.
LC 76 – Minimum Window Substring (Hard): Dùng mảng đếm nhu cầu ký tự, khi required == 0 thì cửa sổ hợp lệ, co left để tìm cửa sổ nhỏ nhất.

Bài luyện tập: LC 424, LC 567, LC 209, LC 239 (Sliding Window Maximum – dùng deque), LC 1004.

PHẦN 4: NGĂN XẾP (Stack)

Pattern 5: Stack & Stack Đơn Điệu (Monotonic Stack)

Tín hiệu:

“Dấu ngoặc hợp lệ”
“Phần tử lớn hơn/nhỏ hơn tiếp theo” (Next Greater/Smaller Element)
“Nhiệt độ hàng ngày” (Daily Temperatures)
“Hình chữ nhật lớn nhất trong biểu đồ”
“Tính giá trị biểu thức”

Mental Model (Monotonic Stack):
Duy trì stack có tính đơn điệu (tăng dần hoặc giảm dần). Khi phần tử mới vi phạm tính đơn điệu, pop các phần tử ra khỏi stack và xử lý câu trả lời cho chúng. Mỗi phần tử được push/pop đúng một lần → O(n).

Template (Next Greater Element):

int[] result = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // lưu index
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        result[stack.pop()] = nums[i];
    }
    stack.push(i);
}
// Các index còn lại trong stack không có "next greater" -> gán -1 hoặc 0

Ví dụ: LC 739 – Daily Temperatures. Tìm số ngày chờ để có nhiệt độ cao hơn. Stack lưu index, khi temperatures[i] > temperatures[stack.peek()], tính khoảng cách.
LC 84 – Largest Rectangle in Histogram (Hard): Dùng stack tăng dần, khi gặp cột thấp hơn, tính diện tích hình chữ nhật với chiều cao của cột bị pop.

Bài luyện tập: LC 20, LC 155 (Min Stack), LC 150, LC 22, LC 853 (Car Fleet), LC 42 (cũng có thể làm bằng stack).

Lưu ý: Trong Java, dùng ArrayDeque thay vì Stack (cũ, synchronized, chậm). Luôn lưu index thay vì giá trị để giữ thông tin vị trí.

PHẦN 5: TÌM KIẾM NHỊ PHÂN (Binary Search)

Pattern 6: Binary Search Cổ Điển & “Tìm Kiếm Trên Đáp Án”

Tín hiệu:

“Mảng đã sắp xếp” + “tìm phần tử”
“Mảng xoay vòng đã sắp xếp” (Rotated Sorted Array)
“Tìm đỉnh/thung lũng”
“Tối ưu hóa” (tìm tốc độ ăn nhỏ nhất, sức chứa tàu…)

Mental Model:
Duy trì bất biến: target luôn nằm trong đoạn [left, right]. Mỗi vòng lặp loại bỏ một nửa không gian, đưa về O(log n).
Công thức tránh tràn số: mid = left + (right - left) / 2.
Khi áp dụng cho bài toán tối ưu, ta “đoán” một đáp án, kiểm tra tính khả thi bằng vòng lặp O(n), rồi thu hẹp phạm vi tìm kiếm.

Template chuẩn:

int left = 0, right = arr.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}

Ví dụ:
LC 33 – Search in Rotated Sorted Array. Xác định nửa nào đã sắp xếp, kiểm tra target có nằm trong đó không để quyết định hướng tìm.
LC 875 – Koko Eating Bananas. Không gian đáp án từ 1 đến max(piles). Với mỗi tốc độ k, tính tổng giờ ăn sum(ceil(pile/k)). Nếu hours <= h, có thể thử tốc độ nhỏ hơn.

Bài luyện tập: LC 704, LC 153, LC 4 (Median of Two Sorted Arrays – Hard), LC 1011, LC 74, LC 162.

Lỗi điển hình:

Dùng (left+right)/2 gây tràn số → dùng left + (right - left)/2.
Nhầm điều kiện while (left < right) vs while (left <= right) tùy invariant.

PHẦN 6: DANH SÁCH LIÊN KẾT (Linked List)

Pattern 7: Con Trỏ Nhanh & Chậm + Đảo Ngược

Tín hiệu:

“Phát hiện chu kỳ trong danh sách liên kết”
“Tìm phần tử giữa”
“Đảo ngược danh sách”
“Trộn hai danh sách đã sắp xếp”
“Xóa node thứ N từ cuối”

Mental Model:

Floyd’s Cycle Detection: slow đi 1 bước, fast đi 2 bước. Nếu có chu kỳ, fast sẽ bắt kịp slow. Khi fast chạm cuối, slow đang ở giữa.
Đảo ngược: Dùng 3 con trỏ prev, curr, next để lật liên kết.

Template đảo ngược:

ListNode prev = null, curr = head;
while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
}
return prev;

Ví dụ:
LC 141 – Linked List Cycle. Dùng fast & slow.
LC 19 – Remove Nth Node From End. Dùng hai con trỏ cách nhau n bước; khi fast đến cuối, slow đứng trước node cần xóa. Luôn dùng dummy node để đơn giản hóa việc xóa head.

Bài luyện tập: LC 206, LC 21, LC 142, LC 143, LC 23 (Merge K Sorted Lists – Hard).

PHẦN 7: CÂY (Trees)

Pattern 8: Duyệt Cây Theo Chiều Sâu (DFS – Đệ Quy)

Tín hiệu:

Mọi bài toán với cây nhị phân: “độ sâu tối đa”, “đường đi có tổng lớn nhất”, “kiểm tra BST”, “tổ tiên chung thấp nhất”…

Mental Model – Leap of Faith:

Xác định giá trị mà hàm đệ quy trả về cho một node.
Điều kiện dừng cơ sở (null): trả về giá trị đơn vị (identity).
Tin tưởng rằng lời gọi đệ quy cho cây con trái và phải sẽ đúng, sau đó kết hợp kết quả.

Template:

ReturnType dfs(TreeNode node) {
    if (node == null) return baseValue;
    ReturnType left = dfs(node.left);
    ReturnType right = dfs(node.right);
    return combine(node, left, right);
}

Ví dụ: LC 124 – Binary Tree Maximum Path Sum (Hard). Hàm maxGain(node) trả về lợi ích tối đa của đường đi bắt đầu từ node đi xuống một nhánh. Trong quá trình, cập nhật đường đi “qua” node (tổng của node + nhánh trái + nhánh phải) cho đáp án toàn cục.
LC 236 – Lowest Common Ancestor: Nếu root là p hoặc q, trả về root; nếu trái và phải đều trả về khác null, đó là LCA.

Bài luyện tập: LC 104, LC 226, LC 98, LC 297, LC 105.

Pattern 9: Duyệt Cây Theo Chiều Rộng (BFS – Level Order)

Tín hiệu:

“Duyệt theo từng tầng” (Level Order Traversal), “góc nhìn từ bên phải”, “zigzag”, “độ sâu tối thiểu”.

Template:

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    int levelSize = queue.size();
    for (int i = 0; i < levelSize; i++) {
        TreeNode node = queue.poll();
        // xử lý node
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

Ví dụ: LC 199 – Binary Tree Right Side View. Duyệt BFS, ghi nhận node cuối cùng của mỗi tầng (i == size-1).
Bài tập: LC 102, 107, 103, 515.

PHẦN 8: CÂY TIỀN TỐ (Trie)

Pattern 10: Trie (Prefix Tree)

Tín hiệu:

“Tiền tố phù hợp” (prefix matching), “autocomplete”, “tìm kiếm từ trong lưới”, “cài đặt từ điển”.

Mental Model:
Mỗi node đại diện một ký tự, đường đi từ gốc đến node tạo thành một xâu. Node lá (hoặc node kết thúc) đánh dấu một từ hoàn chỉnh. Tất cả thao tác (chèn, tìm kiếm) đều có độ phức tạp O(L) với L là độ dài từ.

Template:

class Trie {
    Trie[] children = new Trie[26];
    boolean isEnd;

    void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new Trie();
            node = node.children[i];
        }
        node.isEnd = true;
    }

    boolean search(String word) { ... }
    boolean startsWith(String prefix) { ... }
}

Ví dụ: LC 208 – Implement Trie. Cài đặt đầy đủ các phương thức.
LC 212 – Word Search II (Hard): Chèn tất cả từ cần tìm vào Trie, sau đó DFS từ mỗi ô trong bảng; cắt tỉa sớm bằng Trie để giảm không gian tìm kiếm.

Bài luyện tập: LC 211 (Add and Search Word).

PHẦN 9: HEAP / HÀNG ĐỢI ƯU TIÊN (Priority Queue)

Pattern 11: Heap (Top-K, Trộn K Phần Tử)

Tín hiệu:

“K phần tử lớn nhất/nhỏ nhất”
“Top K thường xuyên nhất”
“Trung vị trong dòng dữ liệu”
“Trộn K danh sách đã sắp xếp”
“Lập lịch công việc”

Mental Model:

Min-heap: gốc là phần tử nhỏ nhất. Muốn Top K lớn nhất → dùng min-heap kích thước K (loại bỏ phần tử nhỏ nhất khi vượt quá K, giữ lại K lớn nhất).
Max-heap: ngược lại, dùng cho Top K nhỏ nhất.

Template Top K:

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
    minHeap.offer(n);
    if (minHeap.size() > k) minHeap.poll();
}
// Top K lớn nhất nằm trong heap (không đảm bảo thứ tự)

Ví dụ: LC 215 – Kth Largest Element. Dùng min-heap kích thước K.
LC 295 – Find Median from Data Stream: Dùng hai heap: max-heap cho nửa nhỏ, min-heap cho nửa lớn, luôn giữ cân bằng. Trung vị nằm ở đỉnh của một hoặc trung bình hai đỉnh.

Bài luyện tập: LC 347, LC 23 (Merge K Sorted Lists – dùng min-heap), LC 692, LC 1046.

Lưu ý: PriorityQueue mặc định là min-heap. Khi dùng comparator như (a,b)->a-b cần cẩn thận tràn số.

PHẦN 10: QUAY LUI (Backtracking)

Pattern 12: Backtracking (Liệt Kê Tổ Hợp – Hoán Vị – Tập Con)

Tín hiệu:

“Tất cả tổ hợp/hoán vị/tập con”
“Sinh tất cả dãy ngoặc hợp lệ”
“Bài toán N-Queens”
“Giải Sudoku”
“Word Search / Word Break”

Mental Model:
Xây dựng cây quyết định: tại mỗi bước, chọn một lựa chọn, đệ quy, rồi hủy lựa chọn đó để thử lựa chọn khác. Quy tắc vàng: luôn “un-choose” (backtrack) để trả trạng thái về trước khi thử nhánh khác.

Template (Subsets):

void backtrack(List<Integer> path, int[] nums, int start, List<List<Integer>> result) {
    result.add(new ArrayList<>(path)); // ghi nhận trạng thái hiện tại
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);           // chọn
        backtrack(path, nums, i + 1, result);
        path.remove(path.size() - 1); // hủy chọn
    }
}

Ví dụ:
LC 78 – Subsets. Template trên sinh tất cả tập con.
LC 46 – Permutations. Cần mảng boolean[] used để tránh chọn lại cùng phần tử.
LC 79 – Word Search. Đánh dấu ô đã thăm bằng ký tự đặc biệt, thử 4 hướng, sau đó khôi phục (backtrack) khi quay lui.

Bài luyện tập: LC 90, LC 47, LC 39/40 (Combination Sum), LC 51 (N-Queens), LC 131 (Palindrome Partitioning).

Lỗi thường gặp:

Quên new ArrayList<>(path) khi thêm vào kết quả, dẫn đến tất cả phần tử cùng tham chiếu một list bị thay đổi.
Không khôi phục trạng thái (visited flag, path), làm sai kết quả các nhánh sau.

PHẦN 11: ĐỒ THỊ (Graphs)

Pattern 13: BFS/DFS Trên Đồ Thị & Lưới

Tín hiệu:

“Số lượng hòn đảo”
“Clone đồ thị”
“Word Ladder”
“Lịch học (Course Schedule)”
“Thành phần liên thông”

Mental Model:
Biểu diễn đồ thị bằng danh sách kề (Map hoặc List<List>) hoặc lưới 2D.

BFS: Tìm đường đi ngắn nhất (không trọng số), duyệt theo tầng.
DFS: Khám phá sâu, thường dùng đệ quy hoặc stack, phát hiện chu trình, sắp xếp topo.
Cả hai đều cần đánh dấu đã thăm.

Template DFS lưới (số hòn đảo):

void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;
    grid[r][c] = '0'; // đánh dấu đã thăm (in-place)
    for (int[] d : dirs) dfs(grid, r + d[0], c + d[1]);
}

Ví dụ:
LC 200 – Number of Islands. Đếm số lần gọi DFS khi gặp đất ‘1’.
LC 207 – Course Schedule (Topological Sort). Dùng Kahn’s algorithm: đếm indegree, BFS từ các đỉnh có indegree = 0, giảm indegree khi thăm. Nếu số môn học lấy được bằng numCourses → không có chu trình.

Bài luyện tập: LC 133, LC 210, LC 127 (Word Ladder – BFS tìm đường ngắn nhất), LC 695, LC 417, LC 994.

Pattern 14: Đồ Thị Nâng Cao (Dijkstra, Union-Find)

Khi nào dùng:

Dijkstra: Đường đi ngắn nhất có trọng số dương, biểu diễn bằng heap.
Union-Find (Disjoint Set Union): Quản lý các tập hợp không giao nhau, kiểm tra liên thông, phát hiện chu trình trong đồ thị không hướng. Gần như O(1) mỗi thao tác nhờ path compression và union by rank.

Template Union-Find:

class UnionFind {
    int[] parent, rank;
    int components;
    UnionFind(int n) {
        parent = new int[n]; rank = new int[n]; components = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) { 
        if (parent[x] != x) parent[x] = find(parent[x]); 
        return parent[x]; 
    }
    boolean union(int x, int y) { 
        int px = find(x), py = find(y);
        if (px == py) return false;
        // union by rank
        ...
        components--;
        return true;
    }
}

Bài luyện tập: LC 743 (Network Delay Time – Dijkstra), LC 787 (Cheapest Flights – Bellman-Ford), LC 547 (Friend Circles – Union-Find), LC 684.

PHẦN 12: QUY HOẠCH ĐỘNG (Dynamic Programming)

Pattern 15: Quy Hoạch Động 1 Chiều (1-D DP)

Tín hiệu:

“Số cách để…”
“Chi phí nhỏ nhất / lợi nhuận lớn nhất để…”
“Dãy con dài nhất / ngắn nhất”
“Có thể đạt được…?”

Mental Model:
Định nghĩa dp[i] là đáp án cho i phần tử đầu tiên (hoặc kết thúc tại i). Tìm công thức truy hồi: dp[i] phụ thuộc vào dp[i-1], dp[i-2], ….
Có thể triển khai bottom-up (lặp) để tiết kiệm bộ nhớ, thường chỉ cần 1-2 biến.

Ví dụ:
LC 70 – Climbing Stairs. dp[i] = dp[i-1] + dp[i-2]. Dùng hai biến prev2, prev1.
LC 198 – House Robber. Tại mỗi nhà, quyết định có cướp hay không: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
LC 300 – Longest Increasing Subsequence. DP O(n²): dp[i] = max(dp[j] + 1) với mọi j < i và nums[j] < nums[i]. Còn có cách O(n log n) bằng patience sorting.

Bài luyện tập: LC 213, LC 322 (Coin Change), LC 139 (Word Break), LC 152, LC 91.

Pattern 16: Quy Hoạch Động 2 Chiều (2-D DP)

Tín hiệu:

Hai chuỗi / hai mảng (bài toán dãy con chung, khoảng cách chỉnh sửa)
Lưới (bài toán đường đi)

Ví dụ:
LC 1143 – Longest Common Subsequence. dp[i][j] là LCS của text1[0..i-1] và text2[0..j-1]. Nếu ký tự giống nhau: dp[i][j] = dp[i-1][j-1] + 1; nếu khác: max(dp[i-1][j], dp[i][j-1]).
LC 72 – Edit Distance (Hard). Ba thao tác: xóa, chèn, thay thế. dp[i][j] cho biết số bước ít nhất.
LC 416 – Partition Equal Subset Sum. Quy về bài toán knapsack: có tập con nào tổng bằng target không. DP 1 chiều nhưng nên coi là dạng DP tập con.

Bài luyện tập: LC 583, LC 62, LC 64, LC 174, LC 494.

Lỗi chung về DP: Quên xác định base case; nhầm chỉ số giữa mảng và bảng DP (thường lệch 1); nhầm lẫn giữa dãy con liên tiếp (substring/subarray) và không liên tiếp (subsequence).

PHẦN 13: THAM LAM & KHOẢNG (Greedy & Intervals)

Pattern 17: Tham Lam (Greedy)

Tín hiệu:

“Số bước tối thiểu để…”
“Lợi nhuận tối đa / số cuộc họp tối đa”
Bài toán lập lịch, nhảy (Jump Game), trạm xăng.

Mental Model:
Tại mỗi bước, chọn phương án tốt nhất ngay lập tức (local optimum) với hy vọng đạt global optimum. Cần chứng minh tính đúng đắn vì không phải lúc nào greedy cũng hiệu quả.

Ví dụ:
LC 55 – Jump Game. Duy trì biến maxReach xa nhất có thể đến. Nếu chỉ số hiện tại vượt quá maxReach, không thể đến đích.
LC 134 – Gas Station. Tính tổng khí tịnh, nếu tổng < 0 thì không thể đi hết. Nếu bình xăng tạm thời âm, reset điểm xuất phát.

Bài luyện tập: LC 45 (Jump Game II), LC 763 (Partition Labels).

Pattern 18: Khoảng (Intervals – Sắp Xếp + Xử Lý Đoạn Giao Nhau)

Tín hiệu:

“Gộp các khoảng”, “chèn khoảng”, “phòng họp tối thiểu”, “xoá khoảng để không chồng lấn”.

Mental Model:
Sắp xếp các khoảng theo thời điểm bắt đầu (hoặc kết thúc), sau đó xử lý tuần tự.

Template:

Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // sắp xếp theo start

Ví dụ:
LC 56 – Merge Intervals. Duyệt qua danh sách đã sắp xếp, nếu khoảng hiện tại chồng lấn với khoảng trước đó, cập nhật điểm kết thúc lớn nhất.
LC 253 – Meeting Rooms II. Dùng min-heap lưu thời điểm kết thúc các cuộc họp đang diễn ra; với mỗi cuộc họp mới, nếu có phòng trống (kết thúc sớm nhất <= bắt đầu), pop ra rồi push kết thúc mới. Kích thước heap là số phòng tối thiểu.
LC 435 – Non-overlapping Intervals. Sắp xếp theo end, greedy chọn các khoảng không chồng lấn.

Bài luyện tập: LC 57, LC 252 (Meeting Rooms I), LC 1851.

PHẦN 14: TOÁN HỌC & XỬ LÝ BIT (Math & Bit Manipulation)

Pattern 19: Toán Học Cần Nhớ

Một số thủ thuật thường dùng:

GCD (Ước chung lớn nhất): gcd(a,b) = b == 0 ? a : gcd(b, a%b).
LCM: lcm(a,b) = a / gcd(a,b) * b (nhân sau khi chia để tránh tràn).
Lũy thừa nhanh (modulo): Dùng phép bình phương và nhân, O(log n).

Bài tiêu biểu: LC 50 – Pow(x, n). Xét dấu mũ âm, dùng lũy thừa nhanh.

Pattern 20: Xử Lý Bit (Bit Manipulation)

Tín hiệu:

“Số xuất hiện một lần, còn lại hai lần” (Single Number)
Các thao tác bit cơ bản: đếm bit 1, đảo bit, phép XOR.

Các thủ thuật:

x & 1 : kiểm tra lẻ/chẵn
x & (x - 1) : tắt bit 1 thấp nhất (Brian Kernighan’s algorithm)
x ^ x = 0, x ^ 0 = x

Ví dụ:
LC 136 – Single Number. XOR tất cả các phần tử, kết quả là số duy nhất.
LC 191 – Number of 1 Bits. Dùng n & (n-1) để đếm.
LC 338 – Counting Bits. Quy hoạch động kết hợp bit: dp[i] = dp[i >> 1] + (i & 1).

Lộ Trình 8-12 Tuần: Học Và Ôn Tập

Để chinh phục 20 pattern này, bạn có thể phân bổ thời gian như sau:

Tuần 1-2: Patterns 1-3 (Hashing, Prefix Sum, Two Pointers) – 20 bài
Tuần 3-4: Patterns 4-6 (Sliding Window, Stack, Binary Search) – 20 bài
Tuần 5-6: Patterns 7-9 (Linked List, Tree DFS+BFS, Trie) – 20 bài
Tuần 7-8: Patterns 10-12 (Heap, Backtracking, Graph) – 25 bài
Tuần 9-10: Patterns 13-16 (Advanced Graph, 1D-DP, 2D-DP, Greedy, Intervals) – 30 bài
Tuần 11-12: Patterns 17-20 (Math, Bit) + Mock Interviews – 15 bài + 6 lần phỏng vấn thử

Tổng cộng khoảng 130 bài, đủ để bao quát NeetCode 150 và Blind 75.

Theo dõi tiến độ bằng spreadsheet hoặc Notion với các cột: Ngày, Problem, Pattern, Độ khó, Thời gian giải, Đã xong?, Ghi chú. Ví dụ:

Date	Problem	Pattern	Difficulty	Time	Solved?	Notes
5/1	LC 1	Hashing	Easy	18m	✅
5/2	LC 49	Hashing	Medium	35m	⚠️	Quên sort

Checklist Thành Thạo: Ba Cấp Độ

Cấp độ 1 – Nhận diện Pattern (60 giây):
Chọn ngẫu nhiên 20 bài, đoán đúng pattern ≥ 16/20.

Cấp độ 2 – Phản xạ Template:
Viết được template mỗi pattern không cần tra cứu. Tùy chỉnh template cho biến thể trong 5 phút.

Cấp độ 3 – Giải trọn vẹn:
Giải một bài Medium trong 25 phút, dùng phương pháp UMPIRE, vừa code vừa “narrate” suy nghĩ (kỹ năng cần cho phỏng vấn thực tế). Tự động kiểm tra edge cases, tính toán độ phức tạp.

Những Bẫy Kinh Điển Cần Tránh

Tràn số: (left + right)/2 → nên dùng left + (right-left)/2; ưu tiên long nếu tổng có thể vượt Integer.MAX_VALUE.
Off-by-one: Luôn kiểm tra điều kiện vòng lặp (< n hay <= n), chỉ số 0-based hay 1-based.
Edge cases tối thiểu cho mỗi bài: Mảng rỗng, một phần tử, toàn giá trị giống nhau, toàn bộ trùng lặp, đầu vào đã sắp xếp/đảo ngược, số âm, tràn số.
Java riêng: So sánh Integer với == chỉ an toàn đến 127; Stack cũ chậm, thay bằng ArrayDeque; PriorityQueue mặc định min-heap; Arrays.asList trả về list immutable size.
Đệ quy sâu: Java stack mặc định chỉ ~10K frame, bài toán quá sâu cần chuyển sang vòng lặp + stack thủ công.

Tóm Lại

Hành trình chinh phục phỏng vấn FAANG không phải là giải thật nhiều bài, mà là giải đúng trọng tâm. Hai mươi pattern trên chính là “bảng cửu chương” của mọi bài LeetCode. Hãy học từng pattern một cách chậm rãi, thực hành đều đặn, và tự kiểm tra bằng mock interview.

Chúc bạn sớm nhận được thư mời làm việc từ công ty mơ ước!

20 LeetCode Patterns Chinh Phục FAANG: Từ 3000 Bài Toán Đến Hệ Thống Tư Duy “Nhìn Là Biết”