Chương 17 - Divide and Conquer

Divide and Conquer (D&C): chia bài thành các bài con độc lập, giải đệ quy, rồi kết hợp. Khác với DP (bài con có thể overlap), D&C bài con không trùng nhau. Các thuật toán nổi tiếng (merge sort, quicksort, fast power, closest pair) đều là D&C.

Mục tiêu chương

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

• Nhận diện D&C: chia bài thành các bài con độc lập (khác DP).
• Master theorem cheat: 2T(n/2)+O(n) = O(n log n).
• Đếm bằng merge sort: inversions, smaller-after-self.
• Pattern “crossing subarray” cho Maximum Subarray.

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

• Bài có thể chia mảng / khoảng / cây làm 2-3 phần độc lập.
• Cần giảm O(n²) → O(n log n) thông qua kết hợp 2 nửa O(n).
• Master theorem áp được: T(n) = aT(n/b) + f(n).

Master theorem cheat: - a = b, f(n) = O(n) → T(n) = O(n log n) (merge sort).

• a = 1, b = 2, f(n) = O(1) → T(n) = O(log n) (binary search). - a = 2, b = 2, f(n) = O(n) → T(n) = O(n log n).

Template code

def divide_conquer(arr, lo: int, hi: int):
    if lo >= hi:                    # base case
        return base_value(arr[lo])
    mid = (lo + hi) // 2
    left = divide_conquer(arr, lo, mid)
    right = divide_conquer(arr, mid + 1, hi)
    return combine(left, right)     # phần "conquer" - thường O(n)

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

• LC 169 - Majority Element (Boyer–Moore hoặc D&C)
• LC 218 - The Skyline Problem (D&C trên interval)
• LC 932 - Beautiful Array
• LC 1649 - Create Sorted Array through Instructions

---

17.1 Maximum Subarray - D&C version (LC 53)

Đề bài

Cho nums, tìm dãy con liên tục có tổng max. Trả về tổng.

Ví dụ

Input:  nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6 (dãy [4,-1,2,1])

Ràng buộc

• 1 <= len(nums) <= 10^5
• -10^4 <= nums[i] <= 10^4

Clarifying questions

• All negative? → Trả số âm lớn nhất.
• Single element? → Trả chính nó.

Hướng tiếp cận

3 cách: 1. Kadane’s (DP 1D, O(n)) - chuẩn cho LC 53. 2. Prefix sum + min, O(n). 3. Divide & Conquer, O(n log n) - focus của chương này.

D&C insight: chia mảng [lo, hi] làm 2 nửa [lo, mid], [mid+1, hi]. Max subarray hoặc: - Hoàn toàn trong nửa trái (đệ quy). - Hoàn toàn trong nửa phải (đệ quy). - Qua giữa - bắt đầu trong trái, kết thúc trong phải.

Crossing sum tính O(n): - left_max = max của nums[mid] + nums[mid-1] + ... cộng dồn về trái. - right_max = tương tự về phải. - crossing = left_max + right_max.

Max của 3 lựa chọn = đáp án bài con.

Code Python 3

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        def dc(lo: int, hi: int) -> int:
            if lo == hi:
                return nums[lo]
            mid = (lo + hi) // 2

            left = dc(lo, mid)
            right = dc(mid + 1, hi)

            # Crossing - bắt buộc bao gồm cả nums[mid] và nums[mid+1].
            left_max = -float('inf')
            cur = 0
            for i in range(mid, lo - 1, -1):
                cur += nums[i]
                left_max = max(left_max, cur)
            right_max = -float('inf')
            cur = 0
            for i in range(mid + 1, hi + 1):
                cur += nums[i]
                right_max = max(right_max, cur)
            crossing = left_max + right_max

            return max(left, right, crossing)

        return dc(0, len(nums) - 1)

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

• Thời gian: T(n) = 2T(n/2) + O(n) = O(n log n).
• Bộ nhớ: O(log n) stack.

Bình luận

• Kadane’s O(n) dễ hơn và nhanh hơn. D&C đáng học vì:
  • Chứng minh nguyên lý “tách + kết hợp” rất sáng tỏ.
  • Mở rộng được sang Segment Tree (Chương 22) - segment tree dùng đúng pattern này: mỗi node lưu (left_max, right_max, total, best) đủ để merge 2 con.

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

• LC 53 - Maximum Subarray (Kadane’s).
• LC 152 - Maximum Product Subarray.
• LC 918 - Maximum Sum Circular Subarray.

---

17.2 Merge Sort & Count Inversions (bài kinh điển)

Đề bài

Tính số inversion trong mảng nums: cặp (i, j) với i < j và nums[i] > nums[j].

Ví dụ

Input:  nums = [2, 4, 1, 3, 5]
Output: 3
(số cặp i < j với nums[i] > nums[j]; cụ thể: (2,1), (4,1), (4,3))

Ràng buộc

• 1 <= len(nums) <= 5·10^4
• -10^9 <= nums[i] <= 10^9

Clarifying questions

• Array có thể có duplicate? → Có; duplicate không tạo inversion.

Hướng tiếp cận

Brute force - O(n²). Đếm mọi cặp.

D&C bằng Merge Sort - O(n log n).

Trong khi merge 2 nửa đã sort: - Khi lấy từ nửa phải (vì nums_right[j] < nums_left[i]), mọi phần tử còn lại trong nửa trái đều tạo inversion với nums_right[j]. → cộng (len_left - i) vào counter.

Hình minh hoạ với [2, 4, 1, 3, 5]:

Chia:    [2, 4, 1]  |  [3, 5]
Đệ quy   [2, 4]  [1]    [3]  [5]
trái:    [2] [4]
         merge [2,4]: 0 inversion
       merge [2,4] với [1]:
         lấy 1 từ phải → còn 2 phần tử [2,4] trong trái lớn hơn → +2 inversion
         kết quả: [1, 2, 4]; total = 2

phải:    merge [3] [5]: 0 inversion → [3, 5]

merge [1, 2, 4] với [3, 5]:
  1 (trái), 2 (trái), 4 (trái), 3 (phải) - khi lấy 3, 4 vẫn ở trái còn lớn → +1
  4, 5 → 5 từ phải, không còn trái → 0 inv

Tổng: 2 + 1 = 3  ✓

Code Python 3

from typing import List

class Solution:
    def countInversions(self, nums: List[int]) -> int:

        def merge_sort(arr: List[int]) -> tuple[List[int], int]:
            if len(arr) <= 1:
                return arr, 0
            mid = len(arr) // 2
            left, inv_l = merge_sort(arr[:mid])
            right, inv_r = merge_sort(arr[mid:])
            merged, inv_split = merge(left, right)
            return merged, inv_l + inv_r + inv_split

        def merge(L: List[int], R: List[int]) -> tuple[List[int], int]:
            i = j = inv = 0
            out: List[int] = []
            while i < len(L) and j < len(R):
                if L[i] <= R[j]:
                    out.append(L[i]); i += 1
                else:
                    out.append(R[j]); j += 1
                    inv += len(L) - i        # các L[i..] đều > R[j]
            out.extend(L[i:])
            out.extend(R[j:])
            return out, inv

        _, total = merge_sort(nums)
        return total

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

• Thời gian: O(n log n). Bộ nhớ: O(n) cho auxiliary array.

Bình luận

• Pattern “đếm khi merge” áp dụng cho rất nhiều bài:
  • LC 315 - Count of Smaller Numbers After Self (Chương 22).
  • LC 327 - Count of Range Sum.
  • LC 493 - Reverse Pairs.
• Khác Fenwick tree (BIT): cùng độ phức tạp nhưng Fenwick có hằng số nhỏ hơn.

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

• LC 315 - Count of Smaller Numbers After Self.
• LC 327 - Count of Range Sum.
• LC 493 - Reverse Pairs.

---

17.3 Quickselect - Kth Largest (LC 215) - recap

Đã giải đầy đủ ở Chương 15.1. Ở đây tóm tắt lens D&C.

Đề bài

Cho nums, tìm phần tử lớn thứ k (1-indexed). Pattern D&C giải O(n) trung bình.

Ví dụ

Input:  nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Input:  nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4

Hướng tiếp cận

Quickselect là D&C đặc biệt - đệ quy chỉ 1 nửa (nửa chứa Kth) thay vì cả 2. Vì vậy: - T(n) = T(n/2) + O(n) = O(n) trung bình (không phải O(n log n) như Quicksort). - Worst-case O(n²) nếu pivot xấu - tránh bằng random pivot.

Lưu ý chiều index: partition bên dưới sắp theo thứ tự tăng dần, nên p là vị trí thứ p từ nhỏ nhất (0-based). Kth largest đứng ở vị trí len(nums) - k (0-based) sau khi sort. Vì vậy hàm public LC nhận k 1-indexed và chuyển thành target = len(nums) - k trước khi gọi quickselect.

Code Python 3

import random
from typing import List


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # Kth largest 1-indexed ⇔ vị trí (n - k) 0-based sau khi sort tăng dần.
        target = len(nums) - k
        return self._quickselect(nums, 0, len(nums) - 1, target)

    def _quickselect(self, arr: List[int], lo: int, hi: int, target: int) -> int:
        while lo <= hi:
            p = self._partition(arr, lo, hi)
            if p == target:
                return arr[p]
            elif p < target:
                lo = p + 1
            else:
                hi = p - 1
        return -1  # unreachable theo đề bài

    def _partition(self, arr: List[int], lo: int, hi: int) -> int:
        # Random pivot để tránh worst-case O(n^2) trên input đã sort.
        rand = random.randint(lo, hi)
        arr[rand], arr[hi] = arr[hi], arr[rand]
        pivot = arr[hi]
        store = lo
        for i in range(lo, hi):
            if arr[i] < pivot:
                arr[store], arr[i] = arr[i], arr[store]
                store += 1
        arr[store], arr[hi] = arr[hi], arr[store]
        return store

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

• Thời gian: O(n) trung bình, O(n²) worst-case (rất hiếm với random pivot).
• Bộ nhớ: O(1).

Bình luận

• Bẫy chiều index ở recap version cũ: nếu code lấy p == k mà partition sắp tăng dần thì kết quả thực ra là kth smallest (0-based). Wrapper findKthLargest ở trên chuyển đổi rõ ràng giúp tránh bug này.

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

• LC 215 - Kth Largest Element.
• LC 347 - Top K Frequent Elements.
• LC 973 - K Closest Points to Origin.

---

17.4 Pow(x, n) (LC 50) - recap

Đã giải đầy đủ ở Chương 3.2. Ở đây tóm tắt lens D&C.

Đề bài

Tính x^n với x thực, n nguyên (có thể âm). Pattern D&C cho O(log n).

Ví dụ

Input:  x = 2.00000, n = 10
Output: 1024.00000

Input:  x = 2.10000, n = 3
Output: 9.26100

Input:  x = 2.00000, n = -2
Output: 0.25000   (= 1 / 2^2)

Hướng tiếp cận

x^n = (x^(n/2))^2 (chẵn) hoặc x · (x^((n-1)/2))^2 (lẻ). Mỗi bước chia nửa n → T(n) = T(n/2) + O(1) = O(log n).

Code Python 3

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0: return 1.0
        if n < 0: return 1.0 / self.myPow(x, -n)
        half = self.myPow(x, n // 2)
        return half * half if n % 2 == 0 else half * half * x

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

• Thời gian: O(log n).
• Bộ nhớ: O(log n) stack hoặc O(1) iterative.

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

• LC 50 - Pow(x, n).
• LC 372 - Super Pow.
• LC 29 - Divide Two Integers.

---

17.5 Different Ways to Add Parentheses (LC 241)

Đề bài

Cho biểu thức s chứa số và toán tử +, -, *. Trả về tất cả giá trị có thể có sau khi thêm dấu ngoặc theo các cách khác nhau.

Ví dụ

Input:  s = "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Giải thích:
  (2*(3-(4*5))) = -34
  ((2*3)-(4*5)) = -14
  ((2*(3-4))*5) = -10
  (2*((3-4)*5)) = -10
  (((2*3)-4)*5) = 10

Ràng buộc

• 1 <= len(expression) <= 20
• Operands ∈ [0, 99]

Clarifying questions

• Chỉ 1 số? → Trả [int(s)].
• Toán tử ở đầu/cuối? → Theo đề: input luôn hợp lệ.

Hướng tiếp cận

Tại mỗi toán tử op, chia s thành 2 phần (trái, phải). Đệ quy tính all values của mỗi phần. Kết hợp: với mỗi (l, r) cặp giá trị, thêm l op r vào kết quả.

Memoize theo substring để tránh tính lại.

Hình minh hoạ với "2*3-4":

"2*3-4":
  Tại '*' (pos 1):
    Trái = "2" → [2]
    Phải = "3-4" → đệ quy:
      Tại '-' (pos 1):
        Trái = "3" → [3]
        Phải = "4" → [4]
        → [3 - 4] = [-1]
      → "3-4" có [-1]
    Kết hợp: 2 * -1 = -2

  Tại '-' (pos 3):
    Trái = "2*3" → đệ quy → [6]
    Phải = "4" → [4]
    → [6 - 4] = [2]

  → "2*3-4" có [-2, 2]

Code Python 3

from functools import cache
from typing import List

class Solution:
    def diffWaysToCompute(self, s: str) -> List[int]:

        @cache
        def compute(expr: str) -> tuple[int, ...]:
            if expr.isdigit():
                return (int(expr),)
            result: list[int] = []
            for i, ch in enumerate(expr):
                if ch in '+-*':
                    for l in compute(expr[:i]):
                        for r in compute(expr[i + 1:]):
                            if ch == '+': result.append(l + r)
                            elif ch == '-': result.append(l - r)
                            else: result.append(l * r)
            return tuple(result)

        return list(compute(s))

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

• Thời gian: Catalan-like, ~ O(C_n · n) với C_n = số Catalan thứ n.
• Bộ nhớ: O(C_n) cho cache.

Bình luận

• Pattern “chia tại mỗi toán tử”: Catalan numbers tự nhiên xuất hiện - số cách đặt ngoặc cho n+1 số = C_n.
• Bẫy: quên dùng tuple cho cache (list không hashable).
• Liên hệ: LC 95 (Unique BST II) cùng tinh thần - chia tại mỗi root tiềm năng.

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

• LC 95 - Unique Binary Search Trees II.
• LC 96 - Unique Binary Search Trees.
• LC 894 - All Possible Full Binary Trees.

---

17.6 Closest Pair of Points (bài kinh điển)

Đề bài

Cho n điểm trên mặt phẳng, tìm cặp 2 điểm gần nhất (Euclidean distance). Phải O(n log n).

Ví dụ

Input:  points = [(0,0), (1,1), (4,5), (2,2), (8,8)]
Output: ((0,0), (1,1))  dist = sqrt(2)

Ràng buộc

• 2 <= n <= 10^5
• -10^9 <= x, y <= 10^9

Clarifying questions

• 2 điểm trùng nhau? → Distance = 0; vẫn coi là pair hợp lệ.

Hướng tiếp cận

Brute force - O(n²). So mọi cặp.

D&C - O(n log n).

1. Sort points theo x.
2. Chia làm 2 nửa tại x_mid.
3. Đệ quy tìm d_left, d_right.
4. d = min(d_left, d_right).
5. Strip check: xét các điểm có |x - x_mid| < d, sort theo y, mỗi điểm chỉ cần so với ≤ 7 điểm kế tiếp trong strip (hình học chứng minh).
6. Trả về min.

Đây là bài kinh điển trong giáo trình CS - phần lớn không xuất hiện trên LeetCode chuẩn, nhưng được hỏi ở phỏng vấn Big Tech như một bài tối ưu hoá brute force O(n²).

Code Python 3

import math
from typing import List, Tuple

Point = Tuple[float, float]

class Solution:
    def closestPair(self, points: List[Point]) -> float:
        # Sort by x trước.
        pts_x = sorted(points)

        def dist(p: Point, q: Point) -> float:
            return math.hypot(p[0] - q[0], p[1] - q[1])

        def dc(pts: List[Point]) -> float:
            n = len(pts)
            if n <= 3:
                return min(dist(pts[i], pts[j])
                           for i in range(n) for j in range(i + 1, n))
            mid = n // 2
            mid_x = pts[mid][0]
            d_left = dc(pts[:mid])
            d_right = dc(pts[mid:])
            d = min(d_left, d_right)

            # Strip.
            strip = sorted([p for p in pts if abs(p[0] - mid_x) < d],
                           key=lambda p: p[1])
            for i in range(len(strip)):
                # Chứng minh: chỉ cần kiểm tra ≤ 7 láng giềng theo y.
                for j in range(i + 1, min(i + 8, len(strip))):
                    d = min(d, dist(strip[i], strip[j]))
            return d

        return dc(pts_x)

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

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

Bình luận

• “7 láng giềng” là kết quả hình học cổ điển: trong strip rộng 2d, không quá 6 điểm có thể nằm trong hình vuông d × d (mật độ giới hạn).
• Bài này hiếm thấy ở LeetCode nhưng xuất hiện ở phỏng vấn Big Tech khi bạn nói “ý tưởng cải tiến O(n²)?”.

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

• LC 973 - K Closest Points to Origin (Chương 15).
• LC 587 - Erect the Fence (Convex Hull).

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

D&C recurrence framework

solve(P):
    if |P| ≤ threshold: brute()
    chia P → P1, P2 (gần đều)
    A1 = solve(P1)
    A2 = solve(P2)
    return combine(A1, A2, cross_information)

• Time = T(n) = aT(n/b) + f(n) ⇒ Master theorem.
• Phần khó nhất thường là combine (cross structure).

Recurrence tree (merge sort / inversion count)

n  ━━━ split ━━━ n/2, n/2 ━━━ split ━━━ n/4, n/4, n/4, n/4 ━━━ ...
                                                              depth = log n
combine cost = O(n) mỗi tầng × log n tầng ⇒ O(n log n)

Quickselect vs Sort vs Heap (LC 215 - Kth Largest)

	Quickselect	Heap size k	Sort
Avg	O(n)	O(n log k)	O(n log n)
Worst	O(n²) (random pivot ↘)	O(n log k)	O(n log n)
Tại chỗ	✅	✗ extra heap	✅
Code	trung bình	ngắn	ngắn nhất

Closest Pair (LC tham khảo) - thiết lập

• Sort theo x. Chia làm đôi → solve 2 nửa được d1, d2. Đặt d = min(d1, d2).
• Strip rộng 2d quanh đường chia: chỉ các cặp trong strip mới có thể nhỏ hơn d. Sort strip theo y, mỗi điểm chỉ check 6 điểm kế.

---