Problem-Solving Patterns & Techniques: Hướng Dẫn Toàn Diện

Giới Thiệu

Bạn đã học Big O notation và có thể phân tích complexity. Nhưng khi gặp bài toán mới, làm sao để thực sự giải nó?

Bí mật là hầu hết các bài toán coding đều theo các pattern lặp đi lặp lại. Khi nhận ra pattern, solution trở nên rõ ràng. Người giải bài giỏi không phát minh thuật toán mới cho mỗi bài — họ match bài toán với pattern đã biết và điều chỉnh.

"Mỗi bài toán bạn giải cho bạn một công cụ để giải bài tiếp theo."
— Insight cốt lõi của giải bài theo pattern.

Những Gì Bạn Sẽ Học

✅ Áp dụng framework giải bài có hệ thống cho mọi coding challenge
✅ Thành thạo Two Pointers cho bài toán array và string
✅ Sử dụng Sliding Window cho tối ưu subarray/substring
✅ Tận dụng Hash Maps cho O(1) lookups và đếm tần suất
✅ Áp dụng Prefix Sum cho range queries hiệu quả
✅ Hiểu Divide and Conquer cho phân rã bài toán đệ quy
✅ Sử dụng Recursion và Backtracking cho tìm kiếm toàn diện
✅ Nhận diện pattern nào phù hợp với loại bài nào

Điều Kiện Tiên Quyết

Hiểu Big O Notation & Phân Tích Độ Phức Tạp
Kiến thức lập trình cơ bản (arrays, loops, functions)
Quen thuộc với TypeScript HOẶC Python

1. Framework Giải Bài

Phương Pháp UMPIRE

U — Understand (Hiểu bài toán)

Đọc bài kỹ (đọc hai lần!)
Xác định inputs và outputs
Làm rõ constraints (kích thước, phạm vi, có duplicate?)

M — Match (Nhận diện pattern)

Đây có phải bài Two Pointers?
Có liên quan đến subarray/substring? → Sliding Window
Cần fast lookups? → Hash Map

P — Plan (Lên kế hoạch)

Viết pseudocode trước code thực
Xác định data structures cần dùng

I — Implement (Triển khai)

Chuyển pseudocode thành code
Đặt tên biến rõ ràng

R — Review (Kiểm tra)

Trace qua với ví dụ
Kiểm tra edge cases (input rỗng, một phần tử, duplicates)

E — Evaluate (Đánh giá)

Nêu time và space complexity
Có thể tối ưu thêm không?

Ví Dụ: Áp Dụng Framework

Bài toán: Cho sorted array, tìm hai số có tổng bằng target.

Input: [2, 4, 6, 10, 15], target = 14
Output: [1, 3] (indices của 4 và 10)

Understand: Sorted array, tìm cặp có tổng = target
Match: Sorted array + cặp → Two Pointers
Plan: Left pointer ở đầu, right ở cuối, di chuyển dựa trên so sánh tổng
Implement: Viết code
Review: Test với ví dụ, kiểm tra mảng rỗng
Evaluate: O(n) time, O(1) space — tối ưu

2. Two Pointers

Khi nào dùng: Làm việc với sorted arrays, tìm cặp, so sánh phần tử từ hai đầu, hoặc phân vùng data.

Pattern 1: Pair Sum trong Sorted Array

TypeScript:

// Tìm hai số trong sorted array có tổng = target
// Time: O(n), Space: O(1)
function twoSumSorted(nums: number[], target: number): [number, number] {
    let left = 0;
    let right = nums.length - 1;
 
    while (left < right) {
        const sum = nums[left] + nums[right];
 
        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;   // Cần tổng lớn hơn → di chuyển left sang phải
        } else {
            right--;  // Cần tổng nhỏ hơn → di chuyển right sang trái
        }
    }
 
    return [-1, -1];
}
 
console.log(twoSumSorted([2, 4, 6, 10, 15], 14));  // [1, 3]

Python:

# Tìm hai số trong sorted array có tổng = target
# Time: O(n), Space: O(1)
def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int]:
    left, right = 0, len(nums) - 1
 
    while left < right:
        current_sum = nums[left] + nums[right]
 
        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1
        else:
            right -= 1
 
    return (-1, -1)
 
print(two_sum_sorted([2, 4, 6, 10, 15], 14))  # (1, 3)

Pattern 2: Xóa Duplicates In-Place

TypeScript:

// Xóa duplicates từ sorted array in-place
// Time: O(n), Space: O(1)
function removeDuplicates(nums: number[]): number {
    if (nums.length === 0) return 0;
 
    let write = 1;
 
    for (let read = 1; read < nums.length; read++) {
        if (nums[read] !== nums[read - 1]) {
            nums[write] = nums[read];
            write++;
        }
    }
 
    return write;
}
 
const arr = [1, 1, 2, 2, 3, 4, 4, 5];
const newLength = removeDuplicates(arr);
console.log(arr.slice(0, newLength)); // [1, 2, 3, 4, 5]

Pattern 3: Kiểm Tra Palindrome

TypeScript:

// Kiểm tra string có phải palindrome (bỏ qua ký tự đặc biệt)
// Time: O(n), Space: O(1)
function isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;
 
    while (left < right) {
        while (left < right && !isAlphanumeric(s[left])) left++;
        while (left < right && !isAlphanumeric(s[right])) right--;
 
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
 
        left++;
        right--;
    }
 
    return true;
}
 
function isAlphanumeric(char: string): boolean {
    return /[a-zA-Z0-9]/.test(char);
}
 
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true

Nhận Diện Two Pointers

Dấu hiệu	Ví dụ
Sorted array + tìm cặp	Two sum, pair with difference
In-place modification	Remove duplicates, move zeros
Palindrome	Valid palindrome
Merge hai sorted arrays	Merge sorted arrays

3. Sliding Window

Khi nào dùng: Tìm subarray hoặc substring tối ưu với kích thước cụ thể hoặc điều kiện nhất định.

Pattern 1: Maximum Sum của k Phần Tử Liên Tiếp (Fixed Window)

TypeScript:

// Tìm maximum sum của k phần tử liên tiếp
// Time: O(n), Space: O(1)
function maxSumSubarray(nums: number[], k: number): number {
    if (nums.length < k) return -1;
 
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += nums[i];
    }
 
    let maxSum = windowSum;
 
    for (let i = k; i < nums.length; i++) {
        windowSum += nums[i] - nums[i - k]; // Thêm mới, bỏ cũ
        maxSum = Math.max(maxSum, windowSum);
    }
 
    return maxSum;
}
 
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9

Python:

# Tìm maximum sum của k phần tử liên tiếp
# Time: O(n), Space: O(1)
def max_sum_subarray(nums: list[int], k: int) -> int:
    if len(nums) < k:
        return -1
 
    window_sum = sum(nums[:k])
    max_sum = window_sum
 
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
 
    return max_sum
 
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # 9

Pattern 2: Longest Substring Không Ký Tự Lặp (Variable Window)

TypeScript:

// Tìm length của longest substring không có ký tự lặp
// Time: O(n), Space: O(min(n, alphabet_size))
function lengthOfLongestSubstring(s: string): number {
    const charIndex = new Map<string, number>();
    let maxLength = 0;
    let left = 0;
 
    for (let right = 0; right < s.length; right++) {
        const char = s[right];
 
        if (charIndex.has(char) && charIndex.get(char)! >= left) {
            left = charIndex.get(char)! + 1;
        }
 
        charIndex.set(char, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
 
    return maxLength;
}
 
console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
console.log(lengthOfLongestSubstring("pwwkew"));   // 3 ("wke")

Python:

# Tìm length của longest substring không có ký tự lặp
# Time: O(n), Space: O(min(n, alphabet_size))
def length_of_longest_substring(s: str) -> int:
    char_index: dict[str, int] = {}
    max_length = 0
    left = 0
 
    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
 
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
 
    return max_length
 
print(length_of_longest_substring("abcabcbb"))  # 3

Pattern 3: Subarray Nhỏ Nhất Với Tổng ≥ Target

TypeScript:

// Tìm subarray ngắn nhất có tổng >= target
// Time: O(n), Space: O(1)
function minSubArrayLen(target: number, nums: number[]): number {
    let minLength = Infinity;
    let windowSum = 0;
    let left = 0;
 
    for (let right = 0; right < nums.length; right++) {
        windowSum += nums[right];
 
        while (windowSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }
 
    return minLength === Infinity ? 0 : minLength;
}
 
console.log(minSubArrayLen(7, [2, 3, 1, 2, 4, 3])); // 2 ([4, 3])

Nhận Diện Sliding Window

Dấu hiệu	Ví dụ
Contiguous subarray/substring	Max sum subarray
"k phần tử liên tiếp"	Max average k elements
"Longest/shortest với điều kiện"	Longest substring không lặp

4. Hash Maps cho Fast Lookups

Khi nào dùng: Cần O(1) lookups, đếm tần suất, kiểm tra duplicates, hoặc nhóm phần tử.

Pattern 1: Two Sum (Unsorted Array)

TypeScript:

// Two Sum dùng hash map
// Time: O(n), Space: O(n)
function twoSum(nums: number[], target: number): [number, number] {
    const seen = new Map<number, number>();
 
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
 
        if (seen.has(complement)) {
            return [seen.get(complement)!, i];
        }
 
        seen.set(nums[i], i);
    }
 
    return [-1, -1];
}
 
console.log(twoSum([2, 7, 11, 15], 9));  // [0, 1]

Python:

# Two Sum dùng hash map
# Time: O(n), Space: O(n)
def two_sum(nums: list[int], target: int) -> tuple[int, int]:
    seen: dict[int, int] = {}
 
    for i, num in enumerate(nums):
        complement = target - num
 
        if complement in seen:
            return (seen[complement], i)
 
        seen[num] = i
 
    return (-1, -1)
 
print(two_sum([2, 7, 11, 15], 9))  # (0, 1)

Pattern 2: Đếm Tần Suất

TypeScript:

// Kiểm tra hai string có phải anagram
// Time: O(n), Space: O(k)
function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;
 
    const freq = new Map<string, number>();
 
    for (const char of s) {
        freq.set(char, (freq.get(char) || 0) + 1);
    }
 
    for (const char of t) {
        const count = freq.get(char);
        if (!count) return false;
        freq.set(char, count - 1);
    }
 
    return true;
}
 
console.log(isAnagram("anagram", "nagaram")); // true
console.log(isAnagram("rat", "car"));         // false

Python:

from collections import Counter
 
# Kiểm tra anagram
def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return Counter(s) == Counter(t)
 
print(is_anagram("anagram", "nagaram"))  # True

Pattern 3: Group By

TypeScript:

// Nhóm anagrams lại
// Time: O(n * k log k), Space: O(n * k)
function groupAnagrams(strs: string[]): string[][] {
    const groups = new Map<string, string[]>();
 
    for (const str of strs) {
        const key = str.split("").sort().join("");
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key)!.push(str);
    }
 
    return Array.from(groups.values());
}
 
console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
// [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Nhận Diện Hash Map

Dấu hiệu	Ví dụ
"Tìm nếu tồn tại"	Two sum, contains duplicate
Đếm occurrences	Anagram check, majority element
Nhóm phần tử	Group anagrams
O(n²) → O(n)	Thay nested loop bằng lookup

5. Prefix Sum

Khi nào dùng: Tính range sums hiệu quả, đặc biệt khi cần query nhiều ranges.

Pattern 1: Range Sum Query

TypeScript:

// Prefix sum cho range queries hiệu quả
// Preprocessing: O(n), Mỗi query: O(1)
class PrefixSum {
    private prefix: number[];
 
    constructor(nums: number[]) {
        this.prefix = new Array(nums.length + 1).fill(0);
        for (let i = 0; i < nums.length; i++) {
            this.prefix[i + 1] = this.prefix[i] + nums[i];
        }
    }
 
    rangeSum(left: number, right: number): number {
        return this.prefix[right + 1] - this.prefix[left];
    }
}
 
const ps = new PrefixSum([2, 4, 1, 3, 5]);
console.log(ps.rangeSum(1, 3)); // 8 (4 + 1 + 3)
console.log(ps.rangeSum(0, 4)); // 15 (toàn bộ mảng)

Python:

# Prefix sum cho range queries hiệu quả
class PrefixSum:
    def __init__(self, nums: list[int]):
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]
 
    def range_sum(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]
 
ps = PrefixSum([2, 4, 1, 3, 5])
print(ps.range_sum(1, 3))  # 8

Pattern 2: Subarray Sum Equals K

TypeScript:

// Đếm subarrays có tổng = k
// Time: O(n), Space: O(n)
function subarraySum(nums: number[], k: number): number {
    const prefixCount = new Map<number, number>();
    prefixCount.set(0, 1);
    let count = 0;
    let currentSum = 0;
 
    for (const num of nums) {
        currentSum += num;
 
        if (prefixCount.has(currentSum - k)) {
            count += prefixCount.get(currentSum - k)!;
        }
 
        prefixCount.set(currentSum, (prefixCount.get(currentSum) || 0) + 1);
    }
 
    return count;
}
 
console.log(subarraySum([1, 1, 1], 2));     // 2
console.log(subarraySum([1, 2, 3], 3));     // 2

Python:

# Đếm subarrays có tổng = k
# Time: O(n), Space: O(n)
def subarray_sum(nums: list[int], k: int) -> int:
    prefix_count: dict[int, int] = {0: 1}
    count = 0
    current_sum = 0
 
    for num in nums:
        current_sum += num
 
        if current_sum - k in prefix_count:
            count += prefix_count[current_sum - k]
 
        prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1
 
    return count
 
print(subarray_sum([1, 1, 1], 2))  # 2

Key insight: Prefix sum + hash map là sự kết hợp mạnh mẽ. Thay vì kiểm tra O(n²) subarrays, dùng hash map tìm complement trong O(1).

6. Divide and Conquer

Khi nào dùng: Bài toán có thể chia thành subproblems nhỏ hơn cùng loại, giải độc lập, và kết hợp lại.

Cách Hoạt Động

Divide: Chia bài toán thành subproblems nhỏ hơn
Conquer: Giải mỗi subproblem đệ quy
Combine: Gộp các solutions lại

Merge Sort

TypeScript:

// Merge sort - divide and conquer
// Time: O(n log n), Space: O(n)
function mergeSort(arr: number[]): number[] {
    if (arr.length <= 1) return arr;
 
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
 
    return merge(left, right);
}
 
function merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let i = 0, j = 0;
 
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
 
    return result.concat(left.slice(i), right.slice(j));
}
 
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

Python:

# Merge sort - divide and conquer
# Time: O(n log n), Space: O(n)
def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
 
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
 
    return merge(left, right)
 
def merge(left: list[int], right: list[int]) -> list[int]:
    result = []
    i = j = 0
 
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
 
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

7. Greedy Approach

Khi nào dùng: Lựa chọn tối ưu cục bộ tại mỗi bước dẫn đến solution tối ưu toàn cục.

Kadane's Algorithm (Maximum Subarray)

TypeScript:

// Maximum subarray sum dùng Kadane's algorithm
// Time: O(n), Space: O(1)
function maxSubArray(nums: number[]): number {
    let maxSum = nums[0];
    let currentSum = nums[0];
 
    for (let i = 1; i < nums.length; i++) {
        // Greedy: mở rộng subarray hiện tại hoặc bắt đầu mới
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
 
    return maxSum;
}
 
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6

Python:

# Maximum subarray sum dùng Kadane's algorithm
# Time: O(n), Space: O(1)
def max_sub_array(nums: list[int]) -> int:
    max_sum = nums[0]
    current_sum = nums[0]
 
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
 
    return max_sum
 
print(max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6

Activity Selection / Interval Scheduling

TypeScript:

// Số lượng tối đa intervals không chồng lấp
// Time: O(n log n), Space: O(1)
function maxNonOverlapping(intervals: [number, number][]): number {
    if (intervals.length === 0) return 0;
 
    intervals.sort((a, b) => a[1] - b[1]);
 
    let count = 1;
    let lastEnd = intervals[0][1];
 
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= lastEnd) {
            count++;
            lastEnd = intervals[i][1];
        }
    }
 
    return count;
}
 
console.log(maxNonOverlapping([[1, 3], [2, 4], [3, 5], [0, 6], [5, 7]])); // 3

Lưu ý: Greedy không phải lúc nào cũng đúng! Luôn xác minh greedy choice property.

8. Recursion và Backtracking

Khi nào dùng: Khám phá toàn bộ khả năng, constraint satisfaction, tạo combinations/permutations.

Pattern 1: Generate All Subsets

TypeScript:

// Tạo tất cả subsets của mảng
// Time: O(2^n), Space: O(n)
function subsets(nums: number[]): number[][] {
    const result: number[][] = [];
 
    function backtrack(start: number, current: number[]): void {
        result.push([...current]);
 
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);       // Chọn
            backtrack(i + 1, current);   // Khám phá
            current.pop();               // Quay lui
        }
    }
 
    backtrack(0, []);
    return result;
}
 
console.log(subsets([1, 2, 3]));
// [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Python:

# Tạo tất cả subsets
# Time: O(2^n), Space: O(n)
def subsets(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
 
    def backtrack(start: int, current: list[int]) -> None:
        result.append(current[:])
 
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
 
    backtrack(0, [])
    return result
 
print(subsets([1, 2, 3]))

Pattern 2: Generate Permutations

TypeScript:

// Tạo tất cả hoán vị
// Time: O(n!), Space: O(n)
function permutations(nums: number[]): number[][] {
    const result: number[][] = [];
 
    function backtrack(current: number[], remaining: number[]): void {
        if (remaining.length === 0) {
            result.push([...current]);
            return;
        }
 
        for (let i = 0; i < remaining.length; i++) {
            current.push(remaining[i]);
            const nextRemaining = [
                ...remaining.slice(0, i),
                ...remaining.slice(i + 1),
            ];
            backtrack(current, nextRemaining);
            current.pop();
        }
    }
 
    backtrack([], nums);
    return result;
}
 
console.log(permutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Template Backtracking

function backtrack(state, choices):
    if state là complete solution:
        ghi nhận solution
        return
 
    for mỗi choice trong choices:
        if choice hợp lệ:
            thực hiện choice        // Chọn
            backtrack(new_state)    // Khám phá
            hoàn tác choice         // Quay lui

Nhận Diện Backtracking

Dấu hiệu	Ví dụ
"Generate tất cả..."	All subsets, permutations
"Tìm tất cả valid..."	Valid parentheses, N-queens
Combinatorial search	Word search, combination sum

9. Pattern Recognition Cheat Sheet

Theo Loại Bài Toán

Loại bài toán	Pattern	Time Complexity
Tìm cặp trong sorted array	Two Pointers	O(n)
Max/min subarray kích thước k	Sliding Window (fixed)	O(n)
Longest substring có điều kiện	Sliding Window (variable)	O(n)
Tìm phần tử / kiểm tra tồn tại	Hash Map	O(n)
Đếm occurrences	Hash Map (frequency)	O(n)
Range sum queries	Prefix Sum	O(1) per query
Subarray có tổng = target	Prefix Sum + Hash Map	O(n)
Sorting hiệu quả	Divide and Conquer	O(n log n)
Optimization với choices	Greedy	O(n) hoặc O(n log n)
Generate tất cả combinations	Backtracking	O(2ⁿ) hoặc O(n!)

Theo Keywords

Keyword	Nghĩ đến
"Sorted array"	Two Pointers, Binary Search
"Contiguous subarray"	Sliding Window, Prefix Sum
"Substring"	Sliding Window, Hash Map
"Pair" hoặc "two elements"	Two Pointers (sorted), Hash Map (unsorted)
"Frequency" hoặc "count"	Hash Map
"Range sum"	Prefix Sum
"Maximum/minimum"	Greedy, Sliding Window, DP
"All combinations"	Backtracking

10. Bài Tập Thực Hành

Two Pointers

Container With Most Water — Tìm hai đường chứa nhiều nước nhất
3Sum — Tìm tất cả bộ ba có tổng = 0
Sort Colors — Dutch national flag problem

Sliding Window

Maximum Average Subarray — Max average k phần tử liên tiếp
Minimum Window Substring — Window nhỏ nhất chứa tất cả target characters
Longest Repeating Character Replacement — Longest substring với tối đa k replacements

Hash Map

Contains Duplicate — Kiểm tra có giá trị xuất hiện hai lần
First Unique Character — Tìm ký tự không lặp đầu tiên
Intersection of Two Arrays — Tìm phần tử chung

Prefix Sum

Running Sum of 1D Array — Tính running sum
Subarray Sum Equals K — Đếm subarrays có tổng = target

Greedy

Best Time to Buy and Sell Stock — Maximum profit
Jump Game — Có thể đến index cuối?
Merge Intervals — Gộp intervals chồng lấp

Backtracking

Letter Combinations of Phone Number — Tạo tất cả letter combos
Combination Sum — Tìm combinations có tổng = target
Word Search — Tìm word trong 2D grid

Tổng Kết và Key Takeaways

✅ Dùng UMPIRE framework: Understand → Match → Plan → Implement → Review → Evaluate
✅ Two Pointers: Tốt nhất cho sorted arrays, cặp, và in-place modifications — O(n) time, O(1) space
✅ Sliding Window: Tốt nhất cho contiguous subarray/substring — O(n) time
✅ Hash Maps: Tốt nhất cho fast lookups, đếm tần suất, và grouping — O(n) time, O(n) space
✅ Prefix Sum: Tốt nhất cho range queries — O(1) per query sau O(n) preprocessing
✅ Divide and Conquer: Tốt nhất cho bài phân rã thành subproblems độc lập — O(n log n)
✅ Greedy: Tốt nhất khi lựa chọn tối ưu cục bộ dẫn đến tối ưu toàn cục
✅ Backtracking: Tốt nhất cho generate tất cả valid combinations — exponential time
✅ Pattern recognition là kỹ năng: Càng giải nhiều bài, càng nhận diện pattern nhanh
✅ Bắt đầu với brute force: Có working solution trước, rồi tối ưu bằng đúng pattern

Bước Tiếp Theo

Giờ bạn đã biết các pattern giải bài thiết yếu, sẵn sàng áp dụng vào data structures cụ thể:

Tiếp tục DSA series:

Arrays & Strings — The Foundation - Áp dụng patterns vào bài array và string
Linked Lists — Dynamic Sequential Data - Two pointers trong linked lists

Quay lại roadmap:

Data Structures & Algorithms Roadmap - Lộ trình học hoàn chỉnh

Practice Resources:

LeetCode Patterns - Filter theo topic và difficulty
NeetCode 150 - Bài tập curated theo pattern
Grind 75 - Study plan tối ưu thời gian

Thuộc chuỗi bài Data Structures & Algorithms Roadmap

Giới Thiệu

Những Gì Bạn Sẽ Học

Điều Kiện Tiên Quyết

1. Framework Giải Bài

Phương Pháp UMPIRE

Ví Dụ: Áp Dụng Framework

2. Two Pointers

Pattern 1: Pair Sum trong Sorted Array

Pattern 2: Xóa Duplicates In-Place

Pattern 3: Kiểm Tra Palindrome

Nhận Diện Two Pointers

3. Sliding Window

Pattern 1: Maximum Sum của k Phần Tử Liên Tiếp (Fixed Window)

Pattern 2: Longest Substring Không Ký Tự Lặp (Variable Window)

Pattern 3: Subarray Nhỏ Nhất Với Tổng ≥ Target

Nhận Diện Sliding Window

4. Hash Maps cho Fast Lookups

Pattern 1: Two Sum (Unsorted Array)

Pattern 2: Đếm Tần Suất

Pattern 3: Group By

Nhận Diện Hash Map

5. Prefix Sum

Pattern 1: Range Sum Query

Pattern 2: Subarray Sum Equals K

6. Divide and Conquer

Cách Hoạt Động

Merge Sort

7. Greedy Approach

Kadane's Algorithm (Maximum Subarray)

Activity Selection / Interval Scheduling

8. Recursion và Backtracking

Pattern 1: Generate All Subsets

Pattern 2: Generate Permutations

Template Backtracking

Nhận Diện Backtracking

9. Pattern Recognition Cheat Sheet

Theo Loại Bài Toán

Theo Keywords

10. Bài Tập Thực Hành

Two Pointers

Sliding Window

Hash Map

Prefix Sum

Greedy

Backtracking

Tổng Kết và Key Takeaways

Bước Tiếp Theo

📬 Đăng ký nhận bản tin

💬 Comments