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

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard

What are the three steps of a Divide and Conquer algorithm, and when should you reach for the pattern?

tap to reveal →

Divide (break the problem into smaller subproblems of the same shape until they're trivial), Conquer (solve each subproblem recursively), and Combine (merge the subproblem solutions into the full answer). 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.

💡 DCC: Divide, Conquer, Combine.

Flashcard

What recurrence describes a balanced two-way Divide and Conquer like merge sort, and what does it resolve to?

tap to reveal →

T(n) = 2·T(n/2) + (combine cost). With an O(n) combine step it resolves to O(n log n) time by the Master Theorem; the recursion stack adds O(log n) space (array merge sort also uses O(n) auxiliary space for its temporary arrays).

💡 Two halves + linear merge = n log n.

Flashcard

In the Divide and Conquer Majority Element solution, what is the key invariant and how does the combine step work?

tap to reveal →

Invariant: the majority of a range must be the majority of at least one of its two halves (pigeonhole). Base case: a single element is its own majority. Combine: if both halves return the same candidate, return it; otherwise count both candidates over the full current range and return whichever appears more.

💡 Majority of the whole must dominate a half.

Flashcard

How does merge sort sort a singly linked list (Sort List), and why is merge sort the natural choice?

tap to reveal →

Find the middle with slow/fast pointers, split into two halves, recursively sort each (base case: 0 or 1 nodes), then merge the two sorted halves using a dummy node, splicing the smaller current node each time. Merge sort fits because a linked list has no random access (unlike quicksort/heapsort) and it needs no auxiliary array — O(n log n) time, O(log n) stack space.

💡 Slow/fast split, dummy-node merge.

Flashcard

How does Divide and Conquer construct a Maximum Binary Tree from a unique-integer array?

tap to reveal →

For the current subarray, find the index of the maximum value and make it the root; recursively build the left subtree from elements left of the max and the right subtree from elements right of the max. Base case: an empty subarray (start == end) returns null.

💡 Max is the root; recurse left and right of it.

Flashcard

How does the Beautiful Array Divide and Conquer construction work, and why does it satisfy the condition?

tap to reveal →

Recursively build a beautiful array of size (N+1)/2 for odds and N/2 for evens (base case N==1 returns [1]); transform the odd array by element*2-1 and the even array by element*2, then concatenate. It works because an odd + an even is always odd, so 2*A[j] (even) can never equal A[i]+A[k] when one side is all odds and the other all evens. Runs in O(N log N) time and space.

💡 Odds left, evens right — odd+even is never 2x.

Q1. Which signal best indicates a problem is a good fit for Divide and Conquer?

Q2. In the Majority Element D&C solution, when the two halves return DIFFERENT candidates, how is the winner chosen for the current segment?

Q3. Why is merge sort preferred over quicksort or heapsort for sorting a singly linked list?

Q4. For Beautiful Array, what transformation is applied when merging the recursively built odd and even subarrays?

Q5. Building a Maximum Binary Tree from nums = [4, 3, 1, 7, 0, 5], what is the root, and from which subarrays are its children built?