1.1 Two Pointers là gì?

Tại sao mạnh?

Nhiều bài có lời giải brute force tự nhiên là duyệt cặp (i, j) → O(n²). Two Pointers khai thác một bất biến (invariant) nào đó của bài để loại trừ phần lớn cặp không cần xét, đưa về O(n).

Hai biến thể

1. Opposite Ends — hai pointer khởi đầu ở hai đầu, di chuyển vào giữa.
2. Same Direction (Fast & Slow) — hai pointer cùng đi từ trái, một nhanh một chậm.

1.2 Tín hiệu nhận biết Two Pointers

Khi đọc đề, các "mùi" sau gợi ý nên thử Two Pointers:

1.3 Hai biến thể — trực quan

Trong cả hai biến thể, mỗi pointer chỉ đi một chiều và mỗi vị trí được thăm hữu hạn lần — đó là lý do tổng thời gian là O(n).

1.4 Worked Example 1 — Reverse String

Đề (LeetCode #344): Đảo ngược mảng ký tự s tại chỗ. Yêu cầu O(1) bộ nhớ phụ.

Brute force

Tạo mảng mới, copy ngược → O(n) time, O(n) space → vi phạm yêu cầu O(1).

Two Pointers (Opposite Ends)

def reverseString(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]   # swap
        left += 1
        right -= 1

Trace với s = ['h','e','l','l','o']

Time O(n) (n/2 swap), Space O(1).

1.5 Worked Example 2 — Two Sum II (Sorted)

Đề (LeetCode #167): Mảng numbers đã sort tăng dần. Tìm hai chỉ số (1-indexed) sao cho tổng = target. Yêu cầu O(1) bộ nhớ phụ.

Tại sao Tuần 1 (#1 Two Sum) phải dùng hash, mà bài này dùng Two Pointers?

Ở #1 mảng chưa sort, không khai thác được thứ tự. Bài này có tính sắp xếp — bất biến mạnh để giảm bộ nhớ.

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]
        elif s < target:
            left += 1                  # cần tổng lớn hơn → dịch trái sang phải
        else:
            right -= 1                 # cần tổng nhỏ hơn → dịch phải sang trái
    return []

Time O(n), Space O(1).

1.6 Two Sum II — Tại sao greedy này đúng?

Sinh viên thường viết được code nhưng không giải thích được. Đây là chứng minh tính đúng đắn:

Chứng minh

Giả sử nums[left] + nums[right] < target. Ta tuyên bố: nums[left] không thể là phần tử của đáp án.

Vì sao? Mọi phần tử ở giữa hai pointer đều ≤ nums[right] (mảng sort). Nên nums[left] + nums[k] ≤ nums[left] + nums[right] < target với mọi k ∈ [left+1, right]. Tức không có k nào ghép với left ra target. Vậy loại bỏ left an toàn — di chuyển left += 1.

Lập luận đối xứng cho trường hợp tổng > target.

1.7 Worked Example 3 — Valid Palindrome

Đề (LeetCode #125): Cho string s, trả về True nếu nó là palindrome (sau khi bỏ ký tự không alphanumeric và đưa về chữ thường).

Ví dụ: "A man, a plan, a canal: Panama" → True (do "amanaplanacanalpanama").

Two Pointers với skip

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        # bỏ qua ký tự không alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

Time O(n) (mỗi ký tự được thăm tối đa 1 lần), Space O(1).

1.8 Worked Example 4 — Container With Most Water

Đề (LeetCode #11): Mảng height[i] = chiều cao cột i. Chọn 2 cột tạo bình chứa nước. Diện tích = min(height[i], height[j]) × (j - i). Tìm diện tích lớn nhất.

Constraints: 2 ≤ n ≤ 10⁵ → cần O(n).

Brute force O(n²)

Duyệt mọi cặp (i, j), tính diện tích, lấy max. Với n = 10⁵ → 10¹⁰ → TLE.

Two Pointers Greedy

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h = min(height[left], height[right])
        best = max(best, h * (right - left))
        # luôn dịch pointer của cột THẤP HƠN
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

1.9 Container — Tại sao luôn dịch cột thấp hơn?

Đây là điểm quan trọng nhất của bài. Sinh viên phải hiểu, không chỉ nhớ.

Lập luận

Giả sử height[left] < height[right]. Diện tích hiện tại bị giới hạn bởi height[left].

Câu hỏi: Có lợi không nếu giữ left và dịch right sang trái?

• Chiều rộng (right − left) giảm.
• Chiều cao bị giới hạn vẫn là min(height[left], height[right']) ≤ height[left].
• Vậy diện tích mới ≤ diện tích cũ. Không thể tốt hơn.

→ Mọi cặp dùng left đều cho diện tích ≤ hiện tại. Loại bỏ left an toàn.

1.10 Biến thể 2 — Same Direction (Fast & Slow)

Hai pointer cùng đi từ trái. Pointer fast duyệt mảng nhanh, đọc dữ liệu. Pointer slow ghi dữ liệu hợp lệ vào.

slow = 0
for fast in range(len(nums)):
    if <điều kiện giữ>:
        nums[slow] = nums[fast]
        slow += 1
return slow   # số phần tử đã giữ

Pattern này hữu dụng cho:

• Loại bỏ duplicate tại chỗ.
• Phân vùng (partition) mảng theo điều kiện.
• Lọc phần tử thoả tiêu chí.

Khoá học sẽ gặp lại pattern này ở Tuần 5 (Linked List — fast/slow tìm middle, detect cycle).

1.11 Worked Example 5 — Remove Duplicates from Sorted Array

Đề (LeetCode #26): Mảng nums đã sort. Loại duplicate tại chỗ, trả về số phần tử duy nhất k. Phần tử k đầu tiên của nums phải chứa các giá trị duy nhất.

def removeDuplicates(nums):
    if not nums: return 0
    slow = 1
    for fast in range(1, len(nums)):
        if nums[fast] != nums[fast - 1]:    # phần tử khác phần trước
            nums[slow] = nums[fast]
            slow += 1
    return slow

Trace với nums = [1,1,2,2,3]

Trả về k = 3. Time O(n), Space O(1).

1.12 Worked Example 6 — Move Zeroes

Đề (LeetCode #283): Cho mảng nums. Đẩy mọi số 0 về cuối, giữ nguyên thứ tự tương đối của các số khác 0. Tại chỗ.

def moveZeroes(nums):
    slow = 0
    # Pha 1: dồn các số khác 0 về đầu
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

Trace với nums = [0, 1, 0, 3, 12]

Time O(n), Space O(1). Số swap tối đa là số phần tử khác 0.

1.13 Worked Example 7 — 3Sum (Sort + Two Pointers)

Đề (LeetCode #15): Mảng nums. Tìm tất cả bộ ba phân biệt (a, b, c) sao cho a + b + c = 0. Không trùng bộ.

Ý tưởng kết hợp pattern

Sort mảng → cố định nums[i] là phần tử thứ nhất → tìm cặp (j, k) trong phần còn lại sao cho nums[j] + nums[k] = -nums[i] bằng Two Pointers (vì phần còn lại đã sort).

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:    # bỏ trùng nums[i]
            continue
        left, right = i + 1, len(nums) - 1
        target = -nums[i]
        while left < right:
            s = nums[left] + nums[right]
            if s == target:
                res.append([nums[i], nums[left], nums[right]])
                left += 1; right -= 1
                while left < right and nums[left] == nums[left-1]: left += 1   # bỏ trùng
                while left < right and nums[right] == nums[right+1]: right -= 1
            elif s < target: left += 1
            else: right -= 1
    return res

1.14 3Sum — Phân tích complexity và bẫy

Time complexity

• Sort: O(n log n).
• Vòng lặp ngoài: O(n).
• Two pointers bên trong: O(n) cho mỗi i.
• Tổng: O(n log n) + O(n²) = O(n²).

Bẫy 1: Bỏ trùng sai

Phải skip duplicate cả ba pointer (i, left, right). Nếu chỉ skip i, sẽ có bộ ba lặp lại do left và right trùng giá trị qua các vòng.

Bẫy 2: Khoảng vòng lặp ngoài

range(len(nums) - 2) chứ không phải range(len(nums)). Vì cần ít nhất 2 phần tử cho left và right.

Knowledge Check — Two Pointers

2.1 Vấn đề mở đầu — Range Sum Query

Bài toán: Cho mảng nums. Trả lời nhiều truy vấn dạng "tổng các phần tử từ index i đến j là bao nhiêu?"

Cách ngây thơ

# Mỗi truy vấn O(j - i + 1)
def rangeSum(nums, i, j):
    return sum(nums[i:j+1])

Với q truy vấn và mảng size n, tổng thời gian là O(q × n). Nếu q và n đều ~10⁵ → 10¹⁰ thao tác → TLE.

2.2 Định nghĩa Prefix Sum

Tính chất chính

Ví dụ minh hoạ

nums = [3, 1, 4, 1, 5, 9, 2, 6]
P    = [0, 3, 4, 8, 9, 14, 23, 25, 31]

# Tổng nums[2..5] (= 4 + 1 + 5 + 9 = 19)
P[6] - P[2] = 23 - 4 = 19   ✓

Tiền xử lý: O(n). Mỗi truy vấn: O(1). Bộ nhớ phụ: O(n).

2.3 Cài đặt Prefix Sum

Phiên bản tiêu chuẩn (P có thêm vị trí 0)

def build_prefix(nums):
    n = len(nums)
    P = [0] * (n + 1)
    for i in range(n):
        P[i+1] = P[i] + nums[i]
    return P

def range_sum(P, i, j):
    return P[j+1] - P[i]    # tổng nums[i..j]

Phiên bản gọn (Pythonic)

from itertools import accumulate
P = [0] + list(accumulate(nums))

2.4 Worked Example 1 — Range Sum Query Immutable

Đề (LeetCode #303): Cài class NumArray với:

• NumArray(nums) — khởi tạo
• sumRange(i, j) — trả về tổng nums[i..j]

Sẽ có nhiều cuộc gọi sumRange → tiền xử lý quan trọng.

class NumArray:
    def __init__(self, nums):
        self.P = [0]
        for x in nums:
            self.P.append(self.P[-1] + x)

    def sumRange(self, i, j):
        return self.P[j+1] - self.P[i]

Constructor O(n); sumRange O(1); Space O(n).

2.5 Worked Example 2 — Find Pivot Index

Đề (LeetCode #724): Tìm index i sao cho tổng bên trái = tổng bên phải. Trả về index nhỏ nhất; -1 nếu không có.

Quan sát

Tại mỗi i: left_sum = P[i], right_sum = P[n] - P[i+1]. Tìm i sao cho hai vế bằng nhau.

def pivotIndex(nums):
    total = sum(nums)
    left = 0
    for i, x in enumerate(nums):
        # right = total - left - x
        if left == total - left - x:
            return i
        left += x
    return -1

Time O(n), Space O(1) (không cần lưu cả mảng prefix — chỉ cần biến tổng chạy).

2.6 Combo Pattern — Prefix Sum + HashMap

Pattern mạnh nhất xuất hiện trong tuần này. Khi cần đếm/tìm subarray có tổng bằng K:

Đây chính là pattern "đổi space lấy time" đã gặp ở Tuần 1, kết hợp với prefix sum. Cộng hai pattern → O(n²) → O(n).

2.7 Worked Example 3 — Subarray Sum Equals K

Đề (LeetCode #560): Mảng nums (có thể âm), số nguyên k. Đếm số subarray liên tiếp có tổng bằng k.

from collections import defaultdict

def subarraySum(nums, k):
    count = 0
    prefix = 0
    seen = defaultdict(int)
    seen[0] = 1                  # prefix rỗng = 0, gặp 1 lần (quan trọng!)
    for x in nums:
        prefix += x
        # cần i sao cho P[i] = prefix - k
        count += seen[prefix - k]
        seen[prefix] += 1
    return count

Time O(n), Space O(n).

2.8 Subarray Sum K — Trace tay

nums = [1, 2, 3], k = 3. Kỳ vọng: 2 subarray ([1,2] và [3]).

Kết quả: 2.

2.9 Worked Example 4 — Continuous Subarray Sum (Modular Prefix)

Đề (LeetCode #523): Trả True nếu có subarray độ dài ≥ 2 có tổng chia hết cho k.

Mẹo modular

Subarray nums[i..j] chia hết k \(\iff\) P[j+1] ≡ P[i] (mod k). Vậy lưu prefix sum theo modulo k trong hash map.

def checkSubarraySum(nums, k):
    seen = {0: -1}            # remainder → index sớm nhất
    prefix = 0
    for i, x in enumerate(nums):
        prefix = (prefix + x) % k
        if prefix in seen:
            if i - seen[prefix] >= 2:    # đủ độ dài
                return True
        else:
            seen[prefix] = i
    return False

Time O(n), Space O(min(n, k)).

2.10 Biến thể nâng cao — 2D Prefix Sum

Mở rộng cho ma trận. Truy vấn: tổng các phần tử trong submatrix (r1,c1) → (r2,c2).

# P[i+1][j+1] = tổng matrix[0..i][0..j]
def build2D(M):
    m, n = len(M), len(M[0])
    P = [[0] * (n+1) for _ in range(m+1)]
    for i in range(m):
        for j in range(n):
            P[i+1][j+1] = M[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]
    return P

def query(P, r1, c1, r2, c2):
    return (P[r2+1][c2+1] - P[r1][c2+1]
            - P[r2+1][c1] + P[r1][c1])

Inclusion-Exclusion (Bao hàm-Loại trừ)

Công thức query áp dụng nguyên lý bao hàm-loại trừ trên 2D — trừ hai hàng/cột thừa, cộng lại phần bị trừ 2 lần. Đây là kỹ thuật xuất hiện ở LeetCode #304.

Phần này là tham khảo — chưa yêu cầu thuộc cho bài về nhà tuần này.

Knowledge Check — Prefix Sum

3.1 Decision Tree — Mảng/String

Bảng này nên được sinh viên thuộc lòng đến hết khoá. Khi đề mới, đọc constraint + tín hiệu rồi tra bảng — đây là kỹ năng "pattern matching" thực sự.

3.2 Worked Example 8 — Product of Array Except Self

Đề (LeetCode #238): Mảng nums. Trả về mảng res sao cho res[i] = tích mọi phần tử trừ nums[i]. Không được dùng phép chia. Yêu cầu O(n) và O(1) bộ nhớ phụ (không tính output).

Ý tưởng — Prefix product + Suffix product

Pattern này là biến thể của prefix sum: thay tổng bằng tích, và cần cả prefix lẫn suffix.

def productExceptSelf(nums):
    n = len(nums)
    res = [1] * n
    # Pha 1: res[i] = tích các phần tử bên trái i
    left = 1
    for i in range(n):
        res[i] = left
        left *= nums[i]
    # Pha 2: nhân thêm tích các phần tử bên phải i
    right = 1
    for i in range(n - 1, -1, -1):
        res[i] *= right
        right *= nums[i]
    return res

Time O(n), Space O(1) (output không tính).

3.3 Worked Example 9 — Trapping Rain Water (preview Tuần 6)

Đề (LeetCode #42): Mảng height mô phỏng địa hình. Tính lượng nước giữ lại sau mưa.

Approach 1 — Prefix max + Suffix max (O(n) time, O(n) space)

Tại vị trí i, nước giữ = min(maxLeft[i], maxRight[i]) - height[i].

def trap(height):
    n = len(height)
    if n < 3: return 0
    L = [0]*n; R = [0]*n
    L[0] = height[0]
    for i in range(1, n): L[i] = max(L[i-1], height[i])
    R[-1] = height[-1]
    for i in range(n-2, -1, -1): R[i] = max(R[i+1], height[i])
    return sum(min(L[i], R[i]) - height[i] for i in range(n))

Approach 2 — Two Pointers (O(1) space) — Tuần 6 sẽ làm chi tiết

Dùng cùng tinh thần "luôn dịch pointer của cột thấp hơn" như Container With Most Water.

Tổng kết Tuần 2

Đã học

• Two Pointers — Opposite Ends và Same Direction; chứng minh tính đúng đắn qua bất biến.
• Prefix Sum — Build O(n), query O(1); padding với P[0]=0; modulo prefix.
• Combo Pattern — Prefix Sum + HashMap để đếm subarray theo điều kiện.
• Biến thể — Prefix product (Product Except Self), Prefix max (Trapping Rain Water).
• Decision tree để chọn pattern dựa trên tín hiệu của đề.

Bài về nhà (10 bài)

1. LeetCode #344 — Reverse String (đã chữa, code lại không nhìn)
2. LeetCode #167 — Two Sum II — Input Array Is Sorted
3. LeetCode #125 — Valid Palindrome
4. LeetCode #11 — Container With Most Water
5. LeetCode #15 — 3Sum
6. LeetCode #26 — Remove Duplicates from Sorted Array
7. LeetCode #303 — Range Sum Query Immutable
8. LeetCode #560 — Subarray Sum Equals K
9. LeetCode #238 — Product of Array Except Self
10. LeetCode #42 — Trapping Rain Water (chỉ cần approach prefix max — O(n) space)

Mỗi bài: solution.py + 3 test tự nghĩ + analysis.md nêu pattern dùng và bất biến (nếu Two Pointers) hoặc công thức prefix.