Skip to content

11. Divide and Conquer#

Theory#

Divide and conquer solves a problem by:

  1. Base case — return directly when the subproblem is small enough.
  2. Divide — split the input into smaller independent (or nearly independent) subproblems.
  3. Conquer — solve each subproblem recursively.
  4. Combine — merge subproblem results into the final answer.

Classic recurrence: T(n) = a·T(n/b) + f(n). Merge sort is the template: split array in half, sort each half, merge.

def solve(lo, hi):
    if lo >= hi:          # base case
        return base_value
    mid = (lo + hi) // 2  # divide
    left = solve(lo, mid)
    right = solve(mid + 1, hi)
    return combine(left, right)

When to use: sorted output from unsorted input, counting cross-boundary events (inversions), geometric problems with plane sweep strips, fast polynomial/matrix multiply, or tree queries that split left/right subtrees.

Not D&C: binary search on an answer value (feasibility predicate), pure tabulation DP, backtracking enumeration, or preprocessing tricks like binary lifting — those belong in Binary Search, Dynamic Programming, Backtracking, or Tree docs.

See also: Recursion, Searching.

Problems at a glance#

LC Problem
33 Search in Rotated Sorted Array ↗
236 Lowest Common Ancestor in a Binary Tree ↗
222 Count Nodes in Complete Binary Tree ↗
509 Fibonacci Number with Memoization ↗
96 Unique Binary Search Trees ↗

1. Classic Divide and Conquer (Recursive Decomposition)#

Problems that split input in half (or into fixed parts), recurse, then combine.

Problem 1: Merge Sort (GeeksforGeeks)#

Problem Statement

Given an array of integers, sort it in ascending order using merge sort.

Example 1:

Input: arr = [38, 27, 43, 3, 9, 82, 10]
Output: [3, 9, 10, 27, 38, 43, 82]

Example 2:

Input: arr = [5, 1, 4, 2, 8]
Output: [1, 2, 4, 5, 8]

Constraints:

  • 1 <= arr.length <= 10^5
  • -10^9 <= arr[i] <= 10^9
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left: list[int], right: list[int]) -> list[int]:
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged
Explanation:

  1. Base case: arrays of length 0 or 1 are already sorted — return as-is.
  2. Divide: split arr at mid into left and right halves.
  3. Conquer: recursively sort each half.
  4. Combine: two-pointer merge of sorted halves into one sorted array.

Time: O(n log n)  |  Space: O(n) for merge buffers (O(log n) recursion stack).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def merge_sort_bottom_up(arr: list[int]) -> list[int]:
    n = len(arr)
    if n <= 1:
        return arr[:]
    a = arr[:]
    size = 1
    while size < n:
        for lo in range(0, n, 2 * size):
            mid = min(lo + size, n)
            hi = min(lo + 2 * size, n)
            temp, i, j = [], lo, mid
            while i < mid and j < hi:
                if a[i] <= a[j]:
                    temp.append(a[i])
                    i += 1
                else:
                    temp.append(a[j])
                    j += 1
            temp.extend(a[i:mid])
            temp.extend(a[j:hi])
            a[lo:hi] = temp
        size *= 2
    return a
Explanation:

  1. Base case: length ≤ 1 — nothing to do.
  2. Divide: process subarrays of doubling width size (1, 2, 4, …) instead of recursion.
  3. Conquer: each pass merges adjacent sorted blocks of length size.
  4. Combine: in-place write-back of merged block into a[lo:hi].

Time: O(n log n)  |  Space: O(n) temporary buffer per merge.

Problem 2: Quick Sort (GeeksforGeeks)#

Problem Statement

Given an array of integers, sort it in ascending order using quick sort.

Example 1:

Input: arr = [10, 7, 8, 9, 1, 5]
Output: [1, 5, 7, 8, 9, 10]

Example 2:

Input: arr = [4, 2, 6, 1, 3]
Output: [1, 2, 3, 4, 6]

Constraints:

  • 1 <= arr.length <= 10^5
  • -10^9 <= arr[i] <= 10^9
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import random

def quick_sort(arr: list[int], lo: int = 0, hi: int | None = None) -> list[int]:
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return arr

    pivot_idx = random.randint(lo, hi)
    arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
    p = partition_lomuto(arr, lo, hi)
    quick_sort(arr, lo, p - 1)
    quick_sort(arr, p + 1, hi)
    return arr

def partition_lomuto(arr: list[int], lo: int, hi: int) -> int:
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i
Explanation:

  1. Base case: subarray of length 0 or 1 (lo >= hi) is sorted.
  2. Divide: pick a pivot (randomized here) and partition so elements ≤ pivot are left, greater are right.
  3. Conquer: recursively sort [lo, p-1] and [p+1, hi].
  4. Combine: nothing — elements are placed in final position by partitioning.

Time: O(n log n) average, O(n²) worst  |  Space: O(log n) stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def quick_sort_hoare(arr: list[int], lo: int = 0, hi: int | None = None) -> list[int]:
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return arr

    p = partition_hoare(arr, lo, hi)
    quick_sort_hoare(arr, lo, p)
    quick_sort_hoare(arr, p + 1, hi)
    return arr

def partition_hoare(arr: list[int], lo: int, hi: int) -> int:
    pivot = arr[(lo + hi) // 2]
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]
Explanation:

  1. Base case: lo >= hi — subarray has at most one element.
  2. Divide: Hoare partition scans from both ends, swapping out-of-place pairs until pointers cross.
  3. Conquer: recurse on [lo, p] and [p+1, hi] (pivot may not be at final index).
  4. Combine: implicit — in-place swaps place elements correctly across recursive calls.

Time: O(n log n) average  |  Space: O(log n) stack. Fewer swaps than Lomuto on average.

Problem 3: Maximum Subarray Sum — Divide and Conquer (GeeksforGeeks)#

Problem Statement

Given an integer array nums, find the contiguous subarray with the largest sum and return that sum.

Example 1:

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: subarray [4, -1, 2, 1] has sum 6.

Example 2:

Input: nums = [1]
Output: 1

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from math import inf

def max_subarray_sum(nums: list[int]) -> int:
    def solve(lo: int, hi: int) -> int:
        if lo == hi:
            return nums[lo]

        mid = (lo + hi) // 2
        left_max = solve(lo, mid)
        right_max = solve(mid + 1, hi)

        left_cross = -inf
        s = 0
        for i in range(mid, lo - 1, -1):
            s += nums[i]
            left_cross = max(left_cross, s)

        right_cross = -inf
        s = 0
        for i in range(mid + 1, hi + 1):
            s += nums[i]
            right_cross = max(right_cross, s)

        cross_max = left_cross + right_cross
        return max(left_max, right_max, cross_max)

    return solve(0, len(nums) - 1)
Explanation:

  1. Base case: single element nums[lo] is the best subarray in that range.
  2. Divide: split at mid into left and right halves.
  3. Conquer: recursively find best subarray fully in left half and fully in right half.
  4. Combine: compute crossing sum — best suffix of left plus best prefix of right; take max of all three.

Time: O(n log n)  |  Space: O(log n) stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from math import inf

def max_subarray_sum_iterative(nums: list[int]) -> int:
    stack = [(0, len(nums) - 1)]
    best = -inf

    while stack:
        lo, hi = stack.pop()
        if lo == hi:
            best = max(best, nums[lo])
            continue

        mid = (lo + hi) // 2
        stack.append((lo, mid))
        stack.append((mid + 1, hi))

        left_cross = -inf
        s = 0
        for i in range(mid, lo - 1, -1):
            s += nums[i]
            left_cross = max(left_cross, s)

        right_cross = -inf
        s = 0
        for i in range(mid + 1, hi + 1):
            s += nums[i]
            right_cross = max(right_cross, s)

        best = max(best, left_cross + right_cross)

    return best
Explanation:

  1. Base case: single-element ranges update best directly.
  2. Divide: explicit stack pushes left and right sub-ranges (avoids recursion depth).
  3. Conquer: each popped range computes its crossing contribution.
  4. Combine: track global maximum across all crossing sums and base cases.

Time: O(n log n)  |  Space: O(n) stack frames in worst case.

Problem 4: Count Inversions in an Array (GeeksforGeeks)#

Problem Statement

Given an array arr[], count the number of inversion pairs: indices i < j where arr[i] > arr[j].

Example 1:

Input: arr = [2, 4, 1, 3, 5]
Output: 3
Explanation: pairs (2,1), (4,1), (4,3).

Example 2:

Input: arr = [5, 4, 3, 2, 1]
Output: 10

Constraints:

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^9
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def count_inversions(arr: list[int]) -> int:
    a = arr[:]
    inv = 0

    def merge_sort(lo: int, hi: int) -> None:
        nonlocal inv
        if lo >= hi:
            return
        mid = (lo + hi) // 2
        merge_sort(lo, mid)
        merge_sort(mid + 1, hi)

        temp, i, j = [], lo, mid + 1
        while i <= mid and j <= hi:
            if a[i] <= a[j]:
                temp.append(a[i])
                i += 1
            else:
                temp.append(a[j])
                inv += mid - i + 1  # all remaining left elements form inversions
                j += 1
        temp.extend(a[i:mid + 1])
        temp.extend(a[j:hi + 1])
        a[lo:hi + 1] = temp

    merge_sort(0, len(a) - 1)
    return inv
Explanation:

  1. Base case: single-element range has 0 inversions.
  2. Divide: split array at mid.
  3. Conquer: count inversions in left half and right half recursively.
  4. Combine: during merge, when a[j] < a[i], all elements a[i..mid] invert with a[j] — add mid - i + 1.

Time: O(n log n)  |  Space: O(n).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def count_inversions_copy(arr: list[int]) -> int:
    def sort_count(a: list[int]) -> tuple[list[int], int]:
        if len(a) <= 1:
            return a, 0

        mid = len(a) // 2
        left, inv_l = sort_count(a[:mid])
        right, inv_r = sort_count(a[mid:])
        merged, inv_m = [], 0
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                inv_m += len(left) - i
                j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged, inv_l + inv_r + inv_m

    _, total = sort_count(arr)
    return total
Explanation:

  1. Base case: length ≤ 1 returns sorted copy with 0 inversions.
  2. Divide: split into left and right subarrays.
  3. Conquer: recursively sort-count each half.
  4. Combine: merge sorted halves, counting cross-half inversions when right element is smaller.

Time: O(n log n)  |  Space: O(n) per recursion level (functional style).

Problem 5: Closest Pair of Points (GeeksforGeeks)#

Problem Statement

Given n points in a 2D plane, find the minimum Euclidean distance between any two distinct points.

Example 1:

Input: points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
Output: 1.41421 (distance between (2,3) and (3,4))

Example 2:

Input: points = [(0, 0), (1, 1)]
Output: 1.41421

Constraints:

  • 2 <= n <= 2×10^5
  • Coordinates fit in 32-bit integers
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from math import sqrt, inf

def closest_pair(points: list[tuple[int, int]]) -> float:
    pts = sorted(points)

    def dist(a, b):
        return sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

    def brute(p):
        best = inf
        for i in range(len(p)):
            for j in range(i + 1, len(p)):
                best = min(best, dist(p[i], p[j]))
        return best

    def solve(px):
        n = len(px)
        if n <= 3:
            return brute(px)

        mid = n // 2
        mid_x = px[mid][0]
        dl = solve(px[:mid])
        dr = solve(px[mid:])
        d = min(dl, dr)

        strip = [p for p in px if abs(p[0] - mid_x) < d]
        strip.sort(key=lambda p: p[1])
        for i in range(len(strip)):
            j = i + 1
            while j < len(strip) and (strip[j][1] - strip[i][1]) < d:
                d = min(d, dist(strip[i], strip[j]))
                j += 1
        return d

    return solve(pts)
Explanation:

  1. Base case: ≤ 3 points — brute-force all pairs.
  2. Divide: sort by x, split into left and right halves at mid.
  3. Conquer: recursively find closest distance dl and dr in each half.
  4. Combine: check strip within d of midline; only compare points within d vertically (at most 7 neighbors per point).

Time: O(n log² n) naive strip sort; O(n log n) with careful merge-by-y  |  Space: O(n).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from math import sqrt, inf

def closest_pair_optimized(points: list[tuple[int, int]]) -> float:
    px = sorted(points)
    py = sorted(points, key=lambda p: p[1])

    def dist(a, b):
        return sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

    def brute(pxs, pys):
        return min(dist(pxs[i], pxs[j])
                   for i in range(len(pxs))
                   for j in range(i + 1, len(pxs)))

    def solve(pxs, pys):
        n = len(pxs)
        if n <= 3:
            return brute(pxs, pys)

        mid = n // 2
        mid_x = pxs[mid][0]
        pys_l = [p for p in pys if p[0] <= mid_x]
        pys_r = [p for p in pys if p[0] > mid_x]

        dl = solve(pxs[:mid], pys_l)
        dr = solve(pxs[mid:], pys_r)
        d = min(dl, dr)

        strip = [p for p in pys if abs(p[0] - mid_x) < d]
        for i in range(len(strip)):
            j = i + 1
            while j < len(strip) and strip[j][1] - strip[i][1] < d:
                d = min(d, dist(strip[i], strip[j]))
                j += 1
        return d

    return solve(px, py)
Explanation:

  1. Base case: ≤ 3 points — brute force.
  2. Divide: split x-sorted list; partition y-sorted list into left/right by x-coordinate.
  3. Conquer: recurse on both halves with pre-partitioned y-lists.
  4. Combine: scan y-ordered strip near midline — avoids re-sorting strip each level.

Time: O(n log n)  |  Space: O(n).

Problem 6: Integer Multiplication — Karatsuba (GeeksforGeeks)#

Problem Statement

Multiply two large non-negative integers faster than the O(n²) schoolbook method using Karatsuba divide and conquer.

Example 1:

Input: x = 1234, y = 5678
Output: 7006652

Example 2:

Input: x = 999, y = 99
Output: 98901

Constraints:

  • 0 <= x, y <= 10^1000 (big integers)
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def karatsuba(x: int, y: int) -> int:
    if x < 10 or y < 10:
        return x * y

    n = max(len(str(x)), len(str(y)))
    m = n // 2
    power = 10 ** m

    a, b = divmod(x, power)
    c, d = divmod(y, power)

    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    ad_bc = karatsuba(a + b, c + d) - ac - bd

    return ac * (10 ** (2 * m)) + ad_bc * power + bd
Explanation:

  1. Base case: single-digit numbers — multiply directly.
  2. Divide: split each number into high/low halves a,b and c,d at 10^m.
  3. Conquer: three recursive multiplies: ac, bd, and (a+b)(c+d).
  4. Combine: ac·10^(2m) + (ad+bc)·10^m + bd using ad+bc = (a+b)(c+d) - ac - bd.

Time: O(n^log₂3) ≈ O(n^1.585)  |  Space: O(log n) stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
THRESHOLD = 32

def karatsuba_hybrid(x: int, y: int) -> int:
    if x < THRESHOLD or y < THRESHOLD:
        return x * y

    n = max(len(str(x)), len(str(y)))
    m = n // 2
    power = 10 ** m

    a, b = divmod(x, power)
    c, d = divmod(y, power)

    ac = karatsuba_hybrid(a, c)
    bd = karatsuba_hybrid(b, d)
    ad_bc = karatsuba_hybrid(a + b, c + d) - ac - bd

    return ac * (10 ** (2 * m)) + ad_bc * power + bd
Explanation:

  1. Base case: numbers below THRESHOLD use hardware multiply (constant time).
  2. Divide: same half-split as classic Karatsuba.
  3. Conquer: recurse until subproblems are small.
  4. Combine: identical formula — hybrid reduces overhead for small subproblems.

Time: O(n^log₂3) asymptotically  |  Space: O(log n).

Problem 7: Search in Rotated Sorted Array (Leetcode:33)#

Problem Statement

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -10^4 <= target <= 10^4
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        def solve(lo: int, hi: int) -> int:
            if lo > hi:
                return -1
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid

            if nums[lo] <= nums[mid]:          # left half sorted
                if nums[lo] <= target < nums[mid]:
                    return solve(lo, mid - 1)
                return solve(mid + 1, hi)
            else:                              # right half sorted
                if nums[mid] < target <= nums[hi]:
                    return solve(mid + 1, hi)
                return solve(lo, mid - 1)

        return solve(0, len(nums) - 1)
Explanation:

  1. Base case: empty range (lo > hi) → target not found.
  2. Divide: pick mid, identify which half is sorted (no rotation pivot inside).
  3. Conquer: recurse only on the half that can contain target by range check.
  4. Combine: return result from the chosen half (or -1).

Time: O(log n)  |  Space: O(log n) stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid
            if nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1
Explanation:

  1. Base case: loop ends when lo > hi — return -1.
  2. Divide: compute mid, determine sorted half.
  3. Conquer: shrink search space to the viable half each iteration.
  4. Combine: direct return on match; otherwise implicit via narrowed bounds.

Time: O(log n)  |  Space: O(1).

2. Divide and Conquer on Data Structures#

Recursive decomposition on trees, arrays, or hierarchical structures.

Problem 1: Lowest Common Ancestor in a Binary Tree (Leetcode:236)#

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Example 1:


Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:


Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        def solve(node: TreeNode | None) -> TreeNode | None:
            if not node or node == p or node == q:
                return node

            left = solve(node.left)
            right = solve(node.right)

            if left and right:
                return node
            return left or right

        return solve(root)
Explanation:

  1. Base case: None → not found; if node is p or q, return it upward.
  2. Divide: recurse into left and right subtrees independently.
  3. Conquer: each subtree returns its first matching ancestor of p/q (or None).
  4. Combine: if both sides return non-null, current node is LCA; else bubble up the non-null side.

Time: O(n)  |  Space: O(h) recursion stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        parent = {root: None}
        stack, found = [root], set()

        while stack and not (p in found and q in found):
            node = stack.pop()
            if node.left:
                parent[node.left] = node
                stack.append(node.left)
            if node.right:
                parent[node.right] = node
                stack.append(node.right)
            if node == p or node == q:
                found.add(node)

        ancestors = set()
        while p:
            ancestors.add(p)
            p = parent[p]
        while q not in ancestors:
            q = parent[q]
        return q
Explanation:

  1. Base case: both p and q located in parent map.
  2. Divide: DFS stack explores left/right children, recording parent pointers.
  3. Conquer: mark when p or q is found.
  4. Combine: walk p ancestors; first ancestor shared with q's upward walk is LCA.

Time: O(n)  |  Space: O(n). Iterative alternative when recursion depth is a concern.

Problem 2: Count Nodes in Complete Binary Tree (Leetcode:222)#

Problem Statement

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:


Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [0, 5 * 10^4].
  • 0 <= Node.val <= 5 * 10^4
  • The tree is guaranteed to be complete.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def countNodes(self, root: TreeNode | None) -> int:
        def height(node: TreeNode | None) -> int:
            h = 0
            while node:
                h += 1
                node = node.left
            return h

        if not root:
            return 0

        left_h = height(root.left)
        right_h = height(root.right)

        if left_h == right_h:
            return (1 << left_h) + self.countNodes(root.right)
        return (1 << right_h) + self.countNodes(root.left)
Explanation:

  1. Base case: empty tree → 0 nodes.
  2. Divide: compare left-subtree height vs right-subtree height (via left-spine walks).
  3. Conquer: if equal, left subtree is a perfect tree of 2^left_h - 1 nodes — recurse only on right; else mirror on left.
  4. Combine: 2^h + 1 (root + perfect side) plus count from the recursive call.

Time: O(log² n)  |  Space: O(log n) stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def countNodes(self, root: TreeNode | None) -> int:
        if not root:
            return 0

        def height(node: TreeNode) -> int:
            h = 0
            while node:
                h += 1
                node = node.left
            return h

        def exists(idx: int, h: int, node: TreeNode) -> bool:
            lo, hi = 0, (1 << (h - 1)) - 1
            for _ in range(h - 1):
                mid = (lo + hi) // 2
                if idx <= mid:
                    node = node.left
                    hi = mid
                else:
                    node = node.right
                    lo = mid + 1
            return node is not None

        h = height(root)
        lo, hi = 0, (1 << (h - 1)) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if exists(mid, h, root):
                lo = mid + 1
            else:
                hi = mid - 1
        return ((1 << (h - 1)) - 1) + lo
Explanation:

  1. Base case: empty root → 0.
  2. Divide: compute tree height h; last level indices [0, 2^(h-1)-1] form a search space.
  3. Conquer: binary search for rightmost existing index using path-from-root checks.
  4. Combine: full levels (2^(h-1) - 1) plus lo nodes on the partial last level.

Time: O(log² n)  |  Space: O(1).

Problem 3: Segment Tree Construction (GeeksforGeeks)#

Problem Statement

Given an array arr[] of length n, build a segment tree that supports range-sum queries. Construct the tree recursively.

Example 1:

Input: arr = [1, 3, 5, 7, 9, 11]
Build tree → query sum(1, 3) = 3 + 5 + 7 = 15

Example 2:

Input: arr = [2, 4, 6]
query sum(0, 2) = 12

Constraints:

  • 1 <= n <= 10^5
  • -10^9 <= arr[i] <= 10^9
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class SegmentTree:
    def __init__(self, arr: list[int]):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self._build(arr, 0, 0, self.n - 1)

    def _build(self, arr: list[int], node: int, lo: int, hi: int) -> None:
        if lo == hi:
            self.tree[node] = arr[lo]
            return

        mid = (lo + hi) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2

        self._build(arr, left_child, lo, mid)
        self._build(arr, right_child, mid + 1, hi)
        self.tree[node] = self.tree[left_child] + self.tree[right_child]

    def query(self, ql: int, qr: int) -> int:
        return self._query(0, 0, self.n - 1, ql, qr)

    def _query(self, node: int, lo: int, hi: int, ql: int, qr: int) -> int:
        if qr < lo or hi < ql:
            return 0
        if ql <= lo and hi <= qr:
            return self.tree[node]
        mid = (lo + hi) // 2
        return (self._query(2 * node + 1, lo, mid, ql, qr) +
                self._query(2 * node + 2, mid + 1, hi, ql, qr))
Explanation:

  1. Base case: leaf node (lo == hi) stores arr[lo].
  2. Divide: split index range [lo, hi] at mid into left/right children.
  3. Conquer: recursively build child subtrees.
  4. Combine: internal node = sum of children's values. Query recursively merges overlapping ranges.

Time: O(n) build, O(log n) query  |  Space: O(4n).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class SegmentTreeIterative:
    def __init__(self, arr: list[int]):
        n = len(arr)
        size = 1
        while size < n:
            size <<= 1
        self.size = size
        self.tree = [0] * (2 * size)
        for i in range(n):
            self.tree[size + i] = arr[i]
        for i in range(size - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, l: int, r: int) -> int:
        l += self.size
        r += self.size
        res = 0
        while l <= r:
            if l % 2 == 1:
                res += self.tree[l]
                l += 1
            if r % 2 == 0:
                res += self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return res
Explanation:

  1. Base case: leaves at indices [size, size+n) hold raw array values.
  2. Divide: implicit — heap indices i have children 2i and 2i+1.
  3. Conquer: bottom-up loop from size-1 down to 1 fills parents.
  4. Combine: each parent = sum of two children; query walks up the tree merging partial nodes.

Time: O(n) build, O(log n) query  |  Space: O(2n).

3. Master Theorem / Recurrence Analysis#

Analyzing divide-and-conquer recurrences and advanced matrix/polynomial splits.

Problem 1: Analyze Merge Sort Time Complexity (Conceptual)#

Problem Statement

Derive the time complexity of merge sort using recurrence relations and the Master Theorem.

Example 1:

Input size n = 1024
Output: Θ(n log n) = Θ(1024 × 10) comparisons (approx.)

Example 2:

Recurrence T(n) = 2T(n/2) + Θ(n)
Output: T(n) = Θ(n log n)

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# Merge sort recurrence:
#   T(n) = 2·T(n/2) + Θ(n)   for n > 1
#   T(1) = Θ(1)              base case
#
# Recursion tree (height = log₂ n):
#   Level 0: 1 node,  cost n
#   Level 1: 2 nodes, cost n/2 each → total n
#   Level 2: 4 nodes, cost n/4 each → total n
#   ...
#   Level log₂ n: n nodes, cost 1 each → total n
#
# Total cost = n × (log₂ n + 1) = Θ(n log n)

def merge_sort_cost(n: int) -> float:
    import math
    if n <= 1:
        return 1
    return 2 * merge_sort_cost(n // 2) + n
Explanation:

  1. Base case: T(1) = Θ(1) — single element needs no merge work.
  2. Divide: one array → two halves of size n/2.
  3. Conquer: two recursive calls each costing T(n/2).
  4. Combine: merge step scans all n elements → Θ(n) per level; log n levels → Θ(n log n).

Time: analysis only  |  Space: O(log n) recursion depth.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# Master Theorem: T(n) = a·T(n/b) + f(n)
# Merge sort: a=2, b=2, f(n)=Θ(n)
#
# Compare f(n) with n^(log_b a) = n^(log_2 2) = n^1 = n
# f(n) = Θ(n) = Θ(n^(log_b a))  → Case 2
# Result: T(n) = Θ(n^(log_b a) · log n) = Θ(n log n)

def master_theorem_case(a: int, b: int, n: int) -> str:
    import math
    critical = n ** (math.log(a, b))
    return f"T(n) = Θ(n log n) when f(n)=Θ(n) and n^(log_{b} {a}) = n"
Explanation:

  1. Base case: Master Theorem applies when subproblems shrink uniformly (n/b).
  2. Divide: a = 2 subproblems of size n/2.
  3. Conquer: recursive cost 2·T(n/2).
  4. Combine: f(n) = Θ(n) matches n^(log_b a) exactly (Case 2) → multiply by extra log n factor.

Result: merge sort is Θ(n log n) time, Θ(n) auxiliary space for merging.

Problem 2: Solve Recurrence T(n) = 2T(n/2) + O(n) (Conceptual)#

Problem Statement

Solve the general divide-and-conquer recurrence T(n) = 2T(n/2) + O(n) that appears in merge sort, counting inversions, and many combine-linear algorithms.

Example 1:

T(n) = 2T(n/2) + n → T(n) = Θ(n log n)

Example 2:

T(n) = 2T(n/2) + n log n → T(n) = Θ(n log² n) (Case 2 with polylog factor)

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# Unroll k times:
# T(n) = 2^k · T(n/2^k) + k·n
# Stop when n/2^k = 1  →  k = log₂ n
# T(n) = n·T(1) + n·log₂ n = Θ(n log n)

def unrolled_cost(n: int, levels: int | None = None) -> int:
    import math
    if levels is None:
        levels = int(math.log2(n))
    if n <= 1 or levels == 0:
        return n
    return 2 * unrolled_cost(n // 2, levels - 1) + n
Explanation:

  1. Base case: T(1) = O(1) when subproblem size reaches 1.
  2. Divide: each level doubles subproblem count while halving size.
  3. Conquer: unrolling gives 2^k · T(n/2^k) plus k·n combine cost.
  4. Combine: substitute k = log₂ n → T(n) = n + n log n = Θ(n log n).

Time: Θ(n log n)  |  Applies to any algorithm with this recurrence shape.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# T(n) = 2T(n/2) + O(n)
# a=2, b=2, f(n)=Θ(n)
# n^(log_2 2) = n
# f(n) = Θ(n) = Θ(n^(log_b a))  → Case 2
# T(n) = Θ(n^(log_b a) · log^(k+1) n) where k=0
# T(n) = Θ(n log n)

RECURRENCES = {
    "merge_sort":       (2, 2, "n",       "Θ(n log n)"),
    "binary_search":    (1, 2, "1",       "Θ(log n)"),
    "karatsuba":        (3, 2, "n",       "Θ(n^log₂3)"),
    "strassen":         (7, 2, "n^2",     "Θ(n^log₂7)"),
}
Explanation:

  1. Base case: T(1) = Θ(1) standard assumption.
  2. Divide: identify a (subproblem count) and b (shrink factor).
  3. Conquer: compute critical exponent log_b a.
  4. Combine: compare f(n) to n^(log_b a) — equality (Case 2) adds log n factor → Θ(n log n).

Key insight: any D&C algorithm that splits in half twice and does linear combine work is Θ(n log n).

Problem 3: Strassen's Matrix Multiplication (GeeksforGeeks)#

Problem Statement

Multiply two n × n matrices using Strassen's divide-and-conquer algorithm in sub-cubic time.

Example 1:

Input: A = [[1,2],[3,4]], B = [[5,6],[7,8]]
Output: [[19,22],[43,50]]

Example 2:

Input: 1×1 matrices A = [[3]], B = [[7]]
Output: [[21]]

Constraints:

  • n is a power of 2 (pad if needed)
  • 1 <= n <= 512
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def add(A, B):
    return [[A[i][j] + B[i][j] for j in range(len(A[0]))] for i in range(len(A))]

def sub(A, B):
    return [[A[i][j] - B[i][j] for j in range(len(A[0]))] for i in range(len(A))]

def split(M):
    n = len(M)
    m = n // 2
    return ( [row[:m] for row in M[:m]],
             [row[m:] for row in M[:m]],
             [row[:m] for row in M[m:]],
             [row[m:] for row in M[m:]] )

def strassen(A, B):
    n = len(A)
    if n == 1:
        return [[A[0][0] * B[0][0]]]

    A11, A12, A21, A22 = split(A)
    B11, B12, B21, B22 = split(B)

    M1 = strassen(add(A11, A22), add(B11, B22))
    M2 = strassen(add(A21, A22), B11)
    M3 = strassen(A11, sub(B12, B22))
    M4 = strassen(A22, sub(B21, B11))
    M5 = strassen(add(A11, A12), B22)
    M6 = strassen(sub(A21, A11), add(B11, B12))
    M7 = strassen(sub(A12, A22), add(B21, B22))

    C11 = add(sub(add(M1, M4), M5), M7)
    C12 = add(M3, M5)
    C21 = add(M2, M4)
    C22 = add(sub(add(M1, M3), M2), M6)

    C = [[0] * n for _ in range(n)]
    m = n // 2
    for i in range(m):
        for j in range(m):
            C[i][j] = C11[i][j]
            C[i][j + m] = C12[i][j]
            C[i + m][j] = C21[i][j]
            C[i + m][j + m] = C22[i][j]
    return C
Explanation:

  1. Base case: 1×1 matrices — single scalar multiply.
  2. Divide: partition each matrix into four n/2 × n/2 quadrants.
  3. Conquer: seven recursive multiplies on combinations of quadrants (Strassen's trick).
  4. Combine: assemble C11..C22 from M1..M7 formulas; stitch into result matrix.

Time: O(n^log₂7) ≈ O(n^2.81)  |  Space: O(n²) per recursion level.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
import math

def next_pow2(n: int) -> int:
    return 1 << (n - 1).bit_length()

def pad_matrix(M, size):
    return [row + [0] * (size - len(row)) for row in M] + \
           [[0] * size for _ in range(size - len(M))]

def strassen_padded(A, B):
    n = len(A)
    size = next_pow2(n)
    if size != n:
        A = pad_matrix(A, size)
        B = pad_matrix(B, size)
    C = strassen(A, B)
    return [row[:n] for row in C[:n]]
Explanation:

  1. Base case: same 1×1 scalar multiply after padding.
  2. Divide: pad to next power of 2 so quadrants split evenly.
  3. Conquer: run recursive Strassen on padded matrices.
  4. Combine: crop result back to original n × n dimensions.

Time: O(n^log₂7)  |  Space: O(n²) with padding overhead.

4. Divide and Conquer with Memoization#

Recursive decomposition where overlapping subproblems are cached.

Problem 1: Fibonacci Number with Memoization (Leetcode:509)#

Problem Statement

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:

  • 0 <= n <= 30
Code and Explanation 

1
2
3
4
5
6
7
8
from functools import cache

class Solution:
    @cache
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        return self.fib(n - 1) + self.fib(n - 2)
Explanation:

  1. Base case: F(0) = 0, F(1) = 1.
  2. Divide: split n into subproblems n-1 and n-2.
  3. Conquer: recursively compute each (cached after first call).
  4. Combine: sum the two sub-results. Memoization prunes exponential recomputation to O(n) calls.

Time: O(n)  |  Space: O(n) memo + stack.

1
2
3
4
5
6
7
8
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b
Explanation:

  1. Base case: n <= 1 return n directly.
  2. Divide: implicit — build answers for sizes 2, 3, …, n in order.
  3. Conquer: each iteration solves one subproblem using two prior results.
  4. Combine: F(i) = F(i-1) + F(i-2) rolling forward.

Time: O(n)  |  Space: O(1).

Problem 2: Unique Binary Search Trees (Leetcode:96)#

Problem Statement

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:


Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 19
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from functools import cache

class Solution:
    def numTrees(self, n: int) -> int:
        @cache
        def count(lo: int, hi: int) -> int:
            if lo >= hi:
                return 1
            total = 0
            for root in range(lo, hi + 1):
                total += count(lo, root - 1) * count(root + 1, hi)
            return total

        return count(1, n)
Explanation:

  1. Base case: empty range (lo > hi) → one tree (empty subtree).
  2. Divide: choose each value root in [lo, hi] as the tree root.
  3. Conquer: count unique left BSTs and right BSTs independently.
  4. Combine: multiply left × right counts (Catalan convolution); sum over all root choices.

Time: O(n²) with memo on (lo, hi)  |  Space: O(n²).

1
2
3
4
5
6
7
8
class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = dp[1] = 1
        for nodes in range(2, n + 1):
            for root in range(1, nodes + 1):
                dp[nodes] += dp[root - 1] * dp[nodes - root]
        return dp[n]
Explanation:

  1. Base case: dp[0] = dp[1] = 1 (empty tree and single node).
  2. Divide: for nodes total keys, try each root position.
  3. Conquer: dp[root-1] left subtrees, dp[nodes-root] right subtrees.
  4. Combine: dp[nodes] += left × right — same Catalan recurrence, bottom-up.

Time: O(n²)  |  Space: O(n).

Problem 3: Matrix Chain Multiplication (GeeksforGeeks)#

Problem Statement

Given dimensions of n matrices in an array dims where matrix i has dimensions dims[i-1] × dims[i], find the minimum number of scalar multiplications needed to compute the product.

Example 1:

Input: dims = [1, 2, 3, 4, 3] (matrices: 1×2, 2×3, 3×4, 4×3)
Output: 30

Example 2:

Input: dims = [10, 20, 30] (one product: 10×20 × 20×30)
Output: 6000

Constraints:

  • 2 <= len(dims) <= 100
  • 1 <= dims[i] <= 500
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
from functools import cache

def matrix_chain_order(dims: list[int]) -> int:
    @cache
    def solve(i: int, j: int) -> int:
        if i == j:
            return 0

        best = float("inf")
        for k in range(i, j):
            cost = (solve(i, k) + solve(k + 1, j) +
                    dims[i - 1] * dims[k] * dims[j])
            best = min(best, cost)
        return best

    return solve(1, len(dims) - 1)
Explanation:

  1. Base case: single matrix (i == j) needs 0 multiplications.
  2. Divide: choose split point k between matrices i..k and k+1..j.
  3. Conquer: recursively find optimal cost for left and right chains.
  4. Combine: add left cost + right cost + merge cost dims[i-1] × dims[k] × dims[j]; minimize over k.

Time: O(n³)  |  Space: O(n²) memo.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def matrix_chain_order_dp(dims: list[int]) -> int:
    n = len(dims) - 1
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float("inf")
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
                dp[i][j] = min(dp[i][j], cost)
    return dp[1][n]
Explanation:

  1. Base case: dp[i][i] = 0 for single-matrix intervals.
  2. Divide: iterate interval lengths from 2 to n (smallest chains first).
  3. Conquer: for each [i, j], try every split k.
  4. Combine: dp[i][j] = min(dp[i][k] + dp[k+1][j] + merge cost) — interval D&C tabulated.

Time: O(n³)  |  Space: O(n²).