Divide and Conquer Template
Extract the three-step template (divide, conquer, combine) from merge sort and apply it systematically to new problem shapes.
Divide and Conquer Template is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What is Divide and Conquer?
Divide and Conquer (D&C) solves a problem by breaking it into independent sub-problems of the same type, solving each recursively, and combining their solutions. The key word is independent — sub-problems do not share state (unlike DP where they overlap). Classic examples: merge sort, binary search, quick sort, closest pair of points, and fast matrix multiplication. D&C typically achieves O(n log n) time through the three-step template.
# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP: sub-problems OVERLAP (same sub-problem solved multiple times)
# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing
# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n) [merge sort]
# T(n) = T(n/2) + O(1) → O(log n) [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]The Three-Step Template
Every D&C algorithm follows three steps: (1) Divide — split the problem into two (or more) smaller sub-problems, typically at the midpoint. (2) Conquer — recursively solve each sub-problem. Define a base case to stop recursion (usually n ≤ 1). (3) Combine — merge or combine the sub-problem solutions into the overall solution. The creativity lies entirely in the Combine step; Divide is usually just splitting at the midpoint.
def divide_and_conquer(arr, lo, hi):
# BASE CASE: trivial sub-problem
if lo >= hi:
return base_case_result(arr, lo, hi)
# DIVIDE: split at midpoint
mid = (lo + hi) // 2
# CONQUER: solve sub-problems recursively
left_result = divide_and_conquer(arr, lo, mid)
right_result = divide_and_conquer(arr, mid + 1, hi)
# COMBINE: merge results
return combine(left_result, right_result, arr, lo, mid, hi)
def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)Merge Sort as the Canonical Example
Merge sort perfectly illustrates D&C: Divide the array at the midpoint. Conquer by recursively sorting each half. Combine by merging the two sorted halves in O(n). The merge step is where all the work happens. Recurrence: T(n) = 2T(n/2) + O(n). By the Master Theorem case 2: T(n) = O(n log n). This is the most important D&C recurrence to memorise.
def merge_sort(arr):
# BASE CASE
if len(arr) <= 1:
return arr
# DIVIDE
mid = len(arr) // 2
# CONQUER
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# COMBINE
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]
print(merge_sort([5, 3, 8, 1, 9, 2])) # [1,2,3,5,8,9]Master Theorem Quick Reference
The Master Theorem solves recurrences of the form T(n) = aT(n/b) + f(n): Case 1: f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a)). Case 2: f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n). Case 3: f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n)). Merge sort: a=2, b=2, f(n)=O(n), n^log_2(2)=n → Case 2 → O(n log n).
# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n) → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1) → a=2,b=2,f=1,n^1=n >> 1 → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2) → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1) → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree
recurrences = [
('Merge sort: 2T(n/2)+n', 'O(n log n)'),
('Binary search: T(n/2)+1', 'O(log n)'),
('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)Maximum Subarray: D&C Approach
The D&C approach to maximum subarray: the answer is either entirely in the left half, entirely in the right half, or crosses the midpoint. For the crossing case, expand left from mid and right from mid+1, taking the maximum sum in each direction, then combine. This O(n log n) D&C is slower than Kadane's O(n) but demonstrates the template beautifully and is a common interview question about D&C.
def max_subarray_dc(nums, lo=None, hi=None):
if lo is None: lo, hi = 0, len(nums) - 1
if lo == hi: return nums[lo]
mid = (lo + hi) // 2
# Conquer
left_max = max_subarray_dc(nums, lo, mid)
right_max = max_subarray_dc(nums, mid + 1, hi)
# Cross-midpoint sum
left_sum = curr = 0
for i in range(mid, lo - 1, -1):
curr += nums[i]
left_sum = max(left_sum, curr)
right_sum = curr = 0
for i in range(mid + 1, hi + 1):
curr += nums[i]
right_sum = max(right_sum, curr)
cross_max = left_sum + right_sum
return max(left_max, right_max, cross_max)
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums)) # 6Power Function: Fast Exponentiation
Fast Power (LeetCode 50): compute x^n in O(log n) using D&C. If n is even: x^n = (x^(n/2))^2. If n is odd: x^n = x × x^(n-1). Handle negative n with x^(-n) = 1/x^n. Each recursive call halves n, so the depth is O(log n). This is a clean example where the Combine step is just multiplication — trivial but effective.
def my_pow(x, n):
if n < 0:
return 1 / my_pow(x, -n)
# BASE CASE
if n == 0: return 1
# DIVIDE and CONQUER
half = my_pow(x, n // 2)
if n % 2 == 0:
return half * half # even: x^n = (x^(n/2))^2
else:
return x * half * half # odd: x^n = x * (x^(n/2))^2
print(my_pow(2, 10)) # 1024
print(my_pow(2, -2)) # 0.25
print(my_pow(3, 5)) # 243
print(my_pow(0, 0)) # 1Sorted Array to BST
Convert Sorted Array to BST (LeetCode 108) uses D&C: take the midpoint as the root (ensuring height balance), recursively build the left subtree from the left half and right subtree from the right half. This produces a height-balanced BST with minimum height O(log n). The D&C structure mirrors binary search — each level of recursion assigns the midpoint as the root of the current sub-range.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sorted_array_to_bst(nums):
def helper(lo, hi):
if lo > hi: return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid]) # DIVIDE at midpoint
node.left = helper(lo, mid - 1) # CONQUER left
node.right = helper(mid + 1, hi) # CONQUER right
# COMBINE: already done by assignment
return node
return helper(0, len(nums) - 1)
def inorder(node):
if not node: return []
return inorder(node.left) + [node.val] + inorder(node.right)
root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root)) # [-10,-3,0,5,9] (sorted, proving BST property)When D&C is Not the Best Choice
D&C has overhead: function call stack depth, array slicing (if not using indices), and the combine step. It is optimal when the combine step is O(n) or cheaper. When sub-problems overlap, D&C recomputes solutions wastefully — DP is needed. When the combine step dominates (e.g., O(n²)), D&C doesn't improve over naive approaches. Know when to choose: D&C for independent sub-problems, DP for overlapping sub-problems.
# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead
def fib_dc(n):
if n <= 1: return n
return fib_dc(n-1) + fib_dc(n-2) # O(2^n)!
def fib_dp(n):
a, b = 0, 1
for _ in range(n): a, b = b, a+b
return a # O(n)
print(fib_dp(30)) # fast
# fib_dc(40) would take seconds — do not run large values!D&C for Binary Search on Sorted Matrix
Search in a 2D matrix (LeetCode 240) where each row and column is sorted can be solved with D&C: start from the top-right corner. If current > target, move left (eliminates column). If current < target, move down (eliminates row). If equal, found it. This O(m+n) algorithm is technically not recursive D&C but shares the key idea: eliminate half the search space at each step.
def search_matrix(matrix, target):
if not matrix: return False
m, n = len(matrix), len(matrix[0])
row, col = 0, n - 1 # start top-right
while row < m and col >= 0:
val = matrix[row][col]
if val == target:
return True
elif val > target:
col -= 1 # eliminate this column
else:
row += 1 # eliminate this row
return False
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5)) # True
print(search_matrix(matrix, 20)) # FalseRecursion Tree Analysis
For D&C recurrences not fitting the Master Theorem, use the recursion tree method. Draw each level of recursive calls and sum the work per level. Merge sort: at level k there are 2^k sub-problems of size n/2^k. Work per level = 2^k × O(n/2^k) = O(n). Total levels = log n. Total work = O(n log n). This visual method works for any recurrence and builds intuition for why D&C usually hits O(n log n).
# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)
import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')Interview Communication for D&C
When presenting a D&C solution in an interview: (1) State the three steps explicitly: 'I will divide at the midpoint, recursively solve each half, then combine by merging.' (2) Identify the base case clearly. (3) Derive the recurrence: T(n) = 2T(n/2) + O(n). (4) Apply Master Theorem or recursion tree to derive O(n log n). (5) Mention when D&C is better or worse than alternatives (DP for overlapping sub-problems, Kadane's for max subarray).
# D&C interview template to memorize:
def dc_template(problem, lo, hi):
# 1. BASE CASE (state it first)
if lo == hi: return solve_base(problem, lo)
# 2. DIVIDE
mid = (lo + hi) // 2
# 3. CONQUER
left = dc_template(problem, lo, mid)
right = dc_template(problem, mid + 1, hi)
# 4. COMBINE (this is where the algorithm-specific logic goes)
return combine_results(left, right, problem, lo, mid, hi)
def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)
print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Divide and Conquer follows the template: base case → divide at midpoint → conquer recursively → combine, T(n) = 2T(n/2) + O(n) gives O(n log n) by Master Theorem Case 2, and D&C is optimal for independent sub-problems while DP is needed when sub-problems overlap. Next up we apply D&C to count inversions in an array using a modified merge sort.
Frequently asked questions
Is the “Divide and Conquer Template” lesson free?
Yes — the full text of “Divide and Conquer Template” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Divide and Conquer Template”?
Extract the three-step template (divide, conquer, combine) from merge sort and apply it systematically to new problem shapes. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Divide and Conquer Template” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Divide and Conquer Template
- Count Inversions Using Modified Merge Sort
- Majority Element: Boyer-Moore Voting
- Median of Two Sorted Arrays