D&C Practice Questions
Ten interview classics, every D&C shape represented. Each problem is a direct application of one of the four canonical recurrence forms or an advanced pattern — once you spot which shape it is, the code writes itself.
Before reading any solution, force yourself through the four-question checklist:
- How do I split the input?
- What’s the base case?
- What’s the combine step?
- What’s the recurrence and the runtime? (Use the Master Theorem.)
The code is a 10-line transcription of those four answers. If you can write the recurrence, you’ve already solved the analysis.
Easy
| Problem | Pattern | Status |
|---|---|---|
| Pow(x, n) | Fast exponentiation, T(n) = T(n/2) + O(1) | Available |
| Majority Element | T(n) = 2T(n/2) + O(n) plus Boyer-Moore alternative | Available |
Medium
| Problem | Pattern | Status |
|---|---|---|
| Sort an Array (Merge Sort) | Canonical T(n) = 2T(n/2) + O(n) | Available |
| Kth Largest Element in an Array | Quickselect, T(n) = T(n/2) + O(n) avg | Available |
| Maximum Subarray (D&C) | Left / right / crossing, T(n) = 2T(n/2) + O(n) | Available |
| Different Ways to Add Parentheses | D&C on operator positions, exponential branching | Available |
| Search a 2D Matrix II | Quadrant-pruning D&C, staircase O(n+m) alternative | Available |
Hard
| Problem | Pattern | Status |
|---|---|---|
| Count of Smaller Numbers After Self | Merge sort with extra accounting, O(n log n) | Available |
| Median of Two Sorted Arrays | Binary search on partition, O(log min(m, n)) | Available |
| The Skyline Problem | Merge-style D&C on building outlines, O(n log n) | Available |
More Practice (Coming Soon)
| Problem | Pattern | Status |
|---|---|---|
| Reverse Pairs | Merge sort with extra accounting | Coming Soon |
| Count of Range Sum | Merge sort on prefix sums | Coming Soon |
| Largest Rectangle in Histogram (D&C) | Recursive on minimum index | Coming Soon |
| Closest Pair of Points | Strip-step D&C | Coming Soon |
| Burst Balloons | Interval D&C (also DP) | Coming Soon |
| Find Peak Element | Binary-search D&C | Coming Soon |
| Convex Hull (Quickhull) | D&C on point positions | Coming Soon |
| K Closest Points to Origin | Quickselect by distance | Coming Soon |
| Construct BST from Preorder | Recursive split on first element | Coming Soon |
| Beautiful Array | Constructive D&C | Coming Soon |