Pattern — Divide and Conquer

Cross-reference

Đây là alias đến Pattern-Recursion-DC focus vào D&C riêng.

Master theorem (rút gọn cho interview)

$T(N)=a\cdot T(N/b)+f(N)$:

• $a=b^k$ với $f(N)=O(N^k)$ → $T(N)=O(N^k\log N)$ — vd: merge sort $O(N\log N)$
• $a<b^k$ → $T(N)=O(N^k)$ — work outside dominates
• $a>b^k$ → $T(N)=O(N^{{\log }_{b}a})$ — work inside dominates — vd: Karatsuba $O(N^{1.585})$

Khi D&C tốt hơn DP / Greedy?

Tình huống	Đề xuất
Subproblems độc lập (không overlap)	D&C
Subproblems lồng nhau (overlapping)	DP (memoize)
Có greedy choice property	Greedy
Cần combine theo range/interval	D&C

Top problems

Bài	LC	Note
Merge Sort	—	Classic D&C + merge — backbone của Counting Inversions
Quick Sort	—	D&C + partition; randomize pivot
Quickselect	LC #215	D&C only 1 side → $O(N)$ avg
Counting Inversions	LC #493 (variant)	Merge sort + count
Reverse Pairs	LC #493	Merge sort + count cặp i < j, nums[i] > 2*nums[j]
Maximum Subarray	LC #53	D&C $O(N\log N)$ vs Kadane $O(N)$
Pow(x, n)	LC #50	Fast exponentiation $O(\log N)$
Closest Pair of Points	—	$O(N\log N)$
Median of 2 Sorted Arrays	LC #4	D&C trên indices, $O(\log (\min (m,n)))$

Pitfalls

1. Off-by-one trong mid — chọn convention closed [lo, hi] hoặc half-open [lo, hi) rồi nhất quán.
2. Merge step thiếu i/j check: phải xử lý phần còn lại của 1 mảng khi mảng kia hết.
3. Combine không O(N) → tổng phức tạp xấu hơn.

→ Nguồn: 05-Divide-and-Conquer