> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Divide & Conquer

> Master the paradigm of splitting problems in half, solving each part, and combining results

# Divide & Conquer

## The Mental Model

Divide and Conquer is the **recursive halving strategy**. Instead of solving a problem of size n directly, split it into smaller subproblems (usually halves), solve each recursively, and combine the results. The power comes from reducing O(n^2) to O(n log n).

**Analogy**: Imagine you need to count a huge pile of coins. Instead of counting one by one (O(n)), you split the pile in half, ask two friends to each count their half, and add the results. Each friend does the same--splits their pile and delegates. At the bottom, someone has one coin and just says "1." The work at each level is O(n) (combining), and there are O(log n) levels, giving O(n log n) total.

<Note>
  **Pattern Recognition Signals**:

  * Problem can be split into independent subproblems
  * Combining halves is cheaper than solving directly
  * "Merge" or "split" appears naturally
  * O(n log n) is needed but brute force is O(n²)
</Note>

***

## The D\&C Template

```cpp theme={null}
ReturnType divideAndConquer(Array arr, int lo, int hi) {
    // Base case: single element or empty
    if (lo >= hi) {
        return baseResult(arr, lo);
    }
    
    // Divide
    int mid = lo + (hi - lo) / 2;
    
    // Conquer
    ReturnType leftResult = divideAndConquer(arr, lo, mid);
    ReturnType rightResult = divideAndConquer(arr, mid + 1, hi);
    
    // Combine
    return combine(leftResult, rightResult, arr, lo, mid, hi);
}
```

***

## Pattern 1: Merge Sort

The classic D\&C algorithm. Demonstrates the paradigm perfectly.

```cpp theme={null}
void merge(vector<int>& arr, int lo, int mid, int hi) {
    vector<int> temp(hi - lo + 1);
    int i = lo, j = mid + 1, k = 0;
    
    while (i <= mid && j <= hi) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= hi) temp[k++] = arr[j++];
    
    for (int i = lo; i <= hi; i++) {
        arr[i] = temp[i - lo];
    }
}

void mergeSort(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    
    int mid = lo + (hi - lo) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
}
```

**Complexity Analysis**:

* Divide: O(1)
* Conquer: 2 × T(n/2)
* Combine: O(n)
* Total: T(n) = 2T(n/2) + O(n) = O(n log n)

***

## Pattern 2: Count Inversions

**Problem**: Count pairs (i, j) where i \< j but arr\[i] > arr\[j].

**Insight**: Modified merge sort. During merge, when we pick from the right half, all remaining left elements form inversions with it.

**Why this works**: After dividing and sorting each half, elements within each half are already sorted (no internal inversions left to count--they were counted in deeper recursive calls). The only inversions that remain are cross-boundary pairs: an element from the left half that is larger than an element from the right half. During the merge step, whenever we pick `arr[j]` from the right half because `arr[j] < arr[i]`, all elements from `arr[i]` to `arr[mid]` are also greater than `arr[j]`--that is `mid - i + 1` inversions in one shot.

```cpp theme={null}
long long mergeCount(vector<int>& arr, int lo, int mid, int hi) {
    vector<int> temp(hi - lo + 1);
    int i = lo, j = mid + 1, k = 0;
    long long inversions = 0;
    
    while (i <= mid && j <= hi) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];  // No inversion: left <= right
        } else {
            temp[k++] = arr[j++];
            // arr[j] < arr[i], and arr[i..mid] are all sorted,
            // so all of arr[i..mid] form inversions with arr[j]
            inversions += (mid - i + 1);
        }
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= hi) temp[k++] = arr[j++];
    
    for (int i = lo; i <= hi; i++) arr[i] = temp[i - lo];
    
    return inversions;
}

long long countInversions(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return 0;
    
    int mid = lo + (hi - lo) / 2;
    long long count = 0;
    
    count += countInversions(arr, lo, mid);
    count += countInversions(arr, mid + 1, hi);
    count += mergeCount(arr, lo, mid, hi);
    
    return count;
}
```

**Codeforces Problems**:

| Problem    | Rating | Link                                         |
| ---------- | ------ | -------------------------------------------- |
| Inversions | 1300   | [CSES](https://cses.fi/problemset/task/1633) |

***

## Pattern 3: Maximum Subarray (Kadane Alternative)

**Problem**: Find contiguous subarray with maximum sum.

**D\&C Approach**: Max subarray is either entirely in left, entirely in right, or crosses the middle.

```cpp theme={null}
struct Result {
    long long maxSum;      // Maximum subarray sum
    long long prefixSum;   // Maximum prefix sum
    long long suffixSum;   // Maximum suffix sum
    long long totalSum;    // Total sum of segment
};

Result solve(vector<int>& arr, int lo, int hi) {
    if (lo == hi) {
        return {arr[lo], arr[lo], arr[lo], arr[lo]};
    }
    
    int mid = lo + (hi - lo) / 2;
    Result left = solve(arr, lo, mid);
    Result right = solve(arr, mid + 1, hi);
    
    Result combined;
    combined.totalSum = left.totalSum + right.totalSum;
    combined.prefixSum = max(left.prefixSum, left.totalSum + right.prefixSum);
    combined.suffixSum = max(right.suffixSum, right.totalSum + left.suffixSum);
    combined.maxSum = max({left.maxSum, right.maxSum, 
                           left.suffixSum + right.prefixSum});
    
    return combined;
}
```

***

## Pattern 4: Closest Pair of Points

**Problem**: Given n points in 2D, find the pair with minimum distance.

**Brute Force**: O(n²) - check all pairs.

**D\&C Approach**:

1. Sort by x-coordinate
2. Split into left and right halves
3. Recursively find closest pair in each half
4. Check pairs crossing the middle (the tricky part)

```cpp theme={null}
double closestPair(vector<Point>& points) {
    // Sort by x
    sort(points.begin(), points.end(), [](auto& a, auto& b) {
        return a.x < b.x;
    });
    
    return closest(points, 0, points.size() - 1);
}

double closest(vector<Point>& points, int lo, int hi) {
    if (hi - lo <= 2) {
        return bruteForce(points, lo, hi);
    }
    
    int mid = lo + (hi - lo) / 2;
    double midX = points[mid].x;
    
    double d = min(closest(points, lo, mid), 
                   closest(points, mid + 1, hi));
    
    // Collect points within d of the dividing line
    vector<Point> strip;
    for (int i = lo; i <= hi; i++) {
        if (abs(points[i].x - midX) < d) {
            strip.push_back(points[i]);
        }
    }
    
    // Sort strip by y and check nearby points
    sort(strip.begin(), strip.end(), [](auto& a, auto& b) {
        return a.y < b.y;
    });
    
    for (int i = 0; i < strip.size(); i++) {
        for (int j = i + 1; j < strip.size() && 
             strip[j].y - strip[i].y < d; j++) {
            d = min(d, distance(strip[i], strip[j]));
        }
    }
    
    return d;
}
```

**Key Insight**: In the strip, we only need to check O(1) points for each point (at most 7 points below any point within distance d). This is the non-obvious part that makes the algorithm O(n log n) instead of O(n^2). A geometric packing argument proves it: within a d x 2d rectangle, you can fit at most 8 points that are all at least d apart from each other.

<Tip>
  **Contest tip**: Closest pair of points is a classic ICPC problem. In practice, you can also solve it by sorting by x-coordinate and checking a sliding window, or even by randomized approaches. But the D\&C solution is the textbook approach and good to know for interviews.
</Tip>

***

## Pattern 5: Quick Select (Kth Smallest)

**Problem**: Find kth smallest element in O(n) average time.

**Approach**: Partition like quicksort, but only recurse into the relevant half. This is the "half-lazy quicksort" -- you do one partition, then only explore the side containing the answer.

**Why it is O(n) on average**: After partitioning, you discard roughly half the array. The work at each level sums to n + n/2 + n/4 + ... = 2n = O(n). Compare to quicksort, which must recurse into both halves for O(n log n) total.

**Worst case**: O(n^2) if the pivot is consistently the worst element (e.g., already sorted array with last-element pivot). Randomizing the pivot or using the "median of medians" algorithm guarantees O(n) worst case, but in CP the randomized version is almost always sufficient.

```cpp theme={null}
int partition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi];  // Choose last element as pivot
    int i = lo;           // i tracks the boundary of "elements <= pivot"
    
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            swap(arr[i], arr[j]);  // Move small element to left partition
            i++;
        }
    }
    
    swap(arr[i], arr[hi]);  // Place pivot at its correct sorted position
    return i;               // Pivot is now at index i
}

int quickSelect(vector<int>& arr, int lo, int hi, int k) {
    if (lo == hi) return arr[lo];  // Single element
    
    int pivotIndex = partition(arr, lo, hi);
    
    if (k == pivotIndex) {
        return arr[k];  // Pivot is the kth element
    } else if (k < pivotIndex) {
        return quickSelect(arr, lo, pivotIndex - 1, k);  // Answer is in left half
    } else {
        return quickSelect(arr, pivotIndex + 1, hi, k);  // Answer is in right half
    }
}

int findKthSmallest(vector<int>& arr, int k) {
    return quickSelect(arr, 0, arr.size() - 1, k - 1);  // Convert 1-indexed to 0-indexed
}
```

**Average Time**: O(n) (each level processes n, n/2, n/4, ... which sums to 2n)

<Tip>
  **Contest tip**: In practice, C++ STL's `nth_element` uses a variant of quickselect and is O(n) average. Prefer `nth_element(arr.begin(), arr.begin() + k, arr.end())` over writing your own -- it is faster to type and well-optimized.
</Tip>

***

## The Master Theorem

For recurrences of the form T(n) = aT(n/b) + f(n):

| Case | Condition                          | Result                  |
| ---- | ---------------------------------- | ----------------------- |
| 1    | f(n) = O(n^c) where c \< log\_b(a) | T(n) = O(n^(log\_b(a))) |
| 2    | f(n) = O(n^c) where c = log\_b(a)  | T(n) = O(n^c log n)     |
| 3    | f(n) = O(n^c) where c > log\_b(a)  | T(n) = O(f(n))          |

**Common Examples**:

* 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)
* Strassen: T(n) = 7T(n/2) + O(n²) → O(n^2.81)

***

## Common Mistakes

<Warning>
  **Mistake 1: Wrong Base Case**

  ```cpp theme={null}
  // WRONG: Infinite recursion when lo == hi
  if (lo > hi) return;

  // CORRECT
  if (lo >= hi) return;
  ```
</Warning>

<Warning>
  **Mistake 2: Stack Overflow**
  D\&C depth is O(log n) for balanced splits, but O(n) for unbalanced (like quicksort worst case). Use iterative or randomized pivot.
</Warning>

<Warning>
  **Mistake 3: Inefficient Combine**
  If combine is O(n²), you lose the benefit:

  * Good: O(n) combine → O(n log n) total
  * Bad: O(n²) combine → O(n² log n) total (worse than brute force!)
</Warning>

***

## D\&C vs Other Paradigms

| Aspect      | D\&C          | DP                | Greedy             |
| ----------- | ------------- | ----------------- | ------------------ |
| Subproblems | Independent   | Overlapping       | One choice         |
| Combine     | Merge results | Use cached        | None               |
| Order       | Top-down      | Usually bottom-up | One pass           |
| Example     | Merge sort    | Fibonacci         | Activity selection |

***

## Practice Problems

### Beginner (800-1100)

| Problem          | Concept       | Link                                                           |
| ---------------- | ------------- | -------------------------------------------------------------- |
| Merge Sort       | Basic D\&C    | Classic                                                        |
| Maximum Subarray | D\&C approach | [LeetCode 53](https://leetcode.com/problems/maximum-subarray/) |

### Intermediate (1100-1400)

| Problem          | Concept            | Link                                                                           |
| ---------------- | ------------------ | ------------------------------------------------------------------------------ |
| Count Inversions | Merge sort variant | [CSES](https://cses.fi/problemset/task/1633)                                   |
| Kth Largest      | Quick select       | [LeetCode 215](https://leetcode.com/problems/kth-largest-element-in-an-array/) |

### Advanced (1400-1700)

| Problem      | Concept               | Link                                                     |
| ------------ | --------------------- | -------------------------------------------------------- |
| Closest Pair | Geometric D\&C        | [CSES](https://cses.fi/problemset/task/2194)             |
| Towers       | D\&C + data structure | [CF 37D](https://codeforces.com/problemset/problem/37/D) |

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="Split in Half" icon="scissors">
    Most D\&C algorithms split the problem into two equal halves.
  </Card>

  <Card title="O(n log n)" icon="chart-line">
    The magic of D\&C: reduce O(n²) to O(n log n).
  </Card>

  <Card title="Combine Efficiently" icon="code-merge">
    The combine step must be O(n) or better for efficiency.
  </Card>

  <Card title="Master Theorem" icon="calculator">
    Use it to analyze D\&C recurrences quickly.
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 11: Dynamic Programming Fundamentals" icon="arrow-right" href="/courses/competitive-programming/11-dp-fundamentals">
  Enter the world of DP—the most powerful technique in competitive programming.
</Card>