Chương 26 - Two Pointers (Fast & Slow Pointer)

Two pointers là vũ khí cơ bản đã xuất hiện ở Array (1.4, 1.5), String (2.2), Linked List (7.3-7.6). Chương này hệ thống hoá thành 3 mẫu: (i) 2 đầu (đối nghịch), (ii) slow & fast (1×/2×), (iii) same direction (sliding window). Mỗi mẫu giải được một họ bài.

Mục tiêu chương

Sau chương này, bạn sẽ:

3 mẫu: 2-đầu (sorted), slow-fast (LL), same-direction (sliding window).
Duplicate handling checklist: skip ở mọi index quan tâm.
Pattern proof: cố định 1 đầu, dịch đầu kia chỉ khi monotonic.
Trapping Rain Water: 2 cách (prefix/suffix max vs two pointers).

Khi nào dùng pattern này?

Mảng / chuỗi đã sort, cần tìm cặp / bộ 3 / bộ k.
Cần O(1) extra space khi xử lý.
Bài có “đuổi nhau” - hai biến trên cùng struct di chuyển theo quy tắc.

3 mẫu hay nhất:

Mẫu	Ví dụ bài	Đặc điểm
2 đầu	3Sum, Container Most Water, Trapping	sort trước, hội tụ từ 2 phía
Slow & Fast	Cycle, Middle of LL, Move Zeroes	tốc độ khác nhau
Same direction	Sliding window, Remove Dup	window mở rộng / thu hẹp

Template code

# 1) 2 đầu (sorted)
l, r = 0, len(arr) - 1
while l < r:
    if check(arr[l], arr[r]):
        # ... dùng cặp ...
        l += 1
        r -= 1
    elif arr[l] + arr[r] < target:
        l += 1
    else:
        r -= 1


# 2) Slow & Fast (in-place)
slow = 0
for fast in range(len(arr)):
    if condition(arr[fast]):
        arr[slow] = arr[fast]
        slow += 1

Bài tự luyện cuối chương

LC 26 - Remove Duplicates from Sorted Array
LC 27 - Remove Element
LC 88 - Merge Sorted Array (in-place từ cuối)
LC 287 - Find the Duplicate Number (Floyd)
LC 905 - Sort Array By Parity

26.1 3Sum (LC 15)

Đề bài

Cho nums. Tìm tất cả triplet [a, b, c] với a + b + c == 0, không trùng lặp.

Ví dụ

Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

Ràng buộc

3 <= len(nums) <= 3000
-10^5 <= nums[i] <= 10^5

Clarifying questions

Mảng có thể có nhiều 0? → Có; cần skip duplicate.
Output thứ tự? → Không quan trọng nhưng mỗi triplet sort tăng dần.

Hướng tiếp cận

Brute force O(n³). Mọi triplet.

Sort + two pointers O(n²).

Sort. Với mỗi i, dùng two pointers l, r tìm cặp tổng -nums[i] trong nums[i+1..n-1].

Xử lý duplicate: skip ký tự trùng tại cả i, l, r.

Hình minh hoạ với nums = [-1, 0, 1, 2, -1, -4] sort → [-4, -1, -1, 0, 1, 2]:

i=0 (-4): target=4. l=1 (-1), r=5 (2). -1+2=1 < 4. l++. ... không tìm được.
i=1 (-1): target=1. l=2 (-1), r=5 (2). -1+2=1 ✓ → add [-1,-1,2].
                    l++, r--. l=3 (0), r=4 (1). 0+1=1 ✓ → add [-1,0,1].
i=2 (-1): skip (trùng nums[1]).
i=3 (0): target=0. l=4 (1), r=5 (2). 1+2=3 > 0. r--. → l=r → dừng.

Code Python 3

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result: list[list[int]] = []
        n = len(nums)
        for i in range(n - 2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            l, r = i + 1, n - 1
            target = -nums[i]
            while l < r:
                s = nums[l] + nums[r]
                if s == target:
                    result.append([nums[i], nums[l], nums[r]])
                    l += 1; r -= 1
                    while l < r and nums[l] == nums[l - 1]: l += 1
                    while l < r and nums[r] == nums[r + 1]: r -= 1
                elif s < target:
                    l += 1
                else:
                    r -= 1
        return result

Phân tích độ phức tạp

Thời gian: O(n²). Bộ nhớ: O(1) (không tính output).

Bình luận

Early exit nums[i] > 0: vì sort tăng, nums[i] > 0 → nums[i+1], nums[r] > 0 → tổng > 0.

Bài tự luyện liên quan

LC 16 - 3Sum Closest.
LC 18 - 4Sum.

26.2 Trapping Rain Water (LC 42)

Đề bài

Cho mảng height[]. Mỗi cột rộng 1. Tính lượng nước đọng giữa các cột.

Ví dụ

Input:  height = [0,1,0,2,1,0,1,3,2,1,2,1]
        (mỗi phần tử là chiều cao 1 cột rộng 1 đơn vị)
Output: 6   (tổng lượng nước đọng giữa các cột)

Ràng buộc

1 <= len(height) <= 2·10^4
0 <= height[i] <= 10^5

Clarifying questions

All 0? → Không có nước, trả 0.
Đơn điệu tăng/giảm? → Không trap được nước → 0.

Hướng tiếp cận

Cách 1 - Prefix max + Suffix max, O(n) time, O(n) space.

Mỗi ô i chứa được: min(max_left[i], max_right[i]) - height[i].

Cách 2 - Two pointers, O(n) time, O(1) space.

l = 0, r = n - 1, giữ lmax, rmax. Dịch con trỏ ở phía cột thấp hơn - chính bên đó quyết định nước đọng tại ô đang xét.

Code Python 3

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        lmax = rmax = 0
        water = 0
        while l < r:
            if height[l] < height[r]:
                if height[l] >= lmax:
                    lmax = height[l]
                else:
                    water += lmax - height[l]
                l += 1
            else:
                if height[r] >= rmax:
                    rmax = height[r]
                else:
                    water += rmax - height[r]
                r -= 1
        return water

Phân tích độ phức tạp

Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

Tại sao two pointers work? Bên thấp hơn quyết định: nếu height[l] < height[r], thì tại ô l, “bao quanh phải” có ít nhất là height[r] > height[l] → đủ để xác định nước = lmax - height[l].
Pattern này cùng tinh thần với Container Most Water (1.5).

Bài tự luyện liên quan

LC 407 - Trapping Rain Water II (Chương 37).
LC 84 - Largest Rectangle in Histogram.

26.3 Container With Most Water (LC 11) - recap

Đã giải đầy đủ ở Chương 1.5. Đây là two pointers pattern cốt lõi.

Liên hệ với chương này

Cùng pattern dịch con trỏ thấp hơn - minh hoạ “2-đầu hội tụ”.
Khác với LC 42 (bài 26.2) ở chỗ: container chỉ xét 2 cột biên, không tính cột giữa.

Code Python 3 (recap)

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        best = 0
        while l < r:
            h = min(height[l], height[r])
            best = max(best, h * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return best

Phân tích độ phức tạp

Thời gian: O(n). Bộ nhớ: O(1).

Bài tự luyện liên quan

LC 42 - Trapping Rain Water (bài 26.2).

26.4 Sort Colors (LC 75) - recap

Đã giải đầy đủ ở Chương 4.1. Three pointers (Dutch flag).

Liên hệ với chương này

Mở rộng của two pointers - thêm 1 con trỏ cho 3 vùng (0/1/2).
Pattern này tái xuất ở Wiggle Sort, partition của quicksort.

Code Python 3 (recap)

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        lo, mid, hi = 0, 0, len(nums) - 1
        while mid <= hi:
            if nums[mid] == 0:
                nums[lo], nums[mid] = nums[mid], nums[lo]
                lo += 1; mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[hi] = nums[hi], nums[mid]
                hi -= 1

Phân tích độ phức tạp

Thời gian: O(n). Bộ nhớ: O(1).

Bài tự luyện liên quan

LC 324 - Wiggle Sort II.

26.5 Remove Duplicates from Sorted Array II (LC 80)

Đề bài

Cho mảng nums đã sort. Xoá duplicate sao cho mỗi phần tử xuất hiện tối đa 2 lần, trả về độ dài mới. In-place.

Ví dụ

Input:  nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]

Ràng buộc

1 <= len(nums) <= 3·10^4
-10^4 <= nums[i] <= 10^4
nums sorted

Clarifying questions

Mảng < 2 phần tử? → Trả len.

Hướng tiếp cận

Two pointers slow & fast. Vì sort, chỉ cần check nums[fast] != nums[slow - 2].

Code Python 3

from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0
        for x in nums:
            if slow < 2 or x != nums[slow - 2]:
                nums[slow] = x
                slow += 1
        return slow

Phân tích độ phức tạp

Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

Trick x != nums[slow - 2] đẹp - nếu phần tử thứ 3 trùng, nó sẽ “thấy” bản thân ở slow - 2.

Bài tự luyện liên quan

LC 26 - Remove Duplicates from Sorted Array (allow 1 only).
LC 27 - Remove Element.

26.6 4Sum (LC 18)

Đề bài

Cho nums và target. Tìm tất cả quadruplet [a, b, c, d] với tổng target, không trùng.

Ví dụ

Input:  nums=[1,0,-1,0,-2,2], target=0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Ràng buộc

1 <= len(nums) <= 200
-10^9 <= nums[i], target <= 10^9

Clarifying questions

Có duplicate? → Có; cần skip duplicate ở cả i, j, l, r.

Hướng tiếp cận

Generalization của 3Sum. Sort + 2 vòng lặp ngoài (i, j) + two pointers cho (l, r). O(n³).

Skip duplicate ở cả 4 vị trí i, j, l, r.

Code Python 3

from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        result: list[list[int]] = []
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                l, r = j + 1, n - 1
                tgt = target - nums[i] - nums[j]
                while l < r:
                    s = nums[l] + nums[r]
                    if s == tgt:
                        result.append([nums[i], nums[j], nums[l], nums[r]])
                        l += 1; r -= 1
                        while l < r and nums[l] == nums[l - 1]: l += 1
                        while l < r and nums[r] == nums[r + 1]: r -= 1
                    elif s < tgt:
                        l += 1
                    else:
                        r -= 1
        return result

Phân tích độ phức tạp

Thời gian: O(n³). Bộ nhớ: O(1).

Bình luận

Generalize k-Sum: k vòng đệ quy, base case k=2 là two pointers.
Pruning: thêm early exit khi nums[i]*4 > target (nếu target lớn).

Bài tự luyện liên quan

LC 15 - 3Sum (bài 26.1).
LC 454 - 4Sum II (dùng hash).

Tóm tắt chương & Quyết định

Two-pointer family - chọn shape nào?

Shape	Khi dùng	Bài tiêu biểu
Two-end (`l`=0, `r`=n-1, đi vào giữa)	Sorted, palindrome, container	LC 11, 15, 167, 125
Same-direction (`l`, `r` đều đi tiến)	Subarray với invariant (sliding window là dạng đặc biệt)	LC 26, 283; Chương 27
Slow-fast (`slow` 1 bước, `fast` 2 bước)	Cycle detect, middle node	LC 141, 142, 876

3Sum / 4Sum - duplicate skip checklist

nums.sort()
for i in range(n):
    if i > 0 and nums[i] == nums[i-1]: continue          # skip anchor dup
    l, r = i+1, n-1
    while l < r:
        s = nums[i] + nums[l] + nums[r]
        if s == 0:
            ans.append([nums[i], nums[l], nums[r]])
            l += 1; r -= 1
            while l < r and nums[l] == nums[l-1]: l += 1  # skip inner left dup
            while l < r and nums[r] == nums[r+1]: r -= 1  # skip inner right dup
        elif s < 0: l += 1
        else: r -= 1

4 chỗ skip - quên chỗ nào cũng sinh duplicate.

Trapping Rain Water (LC 42) - 2 approaches

	Prefix/suffix max array	Two pointers
Time	O(n)	O(n)
Space	O(n)	O(1)
Code dài	Trung bình	Ngắn hơn
Hiểu	Trực quan: nước tại i = `min(L[i], R[i]) - h[i]`	Cần argue tại sao “thanh thấp hơn quyết định”

Recommend: nói trước prefix/suffix (dễ giải thích), rồi tối ưu two-pointer nếu interviewer hỏi space.

Recap Container / Sort Colors lens

Container (LC 11): là two-pointer vì việc luôn dịch con trỏ ở phía thanh thấp hơn là một quyết định tham lam có thể chứng minh được rằng nó không bỏ sót đáp án tối ưu.
Sort Colors (LC 75): three-way partition - biến thể two-pointer khi miền giá trị rời rạc nhỏ (3 giá trị).