Divide & Conquer

Step 19 in the DSA path · 1 concepts · 5 problems

0 / 6 complete

📘 Learn Divide & Conquer from zero

Divide & Conquer solves a problem by splitting it into smaller independent subproblems of the same shape, solving each recursively, then combining their answers into the full answer. The recurrence is T(n) = 2·T(n/2) + (combine cost). Trigger: reach for it when an answer over a range can be assembled from answers over its two halves — and the combine step is cheaper than re-solving from scratch. Here we find the Majority Element (the value appearing more than ⌊n/2⌋ times) of [2,2,1,1,1,2,2]. Key insight: if a value is the global majority, it must be the majority of at least one half — so each recursion returns its half's candidate, and the parent only has to count two candidates over its own range to decide the winner.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Divide the whole range

index :  0  1  2  3  4  5  6
value : [2, 2, 1, 1, 1, 2, 2]
         lo=0          hi=6
         mid = (0+6)/2 = 3
         left  = [0..3]   right = [4..6]
         |<----------->| |<------->|
          2  2  1  1      1  2  2

We split range [0,6] at mid=3 into [0,3] and [4,6]. This is safe because the global majority (needs >3 occurrences) must dominate at least one of the two halves — by pigeonhole it cannot be a minority in both. So solving each half independently loses no candidate.

Step 2 — Recurse to the base case

Keep halving until lo == hi (a single element).
mid([0,3])=1, mid([4,6])=5:

[0,3] -> [0,1] -> [0,0]=2  [1,1]=2
      -> [2,3] -> [2,2]=1  [3,3]=1
[4,6] -> [4,5] -> [4,4]=1  [5,5]=2
      -> [6,6]=2

Base case:  [i,i]  ==>  return value[i]
            ^ a single element is trivially
              its own majority

The base case is a range of length 1: that lone element is by definition the majority of itself, so we return it directly. This terminates the recursion and is safe because there is no smaller subproblem to combine.

Step 3 — Combine [0,1] and [2,3]

Combine the two innermost left pairs:

[0,1]: L=2, R=2  -> agree, candidate 2
[2,3]: L=1, R=1  -> agree, candidate 1

No recount needed when a pair agrees;
candidates bubble up: left half so far
  [0,1] -> 2
  [2,3] -> 1

When the two child candidates agree (2 & 2, or 1 & 1), the answer is obviously that value. We pass 2 up from [0,1] and 1 up from [2,3]. Safe because a unanimous pair cannot have any other majority.

Step 4 — Combine into left half [0,3]

Range [0,3] = [2, 2, 1, 1]
leftCand = 2 (from [0,1])
rightCand = 1 (from [2,3])

Count each candidate over the FULL range [0,3]:
  value : [2, 2, 1, 1]
   ==2?    Y  Y  .  .   -> count(2) = 2
   ==1?    .  .  Y  Y   -> count(1) = 2

tie -> rule: leftCand wins  => 2

The children disagree, so we count both candidates across the parent's own range [0,3]. Both score 2; we break ties toward the left candidate, returning 2. Safe because the true majority of [0,3] must be one of the two halves' candidates, so we never miss it — we only have to decide between the two.

Step 5 — Combine into right half [4,6]

[4,5] = [1, 2]: L=1 (from [4,4]), R=2 (from [5,5])
   count over [4,5]:  ==1? Y . =1   ==2? . Y =1
   tie -> leftCand wins  => 1

Range [4,6] = [1, 2, 2]
leftCand = 1 (from [4,5])
rightCand = 2 (from [6,6])

Count over full range [4,6]:
  value : [1, 2, 2]
   ==1?    Y  .  .  -> count(1) = 1
   ==2?    .  Y  Y  -> count(2) = 2

2 > 1  => winner = 2

Symmetrically on the right: [4,5]=[1,2] ties (each count 1) and yields 1 by the left-wins rule, then [4,6] counts candidates 1 (=1) vs 2 (=2) over its range and returns 2. Safe for the same reason — the parent re-counts over its range, so a candidate that was weak in a sub-range can still win if it is strong overall.

Step 6 — Final combine at the root [0,6]

Root range [0,6] = [2, 2, 1, 1, 1, 2, 2]
leftCand  = 2 (from [0,3])
rightCand = 2 (from [4,6])

Both candidates are 2 -> agree, no recount
needed; but a count confirms the threshold.
Count 2 over [0,6]:
  value : [2, 2, 1, 1, 1, 2, 2]
   ==2?    Y  Y  .  .  .  Y  Y  -> count(2)=4

 n = 7,  floor(n/2) = 3
 4 > 3  ==>  ANSWER = 2

At the root both halves voted 2, so they agree; a single count confirms 2 appears 4 times > ⌊7/2⌋=3. Final answer: 2. The combine is safe and complete: the global majority had to surface as a candidate from at least one half, and the full-range count is the authoritative confirmation.

Step 7 — Why it works: cost & correctness

Recursion tree (each disagreeing node re-counts):

              [0,6]  O(7)
             /     \
        [0,3]O(4)   [4,6]O(3)
        /   \        /   \
    [0,1] [2,3]   [4,5]  [6,6]
     ...   ...     ...

Work per level = O(n)  (counts cover
  disjoint ranges summing to n)
Levels = log n

 T(n) = 2T(n/2) + O(n)  =>  O(n log n) time
 Recursion stack depth   =>  O(log n) space

By the Master Theorem, T(n)=2T(n/2)+O(n) resolves to O(n log n) time, O(log n) stack space. It is correct because of the dividing invariant proven at each step: the majority of a range is always the majority of one of its halves, so propagating two candidates upward and re-counting can never discard the true winner. (Boyer–Moore voting beats this at O(n)/O(1), but D&C is the textbook way to see the divide-combine structure.)

🎯 Guided practice

Easy — Majority Element. Given an array where one element appears more than n/2 times, find it. D&C reasoning: the global majority must be the majority of at least one half (pigeonhole — if it dominated neither half, its total couldn't exceed n/2). So: Divide at mid; Conquer by recursively finding the majority candidate of [lo, mid] and of [mid+1, hi]; base case lo == hi returns that single element. Combine: if both halves agree, return that value; otherwise count how many times each candidate actually appears across the full [lo, hi] range and return whichever wins.
Trace [2, 2, 1, 1, 1, 2, 2] (n=7, so majority needs > 3.5 occurrences; 2 appears 4 times): whenever the two halves return different candidates you re-count both over the current range, and the global majority 2 wins every disagreement as the ranges grow. Recurrence T(n)=2T(n/2)+O(n) → O(n log n), O(log n) stack. (Note: Boyer-Moore voting solves this in O(n) time / O(1) space — interviewers want you to produce the D&C solution and recognize that a linear scan beats it here, exactly the "when NOT to use" lesson.)
Medium — Sort List (sort a singly linked list in O(n log n)). Quicksort and heapsort want random access; a linked list has none, so merge sort is the natural fit. Pattern: Divide — find the middle with the slow/fast pointer trick (init slow=head, fast=head.next; slow advances one node, fast two; when fast reaches the end, slow sits at the first half's last node), then sever into two halves. Conquer — recursively sort each half; base case: a list of 0 or 1 nodes is already sorted, return it. Combine — merge the two sorted halves with a dummy-head pointer, repeatedly splicing whichever current node is smaller.
Trace 4 → 2 → 1 → 3: split into 4 → 2 and 1 → 3; each splits to singletons; merging yields 2 → 4 and 1 → 3; the final merge weaves them into 1 → 2 → 3 → 4. Time T(n)=2T(n/2)+O(n)=O(n log n); space is O(log n) for the recursion stack — no auxiliary array, unlike array merge sort, which is the advantage interviewers probe. Watch the classic pitfall: seeding fast=head.next (one node ahead) ensures a 2-node list splits 1-and-1; seeding fast=head leaves the whole list in one half and recurses forever.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic

○Introduction to Divide and Conquer Algorithm
○easy Longest Nice Substring
○easy Majority Element
○medium Sort List
○medium Maximum Binary Tree
○medium Beautiful Array