Divide and Conquer

Break a problem into independent subproblems, solve recursively, combine the results. Distinct from DP: subproblems don't overlap, so there's no memoization — but the recursion-plus-combine structure is the throughline. Merge sort and quickselect are the canonical templates.

Sub-patterns

• A — Sort-Based Divide and Conquer. Merge sort and its variants.
• B — Counting via Divide and Conquer. Counting inversions during a merge step.
• C — Quickselect. Find the kth element without fully sorting.

Practice set (6)

• Medium — Sort an Array, Kth Largest Element in an Array (also relevant to Heaps and Priority Queues), Different Ways to Add Parentheses
• Hard — Count of Smaller Numbers After Self, Reverse Pairs, Merge k Sorted Lists (also relevant to Heaps and Priority Queues)