Divide & Conquer | Phase 3

The 3 Steps

Divide

Split problem into 2+ smaller subproblems of the same type. Usually at midpoint.

Conquer

Solve each subproblem recursively. Base case: problem small enough to solve directly.

Merge

Combine solutions of subproblems into solution for original problem. This is where the real work happens.

C++
// D&C template
int solve(vector<int>& arr, int l, int r) {
    // BASE CASE
    if(l==r) return arr[l];
    // DIVIDE
    int mid = l+(r-l)/2;
    // CONQUER
    int left  = solve(arr, l, mid);
    int right = solve(arr, mid+1, r);
    // MERGE
    return max(left, right);  // example: range max query
}
// Key property: subproblems are INDEPENDENT (unlike DP where they overlap)
    

Interactive: D&C Split and Merge

Watch divide and conquer split [4, 2, 7, 1] into halves, sort each independently, then merge them back.

Practice Problems

#169Majority ElementEasy

Find element that appears more than n/2 times. Guaranteed to exist.

Boyer-Moore Vote: O(n) O(1) solution. Maintain candidate and count. If count = 0, change candidate. Increment if match, decrement if not.

C++
int majorityElement(vector<int>& nums) {
    int candidate=nums[0], count=1;
    for(int i=1;i<nums.size();i++) {
        if(count==0) { candidate=nums[i]; count=1; }
        else if(nums[i]==candidate) count++;
        else count--;
    }
    return candidate;
}
// Time: O(n)  Space: O(1)

#53Maximum Subarray (D&C)Medium

Find the maximum sum contiguous subarray. D&C approach for understanding; Kadane's is O(n) O(1).

D&C: Max subarray is either: entirely in left half, entirely in right half, or crosses the midpoint. For crossing: extend from mid left and mid+1 right taking max sums.

C++
int maxCross(vector<int>& a, int l, int m, int r) {
    int ls=INT_MIN, s=0;
    for(int i=m;i>=l;i--) { s+=a[i]; ls=max(ls,s); }
    int rs=INT_MIN; s=0;
    for(int i=m+1;i<=r;i++) { s+=a[i]; rs=max(rs,s); }
    return ls+rs;
}
int maxSubDC(vector<int>& a, int l, int r) {
    if(l==r) return a[l];
    int m=l+(r-l)/2;
    return max({maxSubDC(a,l,m), maxSubDC(a,m+1,r), maxCross(a,l,m,r)});
}
// Time: O(n log n)  Space: O(log n)  [Kadane's is O(n) O(1)]

#218The Skyline ProblemHard

Given buildings [left, right, height], output the skyline profile as a list of [x, height] critical points.

Pattern: Use sorted events (building start/end). Max-heap tracks active heights. On start: push height. On end: remove height. Record change when max height changes.

C++
vector<vector<int>> getSkyline(vector<vector<int>>& blds) {
    vector<pair<int,int>> events;
    for(auto& b:blds) {
        events.push_back({b[0],-b[2]});  // start: negative height
        events.push_back({b[1], b[2]});  // end:   positive height
    }
    sort(events.begin(),events.end());
    multiset<int> heights = {0};
    vector<vector<int>> res;
    int prevMax=0;
    for(auto&[x,h]:events) {
        if(h<0) heights.insert(-h);   // building starts
        else   heights.erase(heights.find(h));  // building ends
        int curMax=*heights.rbegin();
        if(curMax!=prevMax) {
            res.push_back({x,curMax});
            prevMax=curMax;
        }
    }
    return res;
}
// Time: O(n log n)  Space: O(n)

#427Construct Quad TreeMedium

Build a quad tree from a 2D binary grid. If all cells in a region are the same, make it a leaf node.

Pattern: D&C. Check if region is uniform. If yes → leaf. If no → divide into 4 quadrants, recurse on each.

C++
struct Node { bool val,isLeaf; Node *tl,*tr,*bl,*br; };
bool uniform(vector<vector<int>>& g, int r, int c, int n) {
    for(int i=r;i<r+n;i++) for(int j=c;j<c+n;j++)
        if(g[i][j]!=g[r][c]) return false;
    return true;
}
Node* build(vector<vector<int>>& g, int r, int c, int n) {
    if(uniform(g,r,c,n)) return new Node{(bool)g[r][c],true};
    int h=n/2;
    return new Node{true,false,
        build(g,r,c,h),   build(g,r,c+h,h),
        build(g,r+h,c,h), build(g,r+h,c+h,h)};
}
Node* construct(vector<vector<int>>& grid) {
    return build(grid,0,0,grid.size());
}

#241Different Ways to Add ParenthesesMedium

Add parentheses in all possible ways to evaluate a math expression string. Return all possible results.

Pattern: Divide at each operator: split into left/right subexpressions, recursively compute all values for each, combine with the operator. Pure D&C.

C++
vector<int> diffWays(string expr) {
    vector<int> res;
    for(int i=0;i<(int)expr.size();i++) {
        char c=expr[i];
        if(c=='+'||c=='-'||c=='*') {
            auto L=diffWays(expr.substr(0,i));
            auto R=diffWays(expr.substr(i+1));
            for(int l:L) for(int r:R) {
                if(c=='+') res.push_back(l+r);
                if(c=='-') res.push_back(l-r);
                if(c=='*') res.push_back(l*r);
            }
        }
    }
    if(res.empty()) res.push_back(stoi(expr));  // base case: pure number
    return res;
}
// Time: O(Catalan(n))  Space: O(Catalan(n))

#932Beautiful ArrayMedium

Return any permutation of [1..n] such that for every i < k < j, A[k]*2 ≠ A[i] + A[j].

Pattern: D&C insight: if A is beautiful, then [2A-1] (all odds) and [2A] (all evens) are also beautiful. Merge: odd+even eliminates all cross-pairs since odd+even is always odd, but 2*(any)=even.

C++
vector<int> beautifulArray(int n) {
    vector<int> res = {1};
    while((int)res.size() < n) {
        vector<int> tmp;
        for(int x : res) if(2*x-1 <= n) tmp.push_back(2*x-1);  // odd half
        for(int x : res) if(2*x   <= n) tmp.push_back(2*x);    // even half
        res = tmp;
    }
    return res;
}
// Time: O(n log n)  Space: O(n)

#23Merge k Sorted ListsHard

Merge k sorted linked lists into one sorted linked list.

Pattern: D&C on the list array. Split k lists in half, recursively merge each half, then merge the two resulting lists. O(n log k) total — each element passes through O(log k) merges.

C++
ListNode* merge2(ListNode* l1, ListNode* l2) {
    ListNode dummy(0); ListNode* cur=&dummy;
    while(l1&&l2) {
        if(l1->val<=l2->val){cur->next=l1;l1=l1->next;}
        else               {cur->next=l2;l2=l2->next;}
        cur=cur->next;
    }
    cur->next=l1?l1:l2;
    return dummy.next;
}
ListNode* mergeK(vector<ListNode*>& lists, int lo, int hi) {
    if(lo==hi) return lists[lo];
    int mid=lo+(hi-lo)/2;
    return merge2(mergeK(lists,lo,mid), mergeK(lists,mid+1,hi));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.empty()) return nullptr;
    return mergeK(lists,0,lists.size()-1);
}
// Time: O(n log k)  Space: O(log k) stack

D&C vs DP: Use D&C when subproblems are independent (no reuse needed). Use DP when subproblems overlap (same sub-problem solved multiple times). If you're caching recursive results, it's DP not D&C.

Deeper Understanding

When to Divide and When to Memo

D&C vs DP: The Key Distinction

When to Use Divide and Conquer

Problem splits into independent halves

Merge sort, quicksort, binary search, merge k lists. Each half is truly independent — no shared state.

"Crossing" problems — answer spans a boundary

Maximum subarray D&C, skyline problem. Three cases: entirely left, entirely right, or crossing midpoint.

Recursive structure maps to problem structure

Quad tree, expression evaluation (#241), segment trees. The problem decomposition mirrors the data structure.

Need worst-case O(n log n)

D&C algorithms often achieve O(n log n) via the master theorem: T(n)=2T(n/2)+O(n) → O(n log n).

Merging two results is O(n) or cheaper

The merge step dominates. If merging is O(n log n), the overall algorithm is O(n log² n) — sometimes worth it.

Common Misconceptions

"D&C and recursion are the same thing"

Wrong. All D&C is recursive, but not all recursion is D&C. D&C specifically splits into independent subproblems and merges. DFS, backtracking, memoization are recursion but not D&C.

"D&C is always O(n log n)"

Depends on the merge step. Binary search: O(log n). Strassen matrix multiply: O(n^2.81). Closest pair of points: O(n log n). Master theorem tells you exactly.

"If subproblems overlap, add memoization to D&C"

Yes, but that becomes DP. Memoized recursion (top-down DP) is functionally the same as tabular DP. The recursive structure helps you derive the DP.

Follow-Up Problems to Push Deeper

#315 Count of Smaller Numbers After Self (Hard)

Modified merge sort — count inversions in the merge step. Shows how to augment D&C with extra tracking.

#493 Reverse Pairs (Hard)

Same merge sort trick but pairs where nums[i] > 2×nums[j]. Demonstrates the D&C augmentation pattern.

#4 Median of Two Sorted Arrays (Hard)

Binary search on partition — a D&C on the virtual merged array without constructing it. O(log(min(m,n))).

🎓 Phase 3 Complete!

You've mastered 7 core algorithms in C++: Sorting, Binary Search, Recursion, DP, Greedy, Backtracking, and Divide & Conquer. Now advance to Phase 4: Advanced Techniques used in Hard problems.