05-Divide-and-Conquer

Buổi 05 — Divide and Conquer

Navigation

← 04-Advanced-Binary-Search | → 06-String-Matching-Trie Giai đoạn: FAANG Mastery | Độ khó: ⭐⭐⭐⭐

---

1. Analogy & Context

Julius Caesar Analogy

Divide and Conquer = “Chiến lược chia để trị” của Julius Caesar.

Đế chế La Mã quá lớn để quản lý trực tiếp:

• Divide: chia đế chế thành các tỉnh nhỏ (subproblems)
• Conquer: mỗi tỉnh tự trị độc lập (solve subproblems recursively)
• Combine: tổng hợp kết quả từ các tỉnh thành quốc sách chung (merge results)

Key insight khác với DP: Các tỉnh KHÔNG chia sẻ tài nguyên (subproblems are INDEPENDENT). Mỗi tỉnh giải quyết vấn đề của chính nó mà không cần biết tỉnh khác làm gì.

D&C vs Dynamic Programming — sự khác biệt cốt lõi:

	Divide & Conquer	Dynamic Programming
Subproblems	Independent (no overlap)	Overlapping (shared)
Reuse	Not needed	Memoization/tabulation
Examples	Merge Sort, Fast Power	Fibonacci, Knapsack
Structure	Tree of calls	DAG of states

FAANG Signal

D&C là nền tảng để hiểu DP (DP = D&C + memoization). Hiểu rõ D&C giúp bạn phân tích complexity qua Master Theorem và thiết kế algorithms như Merge Sort, Quick Sort, Fast Fourier Transform.

---

2. The FAANG Standard

Master Theorem — Complexity của D&C algorithms:

$T(N)=a\cdot T(N/b)+O(N^d)$

Condition	Complexity	Example
$d<{\log }_{b}a$	$O(N^{{\log }_{b}a})$	Strassen matrix mult: O(N^2.81)
$d={\log }_{b}a$	$O(N^d\log N)$	Merge Sort: O(N log N)
$d>{\log }_{b}a$	$O(N^d)$	Binary Search: O(log N)

Ứng dụng Master Theorem:

Algorithm	Recurrence	Result
Merge Sort	$T(N)=2T(N/2)+O(N)$	$O(N\log N)$
Binary Search	$T(N)=T(N/2)+O(1)$	$O(\log N)$
Fast Power	$T(N)=T(N/2)+O(1)$	$O(\log N)$
Max Subarray D&C	$T(N)=2T(N/2)+O(N)$	$O(N\log N)$
Naive Matrix Mult	$T(N)=8T(N/2)+O(N^2)$	$O(N^3)$

---

3. Visual Thinking (Mermaid)

3.1 D&C Structure

graph TD
    Root["PROBLEM(N)"] -->|"Divide"| Left["SUBPROBLEM(N/2)"]
    Root -->|"Divide"| Right["SUBPROBLEM(N/2)"]
    Left --> LL["SUBPROBLEM(N/4)"]
    Left --> LR["SUBPROBLEM(N/4)"]
    Right --> RL["SUBPROBLEM(N/4)"]
    Right --> RR["SUBPROBLEM(N/4)"]
    LL & LR -->|"Combine"| Left
    RL & RR -->|"Combine"| Right
    Left & Right -->|"Combine"| Root

    style Root fill:#4a9eff,color:#fff
    style Left fill:#8b5cf6,color:#fff
    style Right fill:#8b5cf6,color:#fff

3.2 Merge Sort as D&C Tree

graph TD
    A["[38, 27, 43, 3, 9, 82, 10]"] -->|"split"| B["[38, 27, 43, 3]"]
    A -->|"split"| C["[9, 82, 10]"]
    B -->|"split"| D["[38, 27]"]
    B -->|"split"| E["[43, 3]"]
    D -->|"split"| F["[38]"]
    D -->|"split"| G["[27]"]
    F & G -->|"merge"| H["[27, 38]"]
    E -->|"split"| I["[43]"]
    E -->|"split"| J["[3]"]
    I & J -->|"merge"| K["[3, 43]"]
    H & K -->|"merge"| L["[3, 27, 38, 43]"]
    C -->|"..."| M["[9, 10, 82]"]
    L & M -->|"merge"| N["[3, 9, 10, 27, 38, 43, 82]"]

    style N fill:#22c55e,color:#fff

3.3 Closest Pair — Cross-midline Merge Step

flowchart LR
    subgraph Left["Left Half"]
        LP["Points sorted by X<br/>Min dist = d_L"]
    end
    subgraph Right["Right Half"]
        RP["Points sorted by X<br/>Min dist = d_R"]
    end
    subgraph Strip["Strip Zone |x - mid| < d"]
        SP["Check pairs in strip<br/>Only need O(7) comparisons per point!"]
    end

    Left -->|"d = min(d_L, d_R)"| Strip
    Right --> Strip
    Strip -->|"Combine"| Ans["Answer = min(d, strip_min)"]

    style Ans fill:#22c55e,color:#fff

---

4. TypeScript Template

4.1 Generic D&C Template

// ============================================================
// GENERIC D&C TEMPLATE
// Three phases: divide, conquer, combine
// ============================================================
function divideAndConquer<T, R>(
    problem: T[],
    lo: number,
    hi: number,
    baseCase: (arr: T[], lo: number, hi: number) => R,
    divide: (arr: T[], lo: number, hi: number) => number,           // returns mid
    conquerLeft: (arr: T[], lo: number, mid: number) => R,
    conquerRight: (arr: T[], mid: number, hi: number) => R,
    combine: (left: R, right: R, arr: T[], lo: number, hi: number) => R
): R {
    // Base case: small enough to solve directly
    if (hi - lo <= 1) {
        return baseCase(problem, lo, hi);
    }
 
    // Divide
    const mid = divide(problem, lo, hi);
 
    // Conquer (independently)
    const leftResult = conquerLeft(problem, lo, mid);
    const rightResult = conquerRight(problem, mid, hi);
 
    // Combine
    return combine(leftResult, rightResult, problem, lo, hi);
}

4.2 Merge Sort — Revisited with D&C Lens

// Classic merge sort — the canonical D&C algorithm
function mergeSort(arr: number[]): number[] {
    // Base case: array of 0 or 1 element is already sorted
    if (arr.length <= 1) return arr;
 
    // ── DIVIDE ────────────────────────────────────────────────────────────────
    const mid = Math.floor(arr.length / 2);
 
    // ── CONQUER (independent recursive calls) ─────────────────────────────────
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
 
    // ── COMBINE ───────────────────────────────────────────────────────────────
    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++]);
        }
    }
 
    // Append remaining elements
    while (i < left.length) result.push(left[i++]);
    while (j < right.length) result.push(right[j++]);
 
    return result;
}
// T(N) = 2T(N/2) + O(N) → O(N log N) by Master Theorem

4.3 Maximum Subarray — Cross-Boundary Helper

// The COMBINE step for D&C max subarray
// Find max subarray that crosses the midpoint
// (extends from mid going left AND from mid+1 going right)
function maxCrossingSubarray(
    nums: number[],
    lo: number,
    mid: number,
    hi: number
): number {
    // Extend LEFT from mid
    let leftMax = -Infinity;
    let currentSum = 0;
    for (let i = mid; i >= lo; i--) {
        currentSum += nums[i];
        leftMax = Math.max(leftMax, currentSum);
    }
 
    // Extend RIGHT from mid+1
    let rightMax = -Infinity;
    currentSum = 0;
    for (let i = mid + 1; i <= hi; i++) {
        currentSum += nums[i];
        rightMax = Math.max(rightMax, currentSum);
    }
 
    return leftMax + rightMax;  // crossing subarray must include both sides
}

4.4 Maximum Subarray D&C — O(N log N)

// LeetCode #53 — D&C approach
// For each subarray, max is either:
//   (a) entirely in left half
//   (b) entirely in right half
//   (c) crossing the midpoint ← only this requires work in combine step
function maxSubarrayDC(nums: number[]): number {
    return dcHelper(nums, 0, nums.length - 1);
}
 
function dcHelper(nums: number[], lo: number, hi: number): number {
    // Base case
    if (lo === hi) return nums[lo];
 
    // Divide
    const mid = lo + Math.floor((hi - lo) / 2);
 
    // Conquer
    const leftMax = dcHelper(nums, lo, mid);
    const rightMax = dcHelper(nums, mid + 1, hi);
 
    // Combine: check crossing
    const crossMax = maxCrossingSubarray(nums, lo, mid, hi);
 
    return Math.max(leftMax, rightMax, crossMax);
}
 
// T(N) = 2T(N/2) + O(N) → O(N log N)
// Compare: Kadane's Algorithm = O(N) — D&C is WORSE here!
// But D&C teaches the pattern used in: count inversions, closest pair, etc.

4.5 Count Inversions — D&C with Merge

// Count pairs (i, j) where i < j but nums[i] > nums[j]
// Classic D&C: count inversions in left, right, and across boundary
function countInversions(nums: number[]): number {
    const result = mergeSortCount(nums.slice());
    return result.count;
}
 
function mergeSortCount(arr: number[]): { sorted: number[]; count: number } {
    if (arr.length <= 1) return { sorted: arr, count: 0 };
 
    const mid = Math.floor(arr.length / 2);
    const { sorted: left, count: leftCount } = mergeSortCount(arr.slice(0, mid));
    const { sorted: right, count: rightCount } = mergeSortCount(arr.slice(mid));
 
    // Merge and count cross-boundary inversions
    const merged: number[] = [];
    let crossCount = 0;
    let i = 0, j = 0;
 
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            merged.push(left[i++]);
        } else {
            // left[i] > right[j]: ALL remaining elements in left are inversions with right[j]
            crossCount += left.length - i;
            merged.push(right[j++]);
        }
    }
 
    while (i < left.length) merged.push(left[i++]);
    while (j < right.length) merged.push(right[j++]);
 
    return {
        sorted: merged,
        count: leftCount + rightCount + crossCount
    };
}
 
// T(N) = 2T(N/2) + O(N) → O(N log N) — same as merge sort
// Naive: O(N²) — check all pairs

4.6 Fast Power — Exponentiation by Squaring

// LeetCode #50 — Pow(x, n)
// Key insight: x^n = (x^(n/2))^2  if n is even
//              x^n = x * (x^(n/2))^2  if n is odd
// Recurrence: T(N) = T(N/2) + O(1) → O(log N) by Master Theorem
 
function myPow(x: number, n: number): number {
    // Handle negative exponent: x^(-n) = 1 / x^n
    if (n < 0) return 1 / myPow(x, -n);
 
    // Base cases
    if (n === 0) return 1;
    if (n === 1) return x;
 
    // ── DIVIDE ────────────────────────────────────────────────────────────────
    const half = Math.floor(n / 2);
 
    // ── CONQUER ───────────────────────────────────────────────────────────────
    const halfPow = myPow(x, half);     // solve smaller problem
 
    // ── COMBINE ───────────────────────────────────────────────────────────────
    if (n % 2 === 0) {
        return halfPow * halfPow;           // x^n = (x^(n/2))^2
    } else {
        return halfPow * halfPow * x;       // x^n = x * (x^(n/2))^2
    }
}
 
/*
TRACE: myPow(2, 10)
myPow(2, 10) = myPow(2, 5)^2
myPow(2, 5)  = 2 * myPow(2, 2)^2
myPow(2, 2)  = myPow(2, 1)^2
myPow(2, 1)  = 2                      ← base case
 
Unrolling up:
myPow(2, 2)  = 2^2 = 4
myPow(2, 5)  = 2 * 4^2 = 2 * 16 = 32
myPow(2, 10) = 32^2 = 1024  ✓
 
Total recursive calls: O(log 10) ≈ 4 calls
vs naive O(N=10) multiplications
*/
 
// Iterative version (avoids call stack overflow for very large n):
function myPowIterative(x: number, n: number): number {
    if (n < 0) { x = 1 / x; n = -n; }
 
    let result = 1;
    let base = x;
 
    while (n > 0) {
        if (n % 2 === 1) result *= base;    // if current bit is 1, multiply
        base *= base;                        // square the base
        n = Math.floor(n / 2);              // shift right (process next bit)
    }
 
    return result;
}

4.7 Majority Element — Boyer-Moore Voting

// LeetCode #169 — Majority Element
// Problem: Find element appearing > N/2 times
// Boyer-Moore Voting: O(N) time, O(1) space
 
function majorityElement(nums: number[]): number {
    let candidate = nums[0];
    let count = 1;
 
    for (let i = 1; i < nums.length; i++) {
        if (count === 0) {
            // No current candidate — adopt nums[i]
            candidate = nums[i];
            count = 1;
        } else if (nums[i] === candidate) {
            count++;    // support current candidate
        } else {
            count--;    // "cancel out" one vote for candidate
        }
    }
 
    return candidate;   // majority element guaranteed to exist
 
    // WHY THIS WORKS:
    // Intuition: majority element M appears > N/2 times.
    // Every "cancellation" removes one M and one non-M.
    // Even after all non-M elements cancel M, M still has votes left.
    // The last standing candidate MUST be M.
}
 
/*
TRACE for nums = [2, 2, 1, 1, 1, 2, 2]:
i=0: candidate=2, count=1
i=1: nums[1]=2 == candidate → count=2
i=2: nums[2]=1 ≠ candidate → count=1
i=3: nums[3]=1 ≠ candidate → count=0
i=4: count=0 → candidate=1, count=1
i=5: nums[5]=2 ≠ candidate=1 → count=0
i=6: count=0 → candidate=2, count=1
return 2 ✓  (2 appears 4 times > 7/2=3.5)
 
NOTE: This is NOT D&C — it's a greedy/voting algorithm.
D&C approach for majority exists but is O(N log N).
Boyer-Moore is included here as the canonical O(N)/O(1) solution for FAANG.
*/

---

5. Complexity Deep-dive

Master Theorem Applied

$T(N)=2T(N/2)+O(N)$

• $a=2$ (two subproblems), $b=2$ (each half size), $d=1$ (merge is O(N))
• ${\log }_{b}a={\log }_{2}2=1=d$ → Case 2: $O(N^d\log N)=O(N\log N)$

Algorithm	Recurrence	a	b	d	Result
Merge Sort	$2T(N/2)+N$	2	2	1	$O(N\log N)$
Max Subarray D&C	$2T(N/2)+N$	2	2	1	$O(N\log N)$
Binary Search	$T(N/2)+1$	1	2	0	$O(\log N)$
Fast Power	$T(N/2)+1$	1	2	0	$O(\log N)$
Naive Matrix Mult	$8T(N/2)+N^2$	8	2	2	$O(N^3)$
Strassen	$7T(N/2)+N^2$	7	2	2	$O(N^{2.81})$

Khi D&C tệ hơn alternatives:

Problem	D&C	Better Alternative
Max Subarray	$O(N\log N)$	Kadane’s $O(N)$
Fibonacci	$O(2^N)$ naively	DP $O(N)$
Sorting with many duplicates	$O(N\log N)$	Counting Sort $O(N+K)$

---

6. Edge Cases & Pitfalls

Forgetting the Combine Step

D&C chỉ có ý nghĩa khi có bước combine thực sự.

• Nếu chỉ divide rồi conquer mà không combine gì → thường chỉ là simple recursion
• Max Subarray: combine step là maxCrossingSubarray — đây là phần “khó” nhất!

Off-by-One trong Mid Calculation

// Safe (no overflow, correct flooring):
const mid = lo + Math.floor((hi - lo) / 2);
 
// For merge sort with array indices:
const mid = Math.floor((lo + hi) / 2);  // fine for JS (no int overflow)
 
// WRONG for large numbers (other languages):
const mid = (lo + hi) / 2;  // overflow in C++/Java if lo+hi > INT_MAX

Base Case Phải Dừng Recursion Đúng

Thiếu hoặc sai base case = infinite recursion (stack overflow).

// Wrong: never reaches base case if lo >= hi not handled
if (lo === hi) return nums[lo];   // what about empty array (lo > hi)?
 
// Correct: handle both
if (lo >= hi) return lo === hi ? nums[lo] : -Infinity;

D&C vs DP — Chọn Cái Nào?

• Vẽ recursion tree: có overlapping subproblems không?
• Fibonacci: fib(3) được tính nhiều lần → DP (memoize)
• Merge Sort: mỗi subarray chỉ merge một lần → D&C
• Quick Rule: nếu subproblems overlap, dùng DP. Nếu independent, D&C đủ.

Fast Power — Negative Exponent

n có thể âm: $x^{-n}=1/x^n$. Đặc biệt: n = -2147483648 (MIN_INT) → -n overflow trong C++/Java! Trong JS/TS, numbers là float64 nên không có vấn đề này, nhưng vẫn nên aware.

---

7. Pattern Recognition

Khi Nào Dùng Divide & Conquer

“Count/find across a boundary” → D&C với merge step → Count inversions, closest pair of points, count range sum

“Sort / find k-th in sorted order” → D&C (merge sort, quick select) → Merge K sorted lists, nth element

“Fast exponentiation” → D&C squaring → x^n, matrix power (Fibonacci in O(log N)), mod exponentiation

“Optimal split into halves” → D&C with max/min combine → Max subarray D&C, closest pair

Karatsuba multiplication — multiply two N-digit numbers: → $O(N^{1.585})$ thay vì $O(N^2)$ naive

Matrix exponentiation — Fibonacci trong $O(\log N)$: → $\left[\begin{array}{c}F(n+1)\\ F(n)\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\left[\begin{array}{c}1\\ 0\end{array}\right]$

Dấu hiệu nhận biết:

• Bài toán có thể chia đôi và kết quả combine được
• “Count something across a midpoint”
• “Fast computation of x^n, matrix^n”
• “Merge K sorted structures”

---

8. Top LeetCode Problems

#	Problem	Difficulty	D&C Technique
LC-53 #53	Maximum Subarray (D&C)	Medium	Cross-boundary combine
LC-315 #315	Count Smaller Numbers After Self	Hard	Merge sort + count
LC-23 #23	Merge K Sorted Lists	Hard	D&C merge
LC-50 #50	Pow(x, n)	Medium	Fast exponentiation
LC-169 #169	Majority Element	Medium	Boyer-Moore (or D&C)
LC-912 #912	Sort an Array	Medium	Merge sort implementation
LC-327 #327	Count of Range Sum	Hard	D&C + merge
LC-240 #240	Search 2D Matrix II	Medium	D&C on quadrants

Complete Solutions: #50 Pow(x,n) and #169 Majority Element

// ============================================================
// LeetCode #50 — Pow(x, n)
// Using fast exponentiation (exponentiation by squaring)
// ============================================================
function myPowFull(x: number, n: number): number {
    // Handle negative exponent
    // x^(-n) = (1/x)^n
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
 
    return fastPow(x, n);
}
 
function fastPow(x: number, n: number): number {
    if (n === 0) return 1;
 
    // ── DIVIDE: compute half power ─────────────────────────────────────────
    const half = fastPow(x, Math.floor(n / 2));
 
    // ── COMBINE: square the half power ────────────────────────────────────
    if (n % 2 === 0) {
        return half * half;         // x^(2k) = (x^k)^2
    } else {
        return half * half * x;     // x^(2k+1) = x * (x^k)^2
    }
}
 
/*
PROOF OF CORRECTNESS:
- n=0: base case, x^0 = 1 ✓
- n even: x^n = x^(2k) = (x^k)^2 = half*half ✓
- n odd:  x^n = x^(2k+1) = x * x^(2k) = x * (x^k)^2 = x * half*half ✓
 
COMPLEXITY:
- T(n) = T(n/2) + O(1) → O(log n) by Master Theorem
- Each call reduces n by half → log₂(n) levels of recursion
- vs naive: O(n) multiplications
 
TRACE: myPow(2, 13)
fastPow(2, 13)  → n=13 odd: need fastPow(2, 6)
fastPow(2, 6)   → n=6 even: need fastPow(2, 3)
fastPow(2, 3)   → n=3 odd: need fastPow(2, 1)
fastPow(2, 1)   → n=1 odd: need fastPow(2, 0)
fastPow(2, 0)   → return 1
 
Unwinding:
fastPow(2, 1)   = 1*1*2   = 2
fastPow(2, 3)   = 2*2*2   = 8
fastPow(2, 6)   = 8*8     = 64
fastPow(2, 13)  = 64*64*2 = 8192  ✓ (2^13 = 8192)
 
Only 4 recursive calls instead of 13 multiplications!
*/
 
// ============================================================
// LeetCode #169 — Majority Element
// Boyer-Moore Voting Algorithm
// ============================================================
function majorityElementFull(nums: number[]): number {
    // Phase 1: Find the CANDIDATE
    let candidate = nums[0];
    let votes = 1;
 
    for (let i = 1; i < nums.length; i++) {
        if (votes === 0) {
            // Previous candidate eliminated — start fresh
            candidate = nums[i];
            votes = 1;
        } else if (nums[i] === candidate) {
            votes++;    // vote FOR candidate
        } else {
            votes--;    // vote AGAINST candidate (mutual elimination)
        }
    }
 
    // Phase 2: Verify (only needed if majority NOT guaranteed)
    // Problem guarantees majority exists, so we skip verification.
    // But in interviews, always mention this step exists.
 
    /*
    // Verification code (if needed):
    let count = 0;
    for (const num of nums) {
        if (num === candidate) count++;
    }
    return count > nums.length / 2 ? candidate : -1;
    */
 
    return candidate;
}
 
/*
WHY BOYER-MOORE WORKS — Mathematical Proof:
Let M = majority element (appears > N/2 times).
Let non-M elements total < N/2 appearances.
 
Every cancellation removes exactly 1 count of M and 1 count of non-M.
Total cancellations possible by non-M = (count of non-M) < N/2.
Total M appearances = > N/2.
 
After all cancellations: M still has (M count) - (non-M count) > 0 votes.
Therefore M is the last candidate standing. ✓
 
TRACE for [2, 2, 1, 1, 1, 2, 2]:
           candidate  votes  action
Start:     2          1
nums[1]=2: 2          2      same candidate
nums[2]=1: 2          1      cancel
nums[3]=1: 2          0      cancel → votes=0
nums[4]=1: 1          1      new candidate (votes was 0)
nums[5]=2: 1          0      cancel → votes=0
nums[6]=2: 2          1      new candidate (votes was 0)
return 2 ✓
 
Count check: 2 appears 4 times > 7/2=3.5 ✓
 
COMPLEXITY: O(N) time, O(1) space
vs Sorting: O(N log N)
vs HashMap: O(N) time but O(N) space
 
The D&C approach (#169):
- Divide array in half
- Majority of whole = majority of at least one half
- If both halves have same majority → that's the answer
- If different majorities → count both in full array, pick larger
- T(N) = 2T(N/2) + O(N) → O(N log N)  ← SLOWER than Boyer-Moore!
 
Conclusion: Boyer-Moore wins for this problem. D&C is educational but not optimal.
*/

---

9. Self-Assessment Checklist

Checklist sau khi học Divide & Conquer

• Giải thích ba bước Divide / Conquer / Combine với ví dụ cụ thể
• Áp dụng Master Theorem cho T(N) = 2T(N/2) + O(N)
• Implement merge sort từ đầu không nhìn note
• Implement fast power (Pow(x,n)) với cả recursive và iterative
• Giải thích tại sao Boyer-Moore voting works (mathematical proof)
• Implement countInversions bằng D&C
• Biết khi nào D&C tệ hơn DP (overlapping subproblems)
• Giải thích sự khác biệt giữa D&C và DP với ví dụ
• Nhận ra “count across boundary” pattern trong bài toán mới

Luyện tập tiếp theo

• #315 Count Smaller Numbers After Self — D&C merge count (Hard)
• #23 Merge K Sorted Lists — D&C on lists (Hard)
• #327 Count of Range Sum — hard D&C
• Matrix exponentiation cho Fibonacci trong O(log N)
• Karatsuba algorithm concept (không cần implement)

---

Tags: dsa divide-and-conquer merge-sort fast-power master-theorem faang-mastery Related: 04-Advanced-Binary-Search | 06-String-Matching-Trie | Pattern-Recursion-DC