Skip to content
Data Structures & Algorithms

Divide & Conquer interview questions and answers

54 questions, 40 with code. About 4 h 35 min to read them all.

By TestLab · Updated

Plan for an interview
54 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What defines a divide and conquer algorithm and its key characteristics?

A divide and conquer algorithm solves a problem by breaking it into smaller, usually independent subproblems, solving those recursively, and combining their results. It is especially effective when the input can be divided into a predictable structure and the work at each recursive level does not dominate the total work.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The standard divide and conquer process has three steps:

  1. Divide: Split the problem into smaller subproblems.

  2. Conquer: Recursively solve each subproblem until reaching a base case.

  3. Combine: Merge the subproblem results into the final answer.

A typical recurrence is:

T(n) = aT(n/b) + O(n)

Here:

  • a is the number of subproblems.

  • n/b is the approximate size of each subproblem.

  • O(n) is the work performed to divide or combine results.

For example, merge sort divides an array into two halves, recursively sorts each half, and combines them by merging sorted sequences.

Main Characteristics

  • Recursive decomposition: The problem is reduced into smaller instances of the same or a related problem.

  • Base cases: Recursion stops when the input is small enough to solve directly, such as an empty array or one element.

  • Independent subproblems: The subproblems usually do not share states or solve the same overlapping computations.

  • Combination step: Results from smaller instances must be merged, added, compared, or otherwise processed.

  • Divide-and-conquer structure: The recursion forms a tree, with leaves representing base-case computations.

  • Predictable partitioning: The algorithm often assumes that each recursive call receives an approximately equal-sized portion, although not every divide and conquer algorithm requires this.

Typical examples include merge sort, quicksort, binary search, Karatsuba multiplication, counting inversions, and the divide and conquer version of maximum subarray.

Complexity

There is no single complexity for every divide and conquer algorithm; it depends on the number of subproblems, their size, and the division and combination costs.

Algorithm Best Case Average Case Worst Case Auxiliary Space
Merge sort O(n log n) O(n log n) O(n log n) O(n)
Binary search O(1) O(log n) O(log n) O(1) iterative
Quicksort O(n log n) O(n log n) expected O(n²) O(log n) expected stack; O(n) worst-case stack

For merge sort, the auxiliary O(n) includes the merge buffer and O(log n) recursion stack. The input array is not counted. For iterative binary search, space is O(1). For quicksort, the input is excluded from auxiliary space; randomized pivot selection makes the expected recursion depth O(log n).

When the recurrence fits the Master Theorem, T(n) = aT(n/b) + f(n):

  • Case 1: If f(n) = O(n^(log_b(a) - ε)), then T(n) = O(n^(log_b(a))).

  • Case 2: If f(n) = Θ(n^(log_b(a))), then T(n) = Θ(n^(log_b(a)) log n).

  • Case 3: If f(n) = Θ(n^(log_b(a) + ε)), then T(n) = Θ(n^(log_b(a) + ε)).

Not every algorithm satisfies the Master Theorem’s regularity conditions.

Divide and Conquer vs. Dynamic Programming

Approach Subproblem Overlap Typical Use
Divide and conquer Subproblems are generally independent Sorting, searching, geometric algorithms
Dynamic programming Subproblems overlap and are reused Shortest paths, coin change, sequence optimization

If different recursive branches repeatedly calculate the same result, plain divide and conquer repeats that work. Memoization or tabulation should then be used to store and reuse those results.

Common Pitfalls and Interview Tips

  • Incorrect base cases: Empty and single-element inputs must terminate correctly.

  • Missing combination logic: Recursive results are not useful until they are merged correctly.

  • Ignoring duplicate handling: Sorting algorithms must define whether equal values remain separate elements.

  • Unbalanced partitions: Quicksort can degrade to O(n²) when pivots repeatedly create highly unbalanced partitions.

  • Incorrect complexity accounting: Recursion-stack space counts toward auxiliary space unless the algorithm is implemented iteratively.

  • Mutating input: Some implementations rearrange the original collection, while others allocate additional storage.

  • Confusing overlap: Divide and conquer is appropriate when subproblems do not overlap; dynamic programming is generally better when they do.

2

How do Divide & Conquer and Dynamic Programming differ?

Divide & Conquer breaks a problem into independent recursive subproblems and combines their results, while Dynamic Programming stores and reuses results for overlapping subproblems. The key distinction is whether the same subproblem is solved repeatedly—not whether recursion is used.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

  • Divide & Conquer:

  • Divide: Split the input into smaller, usually non-overlapping parts.

  • Conquer: Solve each part recursively until reaching a base case.

  • Combine: Merge the subproblem results into the final answer.

  • Dynamic Programming:

  • Define: Identify states that can be reused.

  • Recurrence: Express each state in terms of smaller states.

  • Evaluate: Compute each state once using memoization or tabulation.

Dynamic Programming may use recursion, but it adds caching or a table so overlapping states are not recomputed. Divide & Conquer generally does not benefit from memoization because its subproblems do not overlap. If Divide & Conquer subproblems do overlap, memoizing them effectively turns the solution into Dynamic Programming.

Recurrences and Complexity

A typical Divide & Conquer recurrence is:

T(n) = aT(n/b) + f(n)

For merge sort, the recurrence is:

T(n) = 2T(n/2) + O(n)

By the Master Theorem, Case 2, this solves to O(n log n) time. Its auxiliary space is O(n) because merging uses a buffer containing up to n elements, while the recursion stack contributes O(log n).

For Fibonacci, the Dynamic Programming recurrence is:

F(n) = F(n - 1) + F(n - 2)

There are n + 1 states, each requiring constant work, so the result is O(n) time. Storing every state takes O(n) space, although retaining only the previous two values reduces it to O(1).

Approach and example Best time Average time Worst time Auxiliary space
Naive recursive Fibonacci O(φⁿ) O(φⁿ) O(φⁿ) O(n) recursion stack
Dynamic Programming Fibonacci O(n) O(n) O(n) O(1) with rolling values
Divide & Conquer merge sort O(n log n) O(n log n) O(n log n) O(n) buffer plus O(log n) stack

These space complexities include the recursion stack where applicable and exclude the input itself. Here, φ is the golden ratio, approximately 1.618.

Divide-and-Conquer Pattern

Divide & Conquer works especially well when:

  • The problem has a natural partition into smaller inputs.

  • Each partition can be solved independently.

  • The answers can be merged efficiently.

Merge sort demonstrates the pattern well: divide a list into halves, recursively sort each half, and merge the sorted halves. It naturally handles empty and single-element lists, duplicates, and negative numbers. Its behavior is unchanged for already sorted input, although sorting is still O(n log n) time.

Worked Example

For merge sort with [3, -1, 2, 3, 0]:

  1. Divide: Split into [3, -1] and [2, 3, 0].

  2. Divide again: Split these into [3], [-1], [2], and [3, 0].

  3. Reach base cases: [3], [-1], and [2] are already sorted; split [3, 0] into [3] and [0].

  4. Combine: Merge [3] and [-1] into [-1, 3]; merge [3] and [0] into [0, 3].

  5. Combine again: Merge [2] and [0, 3] into [0, 2, 3].

  6. Final merge: Merge [-1, 3] and [0, 2, 3], producing [-1, 0, 2, 3, 3].

Dynamic Programming is preferable when different branches repeatedly request the same state, as in recursive Fibonacci.

Choosing Between Them

  • Use Divide & Conquer when the problem splits into independent subproblems and their results can be combined efficiently.

  • Use Dynamic Programming when subproblems overlap and previously computed results can be reused.

  • Many algorithms can be viewed through either lens, so analyze the recurrence and whether repeated states occur rather than relying only on whether recursion is present.

Common Pitfalls

  • Confusing recursion with Dynamic Programming: recursion alone does not make an algorithm dynamic; repeated states must actually be reused.

  • Ignoring stack space: recursive Fibonacci requires O(n) stack space and can exceed Python’s default recursion limit; an iterative implementation avoids this.

  • Mutating the input unintentionally: decide whether an implementation should preserve the original collection.

  • Off-by-one errors: carefully handle base cases such as n = 0 and n = 1 and the boundaries used while combining partitions.

  • Integer overflow: Python integers grow automatically, but fixed-width languages can overflow when calculating large Fibonacci numbers.

Interviewers commonly follow up by asking for the recurrence, base case, overlap analysis, proof of correctness, or an iterative alternative.

3

How does recursion support Divide and Conquer algorithms?

Recursion is the natural control mechanism for Divide and Conquer algorithms: it repeatedly divides a problem into smaller subproblems, solves them recursively until reaching a base case, and then combines their results. Recursion also manages the call stack that preserves each subproblem’s state.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Recursion Works

A Divide and Conquer algorithm usually follows three steps:

  1. Divide: Split the input into smaller, independent subproblems.

  2. Conquer: Recursively solve each subproblem, stopping at a simple base case.

  3. Combine: Merge the subproblem results into the final answer.

The base case is essential because it prevents infinite recursion. Without it, the decomposition would continue until it exhausted memory or exceeded the language’s recursion limit.

Recursion is especially suitable when the problem has a recursive structure and the subproblems are similar but smaller. The call stack automatically stores the boundaries, partial results, and return addresses needed to perform the combine step.

Complexity and the Master Theorem

For merge sort, the recurrence is:

T(n) = 2T(n/2) + O(n)

  • 2T(n/2) represents the two recursive subproblems.

  • O(n) represents dividing and combining the data.

This is Master Theorem Case 2, where f(n) = Θ(n^(log_b a)). Therefore:

T(n) = O(n log n)

For merge sort, the result is the same across input distributions:

Case Time Reason
Best O(n log n) The recursion tree has O(log n) levels, with O(n) work per level.
Average O(n log n) Randomization does not change merge sort’s asymptotic cost.
Worst O(n log n) Every merge is linear, and the recursion depth remains logarithmic.

Auxiliary space is O(n), including temporary lists and the O(log n) recursion stack. The input is not counted; the returned list is output space.

Example Walkthrough

Sorting [4, 1, 3, 2] proceeds as follows:

Step Divide Conquer Combine
1 [4, 1, 3, 2] → [4, 1], [3, 2] Recursively sort both halves Merge sorted halves
2 [4, 1] → [4], [1] Base cases return directly Produce [1, 4]
3 [3, 2] → [3], [2] Base cases return directly Produce [2, 3]
4 Two sorted halves are available Subproblems are solved Produce [1, 2, 3, 4]

Divide and Conquer vs. Dynamic Programming

Approach Subproblem behavior Typical recurrence Common use
Divide and Conquer Subproblems are generally independent T(n) = 2T(n/2) + O(n) Merge sort, binary search, Karatsuba
Dynamic Programming Subproblems overlap and reuse stored results T(n) = T(n-1) + T(n-2) + O(1) without memoization Fibonacci, shortest paths, knapsack

If recursive subproblems overlap significantly, memoization or bottom-up dynamic programming usually avoids repeated computation.

Code Example

from collections.abc import Sequence


def merge_sort(values: Sequence[int]) -> list[int]:
    """Return a sorted copy of values using Divide and Conquer."""
    items = list(values)

    def sort_range(left: int, right: int) -> None:
        # Base case: zero or one element is already sorted.
        if right - left <= 1:
            return

        # Divide: split the current range into two smaller ranges.
        middle = (left + right) // 2

        # Conquer: recursively sort both independent subranges.
        sort_range(left, middle)
        sort_range(middle, right)

        # Combine: merge the two sorted subranges.
        merged: list[int] = []
        left_index = left
        right_index = middle

        while left_index < middle and right_index < right:
            if items[left_index] <= items[right_index]:
                merged.append(items[left_index])
                left_index += 1
            else:
                merged.append(items[right_index])
                right_index += 1

        merged.extend(items[left_index:middle])
        merged.extend(items[right_index:right])
        items[left:right] = merged

    sort_range(0, len(items))
    return items


print(merge_sort([5, 2, 4, 2]))  # [2, 2, 4, 5]

Common Pitfalls

  • Missing base case: The recursion may never terminate.

  • Incorrect merge boundaries: Off-by-one errors can drop elements or duplicate them.

  • Mutating input unintentionally: The example returns a new list and leaves the caller’s sequence unchanged.

  • Ignoring stack depth: Merge sort has only O(log n) recursion depth, but algorithms such as naïve quicksort can require O(n) depth and exceed Python’s default recursion limit.

  • Assuming all inputs are distinct: The merge comparison uses <= so duplicate values are retained correctly.

  • Interview follow-up: Interviewers commonly ask for the recurrence, Master Theorem case, comparison with dynamic programming, and how the algorithm handles empty input, one element, duplicates, and already sorted data.

4

What are the three steps of Divide and Conquer

The Divide and Conquer paradigm solves a problem by recursively breaking it into smaller subproblems of the same type, solving those subproblems, and merging their results. The three canonical steps are Divide, Conquer, and Combine.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

The Three Steps

  • Divide: Split the original problem into two or more smaller, independent subproblems of the same structure. The division continues until subproblems become simple enough to solve directly (the base case).

  • Conquer: Solve each subproblem recursively. If a subproblem is small enough, solve it directly without further recursion.

  • Combine: Merge the solutions of the subproblems to form the solution to the original problem. This step is where the algorithm’s specific logic lives (e.g., merging two sorted halves in merge sort).

Recurrence and Master Theorem

A typical D&C algorithm that creates a subproblems of size n/b and spends f(n) time dividing and combining yields the recurrence: T(n) = a·T(n/b) + f(n).

For merge sort: a = 2, b = 2, f(n) = O(n) → T(n) = 2T(n/2) + O(n).
By the Master Theorem, this falls into Case 2 (f(n) = Θ(n^{log_b a} log^k n) with k = 0), giving T(n) = O(n log n).

Divide & Conquer vs. Dynamic Programming

Aspect Divide & Conquer Dynamic Programming
Subproblem overlap None (independent) Yes (overlapping)
Technique Pure recursion Memoization or tabulation
Typical use Merge sort, quicksort, binary search, closest pair Fibonacci, knapsack, LCS, edit distance
Space Recursion stack only Extra table for subproblem results

When subproblems do overlap, D&C repeats work exponentially; DP stores each subproblem’s result once, reducing time from exponential to polynomial.

Common Pitfalls

  • Forgetting the base case: Without a stopping condition, recursion never terminates (stack overflow).

  • Incorrect combine logic: The merge step must correctly assemble the final answer; an off-by-one error here corrupts the whole result.

  • Assuming no overlap: If subproblems share work (e.g., naive recursive Fibonacci), D&C is inefficient—switch to DP.

  • Ignoring recursion depth: Python’s default limit (~1000) can be hit for large n; consider an iterative version or sys.setrecursionlimit.

  • Counting space incorrectly: Space complexity includes the recursion stack (O(log n) for balanced splits, O(n) worst case for quicksort).

Interview Tips

  • Be ready to write the recurrence for a given D&C algorithm and solve it with the Master Theorem.

  • Interviewers often ask: “When would you choose D&C over DP?” Answer: when subproblems are independent.

  • Follow-up: “How does quicksort’s worst case differ from merge sort?” Quicksort degrades to O(n²) with bad pivots; merge sort guarantees O(n log n).

  • Know the classic D&C problems: merge sort, quicksort, binary search, maximum subarray (D&C version), closest pair of points, Karatsuba multiplication, counting inversions, fast exponentiation (pow(x, n)).

5

What example recurrence models a Divide & Conquer algorithm’s runtime?

A recurrence such as T(n) = 2T(n/2) + Θ(n) models the runtime of a Divide & Conquer algorithm such as merge sort: it solves two half-sized subproblems and performs linear work to combine their results. Its base case is typically T(1) = Θ(1).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Example Algorithm

Merge sort reflects the three standard Divide & Conquer steps:

  • Divide: Split the input into two approximately equal halves.

  • Conquer: Recursively sort each half.

  • Combine: Merge the two sorted halves into one sorted list.

The size of a subproblem decreases by half at each recursive level. Merge sort is stable and guarantees O(n log n) running time.

Recurrence and Master Theorem

For merge sort, the recurrence is T(n) = 2T(n/2) + Θ(n) for n > 1, with the base case T(1) = Θ(1).

Its components are:

  • 2T(n/2): two recursive calls on half-sized inputs.

  • Θ(n): the work required to merge the sorted halves.

  • T(1) = Θ(1): constant work for the base case.

Using the Master Theorem:

  • a = 2 is the number of recursive subproblems.

  • b = 2 is the factor by which the input size is reduced.

  • f(n) = Θ(n) is the non-recursive work.

  • n^(log_b a) = n^(log₂ 2) = n.

Because f(n) = Θ(n^(log_b a)), this is Master Theorem Case 2. Therefore, T(n) = Θ(n log n).

Complexity Comparison

Approach Best time Average time Worst time Auxiliary space When to use
Selection sort O(n²) O(n²) O(n²) O(1) Simple instructional implementation
Merge sort O(n log n) O(n log n) O(n log n) O(n) Stable sorting with guaranteed performance

Merge sort’s O(n) auxiliary space includes temporary lists and an O(log n) recursion stack. The input itself is excluded because this is auxiliary-space complexity.

Three Steps in an Example

For the input [5, 2, 4, 6, 1, 3]:

Stage Result
Divide [5, 2, 4] and [6, 1, 3]
Divide and conquer [2, 4, 5] and [1, 3, 6]
Combine [1, 2, 3, 4, 5, 6]

Divide & Conquer typically creates independent, non-overlapping subproblems. If an algorithm repeatedly solves the same subproblems, memoization or dynamic programming is generally more appropriate.

Common Pitfalls

  • Missing base case: Recursion must stop at inputs of size 0 or 1.

  • Incorrect merge indices: Off-by-one errors can skip values or cause an IndexError.

  • Assuming every D&C algorithm is balanced: An unbalanced recurrence can produce different complexity, such as O(n²).

  • Confusing D&C with dynamic programming: D&C subproblems normally do not overlap; memoization addresses overlapping subproblems.

  • Ignoring auxiliary memory: Merge sort uses both temporary storage and a recursion stack.

Interviewers commonly ask why merge sort is O(n log n), how the Master Theorem applies, and how its stability and space usage compare with quicksort or heapsort.

6

What is the Master Theorem in Divide & Conquer analysis?

The Master Theorem determines the asymptotic running time of a Divide & Conquer recurrence of the form T(n) = aT(n/b) + f(n). It classifies the solution into three cases based on how the combining work f(n) compares with the total recursive work.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, Combine

A Divide & Conquer algorithm follows three steps:

  1. Divide: Split the input into smaller subproblems.

  2. Conquer: Solve each subproblem recursively, stopping at the base case.

  3. Combine: Combine the subproblem results into the final answer.

For example, merge sort divides a list into two halves, recursively sorts them, and combines the sorted halves.

The Master Theorem

The standard recurrence is:

T(n) = aT(n/b) + f(n)

where:

  • a is the number of subproblems.

  • b is the factor by which each subproblem is smaller.

  • f(n) is the non-recursive work performed at each level.

  • The base-case cost is treated as a constant.

Let:

p = log_b(a)

The result depends on the relationship between f(n) and n^p:

Master Theorem case Condition Result
Case 1 f(n) = O(n^(p - ε)) T(n) = Θ(n^p)
Case 2 f(n) = Θ(n^p) T(n) = Θ(n^p log n)
Case 3 f(n) = Ω(n^(p + ε)) and the regularity condition holds T(n) = Θ(f(n))

Here, ε > 0.

Case 3 also requires a regularity condition, commonly written as:

a · f(n/b) ≤ c · f(n) for some constant c < 1 and sufficiently large n.

This condition ensures that recursive work does not dominate the combining work by an uncontrolled amount. If it fails, the standard Master Theorem may be inconclusive.

Applying It to Merge Sort

Merge sort has:

  • a = 2 subproblems

  • b = 2

  • f(n) = Θ(n) for merging

Therefore:

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

Here, p = log₂(2) = 1. Since f(n) = Θ(n^p), this is Case 2:

T(n) = Θ(n log n)

A small trace for [4, 1, 3, 2] is:

  1. Divide into [4, 1] and [3, 2].

  2. Divide again into [4], [1], [3], and [2].

  3. Conquer the one-element base cases.

  4. Combine [4] and [1] into [1, 4].

  5. Combine [3] and [2] into [2, 3].

  6. Combine the two sorted halves into [1, 2, 3, 4].

Code Example

def merge_sort(values: list[int]) -> list[int]:
    """Return a sorted copy of values using merge sort."""
    if len(values) <= 1:
        return values.copy()

    midpoint = len(values) // 2

    # Divide: split the input into two smaller subproblems.
    left = merge_sort(values[:midpoint])
    right = merge_sort(values[midpoint:])

    # Conquer: both recursive calls above return sorted subproblems.

    # Combine: merge the two sorted lists.
    merged: list[int] = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged


print(merge_sort([4, 1, 3, 2]))
# Expected output: [1, 2, 3, 4]

Merge sort handles empty input, one element, duplicates, negative numbers, and already sorted input. It does not mutate the original list.

Complexity and Importance

For merge sort:

Case Time
Best O(n log n)
Average O(n log n)
Worst O(n log n)
  • Time: O(n log n) because each of O(log n) levels performs O(n) total merging work.

  • Auxiliary space: O(n), excluding the input, for the merged lists and temporary slices.

  • Recursion stack: O(log n), included in the total auxiliary-space bound.

  • Input storage: excluded from the space-complexity calculation.

The theorem is important because it replaces manual recursion-tree analysis with a direct comparison between recursive and combining work.

Unlike Divide & Conquer, dynamic programming commonly solves overlapping subproblems. Memoization is usually preferable when the same subproblem is repeatedly computed; Divide & Conquer is most effective when its subproblems do not overlap.

Common Pitfalls

  • Wrong recurrence: Include all non-recursive work, not only the cost of combining results.

  • Ignoring the regularity condition: Case 3 cannot automatically be applied to every Ω case.

  • Using the theorem too broadly: Recurrences with unequal subproblem sizes or irregular work are better handled by the Akra–Bazzi theorem.

  • Ignoring floors and ceilings: Real recurrences often contain ⌊n/b⌋ and ⌈n/b⌉; these usually do not change the asymptotic result.

  • Mutating input accidentally: Decide whether the algorithm should preserve the caller’s data.

Interviewers commonly follow up by asking you to derive a recurrence, identify the applicable case, substitute a, b, and f(n), and explain why the resulting complexity follows from that case.

8

How to find array min and max with Divide & Conquer

The Divide & Conquer approach finds the minimum and maximum of an array by recursively splitting it into halves, solving each half, and combining the two results with two comparisons.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Divide: split the current subarray into two roughly equal halves.

  • Conquer: recursively find the minimum and maximum in each half. Base cases handle subarrays of size 1 (min = max = the element) and size 2 (one comparison decides min and max).

  • Combine: the overall minimum is the smaller of the two half-minimums; the overall maximum is the larger of the two half-maximums.

Recurrence and Complexity

  • Recurrence:
    T(n) = 2T(n/2) + 2 for n > 2
    T(1) = 0 comparisons, T(2) = 1 comparison.

  • Master Theorem: a = 2, b = 2, f(n) = O(1).
    n^{log_b a} = n. Since f(n) = O(n^{1-ε}) for ε = 1, this is Case 1 → T(n) = Θ(n).

  • Comparisons: exactly ⌈3n/2⌉ - 2, which is optimal for comparison-based algorithms.

  • Time: O(n) best, average, and worst case.

  • Space: O(log n) recursion stack (input array not counted).

Comparison with Dynamic Programming

Divide & Conquer subproblems are independent (no overlap), so memoization provides no benefit. Dynamic programming would add unnecessary overhead.

Step-by-Step Example

Array: [3, 5, 1, 9, 2, 8]

  1. Split into [3, 5, 1] and [9, 2, 8].

  2. Left half [3, 5, 1] → split [3, 5] and [1].
    [3, 5] → min=3, max=5 (1 comparison).
    [1] → min=1, max=1.
    Combine → min=1, max=5.

  3. Right half [9, 2, 8] → split [9, 2] and [8].
    [9, 2] → min=2, max=9.
    [8] → min=8, max=8.
    Combine → min=2, max=9.

  4. Final combine → min=min(1,2)=1, max=max(5,9)=9.

Code Example

from typing import List, Tuple

def min_max_dc(arr: List[int]) -> Tuple[int, int]:
    """
    Return (minimum, maximum) of arr using Divide & Conquer.
    Raises ValueError if arr is empty.
    """
    if not arr:
        raise ValueError("Array must not be empty")

    def helper(left: int, right: int) -> Tuple[int, int]:
        # Base case: one element
        if left == right:
            return arr[left], arr[left]
        # Base case: two elements
        if right == left + 1:
            if arr[left] < arr[right]:
                return arr[left], arr[right]
            return arr[right], arr[left]

        # Divide
        mid = (left + right) // 2
        # Conquer
        min_left, max_left = helper(left, mid)
        min_right, max_right = helper(mid + 1, right)
        # Combine
        overall_min = min_left if min_left < min_right else min_right
        overall_max = max_left if max_left > max_right else max_right
        return overall_min, overall_max

    return helper(0, len(arr) - 1)


# Example call
# min_max_dc([3, 5, 1, 9, 2, 8])  # -> (1, 9)

Common Pitfalls

  • Empty input: always check and raise an error or return a sentinel; the recursive helper assumes at least one element.

  • Recursion depth: depth is log₂ n, safe for Python’s default limit (~1000) up to n ≈ 2¹⁰⁰⁰. For huge streams, use an iterative tournament method.

  • Mutating input: the algorithm reads only; do not sort or modify the array.

  • Off-by-one indices: the helper uses inclusive left and right bounds; mid + 1 starts the right half.

  • Interview follow-ups:

  • “Can you do it iteratively?” (pairwise tournament, same comparisons, O(1) space).

  • “Find the second-largest element.” (track losers in the tournament tree).

  • “Why not just use min() and max()?” (two passes = 2n - 2 comparisons; D&C saves ~25%).

9

How does Merge Sort apply Divide & Conquer?

Merge sort exemplifies Divide & Conquer by splitting the input into smaller subproblems, recursively sorting those subproblems, and combining the sorted results through merging. It guarantees (O(n log n)) time complexity, making it a stable and predictable sorting algorithm.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, and Combine

Merge sort applies the three steps as follows:

  1. Divide: Split the array into two approximately equal halves.

  2. Conquer: Recursively apply merge sort to each half until each subarray contains at most one element. A one-element array is already sorted.

  3. Combine: Merge the two sorted subarrays into one sorted array by repeatedly selecting the smaller remaining element.

Because the two recursive calls operate on separate halves, their subproblems do not overlap.

Recurrence and Complexity

The recurrence is:

[ T(n) = 2T(n/2) + O(n) ]

  • The two recursive calls contribute (2T(n/2)).

  • Merging the results takes (O(n)), since each element is processed once per merge level.

This is Master Theorem Case 2, because:

[ a = 2,quad b = 2,quad f(n) = O(n) ]

and:

[ n^{log_b a} = n^{log_2 2} = n ]

Therefore, the overall time complexity is:

[ T(n) = O(n log n) ]

Case Time Reason
Best (O(n log n)) Merging still processes all elements at each level
Average (O(n log n)) The recurrence is unchanged by input order
Worst (O(n log n)) The number of levels and merge work is predictable

The auxiliary space complexity is (O(n)): the implementation uses an (O(n)) buffer plus an (O(log n)) recursion stack. The input list itself is not counted because the function sorts and returns a copy.

Small Walkthrough

For the input [5, 2, 4, 2, -1]:

Step Operation Result
1 Divide the input [5, 2] and [4, 2, -1]
2 Divide and sort the left half [2, 5]
3 Divide and sort the right half [-1, 2, 4]
4 Combine the sorted halves [-1, 2, 2, 4, 5]

Code Example

def merge_sort(values: list[int]) -> list[int]:
    """Return a sorted copy of values using merge sort."""
    working = values.copy()
    buffer = [0] * len(working)

    def merge(left: int, middle: int, right: int) -> None:
        left_index = left
        right_index = middle
        output_index = left

        # Combine: merge the two sorted halves.
        while left_index < middle and right_index < right:
            if working[left_index] <= working[right_index]:
                buffer[output_index] = working[left_index]
                left_index += 1
            else:
                buffer[output_index] = working[right_index]
                right_index += 1
            output_index += 1

        while left_index < middle:
            buffer[output_index] = working[left_index]
            left_index += 1
            output_index += 1

        while right_index < right:
            buffer[output_index] = working[right_index]
            right_index += 1
            output_index += 1

        for index in range(left, right):
            working[index] = buffer[index]

    def sort(left: int, right: int) -> None:
        if right - left <= 1:
            return

        # Divide: split into two approximately equal halves.
        middle = left + (right - left) // 2

        # Conquer: recursively sort both halves.
        sort(left, middle)
        sort(middle, right)

        # Combine: merge the sorted halves.
        merge(left, middle, right)

    sort(0, len(working))
    return working


example = merge_sort([5, 2, 4, 2, -1])
print(example)  # [-1, 2, 2, 4, 5]

Merge Sort Versus Dynamic Programming

Aspect Merge Sort Dynamic Programming
Strategy Divide and Conquer Reuse overlapping subproblem results
Subproblems Do not overlap Often overlap
State storage No memoization table Memoization or bottom-up table
Typical use Sorting independent subarrays Shortest paths, optimization, counting problems

If independently calculated subproblems overlap and the same results are needed repeatedly, memoization is usually preferable to repeatedly solving them.

Common Pitfalls and Interview Tips

  • Infinite recursion: Always stop when the segment length is at most one.

  • Off-by-one errors: Using an exclusive right boundary requires right - left <= 1 as the base case and middle < right.

  • Mutation: Sorting the input in place may surprise callers; the example returns a copy.

  • Stability: When values are equal, taking the element from the left half preserves stability.

  • Space usage: The auxiliary buffer is (O(n)), even though the recursion depth is only (O(log n)).

  • Follow-up questions: Interviewers commonly ask about stability, the (O(n log n)) lower bound for comparison sorting, the difference from heapsort, and how to perform the merge efficiently.

10

How does Quicksort apply the Divide & Conquer strategy?

Quicksort uses Divide & Conquer by placing a pivot in its final position and then sorting the partitions on either side. Unlike merge sort, its combine step requires no merging because the algorithm partitions the array in place.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Divide and Conquer Applies

  1. Divide: Choose a pivot and rearrange the elements into values less than the pivot, values equal to it, and values greater than it.

  2. Conquer: Sort the less-than and greater-than partitions independently. These subproblems contain disjoint sets of elements.

  3. Combine: No explicit merge is needed. The pivot region is already between the two sorted partitions.

Three-way partitioning is especially useful when duplicates are common because equal values are grouped and excluded from further recursive work.

Quicksort’s divide-and-conquer subproblems do not overlap. When subproblems do overlap, as in many dynamic-programming problems, memoization is generally preferable because it reuses previously computed answers.

Recurrence and Complexity

For balanced partitions with two nonempty recursive parts, the recurrence is:

T(n) = 2T(n/2) + O(n)

The O(n) term represents partitioning. By the Master Theorem, Case 2, this gives O(n log n).

A highly unbalanced partition produces:

T(n) = T(n - 1) + O(n)

which gives O(n²).

Case Time Reason
Best O(n) In the shown three-way implementation, an input containing one distinct value needs one partition pass and creates no recursive partitions.
Average/expected O(n log n) A uniformly random pivot gives expected O(n log n) total work.
Worst O(n²) Unlucky pivot choices repeatedly leave a partition containing nearly all remaining elements.
  • Auxiliary space: O(1) in the best case, such as when all values are equal; O(log n) in the average and worst cases. The explicit stack is included, and processing the smaller partition first limits its depth. Partitioning itself uses O(1) space.

  • The caller-owned input array is not counted in auxiliary space. Including the input storage, total memory usage is O(n).

  • This implementation of Quicksort is generally not stable, because partitioning can change the relative order of equal elements.

Example Walkthrough

For [7, 2, 5, 3, 6, 1, 4], one possible pivot sequence is:

Step Less-than region Equal region Greater-than region
Choose pivot 5 [4, 2, 3, 1] [5] [6, 7]
Choose pivot 3 in the left partition [1, 2] [3] [4]
Choose pivot 6 in the right partition [] [6] [7]

After the less-than and greater-than regions are sorted, the combined result is [1, 2, 3, 4, 5, 6, 7].

Code Example

from random import randrange


def quicksort(values: list[int]) -> list[int]:
    """Sort a list of integers in place using randomized Quicksort."""
    pending: list[tuple[int, int]] = [(0, len(values) - 1)]

    while pending:
        left, right = pending.pop()
        if left >= right:
            continue

        pivot_value = values[randrange(left, right + 1)]

        # Divide: create less-than, equal-to, and greater-than regions.
        less = left
        current = left
        greater = right

        while current <= greater:
            if values[current] < pivot_value:
                values[less], values[current] = values[current], values[less]
                less += 1
                current += 1
            elif values[current] > pivot_value:
                values[current], values[greater] = values[greater], values[current]
                greater -= 1
                # The swapped-in value has not yet been examined.
            else:
                current += 1

        left_end = less - 1
        right_start = greater + 1
        left_size = less - left
        right_size = right - greater

        # Conquer: process the smaller partition first to limit stack depth.
        # Because the stack is LIFO, push the larger partition first.
        if left_size < right_size:
            if right_start <= right:
                pending.append((right_start, right))
            if left <= left_end:
                pending.append((left, left_end))
        else:
            if left <= left_end:
                pending.append((left, left_end))
            if right_start <= right:
                pending.append((right_start, right))

    # Combine: no merge is required; pivot values remain in their final regions.
    return values


if __name__ == "__main__":
    print(quicksort([7, 2, 5, 3, 6, 1, 4]))
    # Expected output: [1, 2, 3, 4, 5, 6, 7]

Common Pitfalls

  • Incorrect pivot handling: Exclude the equal-valued region when scheduling further work.

  • Off-by-one errors: Define whether partition boundaries are inclusive or exclusive.

  • Edge cases: Empty and one-element lists remain unchanged; duplicates, including all-equal inputs, are grouped; negative values use normal comparisons; already sorted inputs remain correct.

  • Duplicate-heavy inputs: A two-way partition can degrade to O(n²), while three-way partitioning groups equal values.

  • Unsafe swaps: After swapping with greater, do not advance current because the incoming element has not yet been examined.

  • Input mutation: This implementation sorts the original list in place; copy it first if preservation is required.

  • Recursion limits: The explicit stack avoids Python’s recursion-depth limit.

  • Common follow-up questions: Pivot selection, stability, worst-case behavior, randomized versus median-of-three pivots, and why processing the smaller partition first limits auxiliary stack space.

11

How does Karatsuba multiplication apply divide and conquer to large integers?

Karatsuba multiplication applies divide and conquer by splitting two large numbers into high and low halves, using three recursive multiplications instead of four, and then recombining the results. This reduces the multiplication cost from the classical (O(n^2)) to approximately (O(n^{1.585})).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For numbers (x) and (y), choose a power of two (B = 2^m) and split each operand:

[ x = x_1B + x_0 ]

[ y = y_1B + y_0 ]

where (x_1) and (y_1) are the high halves and (x_0) and (y_0) are the low halves.

The three steps are:

  1. Divide: Split both operands into high and low halves.

  2. Conquer: Recursively calculate:

  3. (z_0 = x_0y_0)

  4. (z_2 = x_1y_1)

  5. (z_1 = (x_0 + x_1)(y_0 + y_1) - z_0 - z_2)

  6. Combine: Reconstruct the answer:

[ xy = z_2B^2 + z_1B + z_0 ]

The important optimization is that the middle cross term is computed with one additional multiplication:

[ x_0y_1 + x_1y_0 ]

rather than calculating (x_0y_1) and (x_1y_0) separately.

Small Example

Using binary splitting with (m=2), so (B=4):

  • (10 = 2 cdot 4 + 2), so (x_1=2), (x_0=2)

  • (6 = 1 cdot 4 + 2), so (y_1=1), (y_0=2)

The recursive products are:

  • (z_0 = 2 cdot 2 = 4)

  • (z_2 = 2 cdot 1 = 2)

  • (z_1 = (2+2)(2+1)-4-2 = 6)

Combining them:

[ 2 cdot 4^2 + 6 cdot 4 + 4 = 32 + 24 + 4 = 60 ]

Therefore, (10 times 6 = 60).

Recurrence and Complexity

Let (n) be the number of bits in the larger operand. Karatsuba makes three recursive calls on operands of approximately (n/2) bits and performs linear-time additions, shifts, and recombination:

[ T(n) = 3T(n/2) + O(n) ]

By the Master Theorem, this is Case 1, because:

[ f(n)=O(n) = Oleft(n^{log_2 3-varepsilon}right) ]

for a suitable (varepsilon > 0). Therefore:

  • Time: (Theta(n^{log_2 3}) approx Theta(n^{1.585}))

  • Best case: (Theta(n^{1.585}))

  • Average case: (Theta(n^{1.585}))

  • Worst case: (Theta(n^{1.585}))

  • Auxiliary space: (O(log n)) recursion-stack depth in the standard unit-cost arithmetic model, excluding the input and result. When arbitrary-precision integer storage is counted, the geometrically shrinking subproblems require (O(n)) auxiliary bits in this implementation.

Comparison with Dynamic Programming

Karatsuba is a divide-and-conquer algorithm because its recursive subproblems do not overlap: the three calls use different combinations of the split operands.

Dynamic programming is preferable when the same subproblem is requested repeatedly. In that situation, memoization or tabulation stores previously computed results and prevents redundant work. Karatsuba does not need memoization because its subproblems are distinct.

Code Example

def karatsuba_multiply(left: int, right: int) -> int:
    """Multiply two integers using educational Karatsuba recursion."""
    negative = (left < 0) != (right < 0)
    left = abs(left)
    right = abs(right)
    threshold = 32

    def multiply(num1: int, num2: int) -> int:
        if num1 == 0 or num2 == 0:
            return 0

        width = max(num1.bit_length(), num2.bit_length())
        if width <= threshold:
            return num1 * num2

        half_bits = (width + 1) // 2
        mask = (1 << half_bits) - 1

        # Divide
        num1_low = num1 & mask
        num1_high = num1 >> half_bits
        num2_low = num2 & mask
        num2_high = num2 >> half_bits

        # Conquer
        low_product = multiply(num1_low, num2_low)
        high_product = multiply(num1_high, num2_high)
        cross_product = (
            multiply(num1_low + num1_high, num2_low + num2_high)
            - low_product
            - high_product
        )

        # Combine
        return (
            (high_product << (2 * half_bits))
            + (cross_product << half_bits)
            + low_product
        )

    product = multiply(left, right)
    return -product if negative else product


print(karatsuba_multiply(123456789, 987654321))
# Expected output: 121932631112635269

Common Pitfalls

  • Incorrect bit width: Split both operands at the same power-of-two boundary.

  • Lost signs: Convert to absolute values and restore the sign only after multiplication.

  • Zero input: Handle zero explicitly to avoid unnecessary recursion.

  • Off-by-one errors: Ensure the low-part mask has exactly half_bits bits.

  • Repeated merging mistakes: The combine expression must use (B^2), (B), and (1) for the high, middle, and low terms.

  • Production use: Python’s built-in int multiplication is already optimized, so this implementation is primarily educational.

12

How does Strassen's algorithm multiply matrices with divide and conquer?

Strassen’s algorithm is a divide and conquer method for matrix multiplication that reduces the number of recursive multiplications from eight to seven, achieving a better asymptotic time complexity than the standard approach.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Divide: Split each n×n matrix into four n/2×n/2 submatrices.

  • Conquer: Recursively compute seven products of the submatrices instead of the eight required by the naive method.

  • Combine: Add and subtract the submatrices to assemble the final result from the seven products.

The seven products are: - P1 = (A11 + A22)(B11 + B22) - P2 = (A21 + A22)B11 - P3 = A11(B12 - B22) - P4 = A22(B21 - B11) - P5 = (A11 + A12)B22 - P6 = (A21 - A11)(B11 + B12) - P7 = (A12 - A22)(B21 + B22)

Then the result quadrants are: - C11 = P1 + P4 - P5 + P7 - C12 = P3 + P5 - C21 = P2 + P4 - C22 = P1 - P2 + P3 + P6

Recurrence and Complexity

The recurrence for the time complexity is: T(n) = 7T(n/2) + O(n^2)

The O(n^2) term accounts for the matrix additions and subtractions needed to form the submatrices and combine the results.

Applying the Master Theorem: - a = 7, b = 2, f(n) = O(n^2) - n^{log_b a} = n^{log_2 7} ≈ n^{2.807} - Since f(n) = O(n^{2}) is polynomially smaller than n^{log_2 7}, this is Case 1. - Therefore, T(n) = Θ(n^{log_2 7}) ≈ O(n^{2.81}).

Best, average, and worst case are all O(n^{log_2 7}) because the algorithm always divides the matrices into the same subproblems regardless of the input values.

Space complexity is O(n^2) for the recursive submatrix copies, plus O(log n) for the recursion stack, so the total is O(n^2). The input matrices themselves are not counted.

Approach Time Complexity Space Complexity When to Use
Naive matrix multiplication O(n^3) O(1) extra Small matrices, simplicity
Strassen’s algorithm O(n^{log_2 7}) ≈ O(n^{2.81}) O(n^2) extra Large matrices, asymptotic performance

Step-by-Step Example

Consider multiplying two 2×2 matrices: A = [[1, 2], [3, 4]], B = [[5, 6], [7, 8]]

  1. Divide: Split A and B into four 1×1 submatrices.

  2. A11 = 1, A12 = 2, A21 = 3, A22 = 4

  3. B11 = 5, B12 = 6, B21 = 7, B22 = 8

  4. Conquer: Compute the seven products.

  5. P1 = (1 + 4)(5 + 8) = 5 * 13 = 65

  6. P2 = (3 + 4)(5) = 7 * 5 = 35

  7. P3 = 1(6 - 8) = 1 * -2 = -2

  8. P4 = 4(7 - 5) = 4 * 2 = 8

  9. P5 = (1 + 2)(8) = 3 * 8 = 24

  10. P6 = (3 - 1)(5 + 6) = 2 * 11 = 22

  11. P7 = (2 - 4)(7 + 8) = -2 * 15 = -30

  12. Combine: Compute the result quadrants.

  13. C11 = 65 + 8 - 24 - 30 = 19

  14. C12 = -2 + 24 = 22

  15. C21 = 35 + 8 = 43

  16. C22 = 65 - 35 - 2 + 22 = 50

Result: [[19, 22], [43, 50]]

Comparison with Dynamic Programming

Divide and conquer solves independent subproblems that do not overlap. In Strassen’s algorithm, each recursive call works on distinct submatrices, so there is no benefit from memoization. Dynamic programming is better when subproblems overlap, as it avoids recomputing the same subproblem multiple times. For matrix multiplication, the subproblems are disjoint, so divide and conquer with the seven-product trick is optimal.

Code Example

def add(matrix_a: list[list[int]], matrix_b: list[list[int]]) -> list[list[int]]:
    return [[matrix_a[i][j] + matrix_b[i][j] for j in range(len(matrix_a))] for i in range(len(matrix_a))]

def subtract(matrix_a: list[list[int]], matrix_b: list[list[int]]) -> list[list[int]]:
    return [[matrix_a[i][j] - matrix_b[i][j] for j in range(len(matrix_a))] for i in range(len(matrix_a))]

def strassen_multiply(matrix_a: list[list[int]], matrix_b: list[list[int]]) -> list[list[int]]:
    """Multiply two square matrices using Strassen's divide and conquer algorithm."""
    n = len(matrix_a)
    if n == 0:
        return []
    if n % 2 != 0:
        raise ValueError("Matrix dimension must be a power of two.")
    if n == 1:
        return [[matrix_a[0][0] * matrix_b[0][0]]]

    mid = n // 2
    # Divide: split into quadrants
    a11 = [row[:mid] for row in matrix_a[:mid]]
    a12 = [row[mid:] for row in matrix_a[:mid]]
    a21 = [row[:mid] for row in matrix_a[mid:]]
    a22 = [row[mid:] for row in matrix_a[mid:]]
    b11 = [row[:mid] for row in matrix_b[:mid]]
    b12 = [row[mid:] for row in matrix_b[:mid]]
    b21 = [row[:mid] for row in matrix_b[mid:]]
    b22 = [row[mid:] for row in matrix_b[mid:]]

    # Conquer: recursively compute seven products
    p1 = strassen_multiply(add(a11, a22), add(b11, b22))
    p2 = strassen_multiply(add(a21, a22), b11)
    p3 = strassen_multiply(a11, subtract(b12, b22))
    p4 = strassen_multiply(a22, subtract(b21, b11))
    p5 = strassen_multiply(add(a11, a12), b22)
    p6 = strassen_multiply(subtract(a21, a11), add(b11, b12))
    p7 = strassen_multiply(subtract(a12, a22), add(b21, b22))

    # Combine: assemble the result quadrants
    c11 = add(subtract(add(p1, p4), p5), p7)
    c12 = add(p3, p5)
    c21 = add(p2, p4)
    c22 = add(subtract(add(p1, p3), p2), p6)

    # Merge quadrants into a single matrix
    result = [[0] * n for _ in range(n)]
    for i in range(mid):
        for j in range(mid):
            result[i][j] = c11[i][j]
            result[i][j + mid] = c12[i][j]
            result[i + mid][j] = c21[i][j]
            result[i + mid][j + mid] = c22[i][j]
    return result

# Example call: multiply two 2x2 matrices
# print(strassen_multiply([[1, 2], [3, 4]], [[5, 6], [7, 8]]))
# Expected output: [[19, 22], [43, 50]]

Common Pitfalls

  • Off-by-one errors when splitting matrices into quadrants.

  • Forgetting that Strassen’s algorithm requires the matrix dimension to be a power of two; pad with zeros if needed.

  • The overhead of matrix additions can make Strassen slower than naive for small n (typically n < 64).

  • Recursion depth is O(log n), which is safe, but submatrix copying uses O(n^2) space.

  • In interviews, be prepared to explain why the seven products are correct and how the combine step works.

13

How does divide and conquer compute a number's power?

Divide-and-conquer exponentiation, commonly called exponentiation by squaring, computes a power by halving the exponent recursively and combining the results. It reduces a power calculation from linear multiplication to logarithmic recursion depth.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, and Combine

For (x^n):

  1. Divide: Split the exponent into a quotient and remainder: [ n = 2q + r ] where (q = lfloor n/2 rfloor) and ® is either 0 or 1.

  2. Conquer: Recursively calculate (x^q).

  3. Combine: Square that result and multiply by (x) when the remainder is 1: [ x^n = (x^q)^2 times x^r ]

For example, (2^{10}) becomes:

[ 2^{10} = (2^5)^2,quad 2^5 = (2^2)^2 times 2,quad 2^2 = (2^1)^2 ]

Recurrence and Complexity

For a positive exponent (n), the recurrence is:

[ T(n) = T(lfloor n/2 rfloor) + O(1) ]

This fits Master Theorem Case 2 with (a=1), (b=2), and (f(n) = O(1) = Theta(n^{log_b a}) = Theta(1)). It gives (O(log n)) time under the usual fixed-size arithmetic model.

  • Best, average, and worst-case time: All are (O(log n)).

  • Auxiliary space: (O(log n)), including the recursion stack.

  • Input storage: The original input is not counted as additional space.

  • Zero exponent: Requires (O(1)) time and space.

  • Arithmetic precision: Arbitrarily large integer results are exact in Python, but floating-point results may lose precision.

Approach Time Auxiliary space When to use
Repeated multiplication (O(n)) (O(1)) Simple implementation with a small exponent
Divide and conquer (O(log n)) (O(log n)) Efficient recursive exponentiation
Iterative exponentiation by squaring (O(log n)) (O(1)) When minimizing recursion-stack space

This is a divide-and-conquer problem rather than dynamic programming because its recursive subproblems do not overlap. If the same subproblems were repeatedly requested, memoization would usually be preferable.

Example Walkthrough

Calculating power(2, 10):

Exponent Divide Combine
10 (10 = 2 times 5 + 0) ((2^5)^2 = 32^2 = 1024)
5 (5 = 2 times 2 + 1) ((2^2)^2 times 2 = 32)
2 (2 = 2 times 1 + 0) ((2^1)^2 = 4)
1 (1 = 2 times 0 + 1) ((2^0)^2 times 2 = 2)
0 Base case Returns 1

Code Example

def power(base: int | float, exponent: int) -> int | float:
    """Calculate a power using divide-and-conquer exponentiation."""
    if exponent == 0:
        return 1

    if exponent < 0:
        if base == 0:
            raise ZeroDivisionError("zero cannot have a negative exponent")
        return 1 / power(base, -exponent)

    # Divide: split the exponent into a quotient and remainder.
    quotient = exponent // 2
    remainder = exponent % 2

    # Conquer: recursively calculate the half-exponent power.
    half_power = power(base, quotient)

    # Combine: square the result and handle an odd exponent.
    result = half_power * half_power
    if remainder == 1:
        result *= base

    return result


print(power(2, 10))  # 1024
print(power(-2, 3))  # -8
print(power(2, 0))   # 1
print(power(2, -2))  # 0.25

Common Pitfalls

  • Forgetting the odd-exponent step: An odd exponent requires one additional multiplication by base.

  • Incorrect zero-base handling: 0 to the power 0 returns 1, while a negative exponent raises ZeroDivisionError.

  • Ignoring precision: Integer bases with nonnegative integer exponents retain exact Python integer results; floating-point calculations can introduce rounding errors.

  • Confusing it with dynamic programming: These recursive subproblems do not overlap, so memoization is unnecessary.

  • Common interview follow-ups: Ask for an (O(1))-space iterative version, modular exponentiation, overflow behavior in fixed-width languages, or a comparison with naive repeated multiplication.

14

How to solve Tower of Hanoi with divide and conquer

Divide and conquer solves Tower of Hanoi by recursively moving a tower of n - 1 disks, moving the largest disk once, and then recursively moving the smaller tower onto it. This produces the optimal sequence of 2^n - 1 moves.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, and Combine

For a tower of n disks from source to target using auxiliary:

  1. Divide: Split the problem into the largest disk and a tower of n - 1 disks.

  2. Conquer: Recursively move the n - 1 disks from source to auxiliary.

  3. Move the largest disk from source to target.

  4. Combine: Recursively move the n - 1 disks from auxiliary to target.

The base case is zero disks, which requires no moves. With one disk, only the direct move is needed.

Recurrence and Optimality

Let M(n) be the minimum number of moves:

  • M(0) = 0

  • M(n) = 2M(n - 1) + 1

Expanding the recurrence gives:

M(n) = 2^n - 1

Therefore, the time complexity is Θ(2^n) for best, average, and worst cases because the algorithm must explicitly produce that many moves.

The Master Theorem case is not applicable here: its standard form requires a subproblem size such as n / b, whereas Hanoi uses n - 1. A recursion-tree expansion or substitution is the correct analysis.

Space usage is:

  • Auxiliary space: Θ(n) for the recursion stack, excluding the input and returned moves.

  • Input space: Θ(1) for the disk count and three peg names.

  • Output space: Θ(2^n) because the result contains 2^n - 1 move strings.

  • Total space including output: Θ(2^n).

Example Walkthrough

For three disks from A to C, using B:

  1. Move disk 1 from A to C.

  2. Move disk 2 from A to B.

  3. Move disk 1 from C to B.

  4. Move disk 3 from A to C.

  5. Move disk 1 from B to A.

  6. Move disk 2 from B to C.

  7. Move disk 1 from A to C.

The result is 7 = 2^3 - 1 moves.

Comparison With Dynamic Programming

Approach Time Space When to use
Recursive divide and conquer Θ(2^n) Θ(n) stack, excluding output Generate the complete optimal move sequence
Bottom-up DP for move count Θ(n) Θ(n) table Calculate only the number of moves using one value per disk count
Memoized count DP Θ(n) Θ(n) memoization table Calculate only the number of moves while reusing M(n - 1)

The sequence generator does not maintain a memo table: it makes 2^(n+1) - 1 recursive calls in total and emits exactly 2^n - 1 moves, one per non-base-case call. More generally, if a variant has S distinct states, memoized state DP uses O(S) time and O(S) memoization space because each state is solved once. Memoization is preferable when a variant revisits identical states.

Code Example

def solve_tower_of_hanoi(
    number_of_disks: int,
    source: str = "A",
    auxiliary: str = "B",
    target: str = "C",
) -> list[str]:
    """Return an optimal Tower of Hanoi move sequence."""
    if number_of_disks < 0:
        raise ValueError("number_of_disks must be non-negative")
    if len({source, auxiliary, target}) != 3:
        raise ValueError("source, auxiliary, and target must be distinct")

    moves: list[str] = []

    def move(
        disks: int,
        from_peg: str,
        via_peg: str,
        to_peg: str,
    ) -> None:
        if disks == 0:
            return

        # Divide: move the smaller tower to the auxiliary peg.
        move(disks - 1, from_peg, to_peg, via_peg)

        # Conquer: move the largest disk to the target peg.
        moves.append(f"{from_peg} -> {to_peg}")

        # Combine: move the smaller tower onto the target peg.
        move(disks - 1, via_peg, from_peg, to_peg)

    move(number_of_disks, source, auxiliary, target)
    return moves


solution = solve_tower_of_hanoi(3)
print(solution)

# Expected output:
# ['A -> C', 'A -> B', 'C -> B', 'A -> C', 'B -> A', 'B -> C', 'A -> C']

Common Pitfalls

  • Off-by-one errors: Use zero disks as the base case; the one-disk case follows automatically.

  • Incorrect peg ordering: The first recursive move uses the target as the auxiliary peg, and the final recursive move uses the source as the auxiliary peg.

  • Invalid input: Reject negative disk counts and ensure all three pegs are distinct.

  • Recursion depth: The recursion depth is O(n). Python’s default recursion limit is approximately 1,000, so the recursive version needs a raised limit or an explicit stack for unusually large inputs.

  • Unnecessary output storage: If only the move count is needed, compute 2^n - 1 directly instead of generating the sequence.

  • Common follow-up: Be ready to explain why fewer than 2^n - 1 moves are impossible and how to implement the algorithm with an explicit stack.

15

How to solve the closest pair of points using divide and conquer

The divide-and-conquer closest-pair algorithm finds the closest two points in (O(n log n)) time by recursively splitting the points, solving each half, and checking a narrow strip around the split line. It avoids comparing all (O(n^2)) pairs.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Algorithm

First, sort the points by (x), and secondarily by (y). Each recursive call follows three steps:

  1. Divide: Split the points into two halves according to their (x)-coordinates.

  2. Conquer: Recursively find the closest pair in each half.

  3. Combine: Merge the halves by (y)-coordinate and examine points near the dividing line.

If the smaller distance found in either half is (d), any better cross-half pair must have both points within distance (d) of the dividing line. These points form a strip. Within the relevant (2d times d) region, geometric packing guarantees that each point needs to be compared with at most seven following points in (y)-sorted order.

This is not primarily a dynamic-programming problem because the two recursive subproblems are disjoint and do not overlap. If subproblems overlap, memoization would generally be preferable.

Complexity and Comparison

The recurrence is:

[ T(n) = 2T(n/2) + O(n) ]

The linear combine step merges the (y)-sorted halves and checks the strip. By the Master Theorem, this is Case 2, where (a=2), (b=2), and (f(n)=Theta(n)), giving (O(n log n)).

Approach Time Extra space When to use
Brute force (O(n^2)) (O(1)) Very small inputs or a simple baseline
Divide and conquer (O(n log n)) (O(n)) General-purpose closest-pair solution
  • Best-case time: (O(n log n))

  • Average-case time: (O(n log n))

  • Worst-case time: (O(n log n))

  • Auxiliary space: (O(n)), excluding the input and including the (O(log n)) recursion stack

  • Total space if the input is counted: (O(n))

Code Example

from math import inf, sqrt

Point = tuple[float, float]


def closest_pair(
    points: list[Point],
) -> tuple[float, tuple[Point, Point]] | None:
    """Return the closest Euclidean distance and pair, or None for fewer than two points."""
    ordered = sorted(points)

    if len(ordered) < 2:
        return None

    # Duplicate points immediately produce the minimum possible distance.
    for previous, current in zip(ordered, ordered[1:]):
        if previous == current:
            return 0.0, (previous, current)

    def merge_by_y(left: list[Point], right: list[Point]) -> list[Point]:
        """Merge two y-sorted point lists in linear time."""
        merged: list[Point] = []
        left_index = 0
        right_index = 0

        while left_index < len(left) and right_index < len(right):
            if left[left_index][1] <= right[right_index][1]:
                merged.append(left[left_index])
                left_index += 1
            else:
                merged.append(right[right_index])
                right_index += 1

        merged.extend(left[left_index:])
        merged.extend(right[right_index:])
        return merged

    def solve(
        segment: list[Point],
    ) -> tuple[float, tuple[Point, Point] | None, list[Point]]:
        count = len(segment)

        # Base case: compare every pair in a small segment.
        if count <= 3:
            best_distance_squared = inf
            best_pair: tuple[Point, Point] | None = None

            for first_index in range(count):
                for second_index in range(first_index + 1, count):
                    delta_x = segment[first_index][0] - segment[second_index][0]
                    delta_y = segment[first_index][1] - segment[second_index][1]
                    distance_squared = delta_x * delta_x + delta_y * delta_y

                    if distance_squared < best_distance_squared:
                        best_distance_squared = distance_squared
                        best_pair = (
                            segment[first_index],
                            segment[second_index],
                        )

            return (
                best_distance_squared,
                best_pair,
                sorted(segment, key=lambda point: point[1]),
            )

        middle = count // 2
        middle_x = segment[middle][0]

        # Divide
        left_segment = segment[:middle]
        right_segment = segment[middle:]

        # Conquer
        left_distance, left_pair, left_by_y = solve(left_segment)
        right_distance, right_pair, right_by_y = solve(right_segment)

        # Combine
        if left_distance <= right_distance:
            best_distance = left_distance
            best_pair = left_pair
        else:
            best_distance = right_distance
            best_pair = right_pair

        merged_by_y = merge_by_y(left_by_y, right_by_y)

        strip = [
            point
            for point in merged_by_y
            if (point[0] - middle_x) ** 2 <= best_distance
        ]

        # The geometric packing argument limits this to seven comparisons.
        for first_index in range(len(strip)):
            for second_index in range(
                first_index + 1,
                min(first_index + 8, len(strip)),
            ):
                delta_x = strip[first_index][0] - strip[second_index][0]
                delta_y = strip[first_index][1] - strip[second_index][1]

                if delta_y * delta_y > best_distance:
                    break

                distance_squared = delta_x * delta_x + delta_y * delta_y
                if distance_squared < best_distance:
                    best_distance = distance_squared
                    best_pair = (strip[first_index], strip[second_index])

        return best_distance, best_pair, merged_by_y

    distance_squared, pair, _ = solve(ordered)
    assert pair is not None
    return sqrt(distance_squared), pair


points: list[Point] = [(0, 0), (2, 0), (3, 0), (5, 0)]
print(closest_pair(points))
# Expected: (1.0, ((2, 0), (3, 0)))

Example Walkthrough

For [(0, 0), (2, 0), (3, 0), (5, 0)]:

  1. Divide: The split occurs at (x=3), producing [(0, 0), (2, 0)] and [(3, 0), (5, 0)].

  2. Conquer: Each half finds distance (2).

  3. Combine: The strip includes the points near (x=3). Comparing (2, 0) and (3, 0) finds distance (1), which becomes the final result.

Edge Cases and Best Practices

  • Empty input or one point: Return None because no pair exists.

  • Duplicate points: Return distance 0 immediately.

  • Negative coordinates: Work normally; sorting and distance calculations are unaffected.

  • Already sorted input: The initial sort leaves the order unchanged, and the result is unaffected.

  • Equal distances: Any one closest pair may be returned.

  • Collinear or same-(x) points: The strip logic handles them correctly.

  • Mutation: This implementation does not mutate the caller’s list.

Common Pitfalls and Interview Tips

  • Forgetting to sort by (x) before dividing or by (y) before merging.

  • Comparing every pair in the strip, which can destroy the (O(n log n)) bound.

  • Assuming a fixed number of strip comparisons without explaining the geometric packing argument.

  • Using squared distances inconsistently when applying the strip condition.

  • Failing to handle coincident points separately.

  • Forgetting that space complexity includes the recursion stack.

16

How do you find a majority element with divide and conquer?

A majority element is an element that appears more than n // 2 times in an array of length n. Divide and conquer splits the array into two halves, recursively finds candidate majority elements, and then verifies the candidates against the current range.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, and Combine

The algorithm follows the three Divide and Conquer steps:

  1. Divide: Split the current range at its midpoint into two non-overlapping ranges.

  2. Conquer: Recursively find a majority candidate in each half.

  3. Combine: Count each distinct candidate in the current range and return one that occurs more than half the time.

A child range may not have a majority even when the combined range does. Therefore, the combine step must verify candidates using the entire current range rather than merely choosing one child’s result.

Recurrence and Complexity

The recurrence is:

T(n) = 2T(n / 2) + O(n)

The O(n) term comes from counting candidates in the current range. This is Master Theorem Case 2, where a = 2, b = 2, and f(n) = Θ(n), giving:

T(n) = Θ(n log n)

Case Time Space
Best O(n log n) O(log n)
Average O(n log n) O(log n)
Worst O(n log n) O(log n)

The space complexity includes the O(log n) recursion stack. The input array is not counted, and the implementation uses indices rather than copying slices.

Comparison with Other Approaches

Approach Time Extra space When to use
Brute-force counting O(n²) O(1) For small arrays or baseline analysis
Divide and conquer O(n log n) O(log n) When practicing the requested D&C pattern
Boyer–Moore voting O(n) O(1) When any linear-time algorithm is allowed

Boyer–Moore is asymptotically better for this problem, but the implementation below uses Divide and Conquer as requested.

Code Example

from typing import Optional


def majority_element(values: list[int]) -> Optional[int]:
    """Return the element occurring more than half the time, or None."""

    def solve(left: int, right: int) -> Optional[int]:
        if left > right:
            return None

        if left == right:
            return values[left]

        # Divide: split the range into two non-overlapping subranges.
        middle = (left + right) // 2

        # Conquer: recursively find candidates in both halves.
        left_candidate = solve(left, middle)
        right_candidate = solve(middle + 1, right)

        # Combine: verify distinct candidates against the current range.
        candidates: list[int] = []
        for candidate in (left_candidate, right_candidate):
            if candidate is not None and candidate not in candidates:
                candidates.append(candidate)

        range_size = right - left + 1

        for candidate in candidates:
            occurrences = 0
            for index in range(left, right + 1):
                if values[index] == candidate:
                    occurrences += 1

            if occurrences > range_size // 2:
                return candidate

        return None

    return solve(0, len(values) - 1)


if __name__ == "__main__":
    result = majority_element([2, 2, 1, 1, 1, 2, 2])
    print(result)  # 2

Walkthrough

For [2, 2, 1, 1, 1, 2, 2]:

  1. The left half [2, 2, 1, 1] has no majority.

  2. The right half [1, 2, 2] has candidate 2.

  3. The combine step counts 2 across the complete array.

  4. It occurs 4 times, which is greater than 7 // 2 = 3.

  5. The algorithm returns 2.

Divide and Conquer vs. Dynamic Programming

D&C is appropriate when recursive subproblems are disjoint, as they are here: each recursive call works on a different index range. If the same subproblem is recomputed many times because states overlap, memoization is usually the better choice. Standard majority-element D&C does not need memoization.

Common Pitfalls

  • Strict majority: The condition is count > n // 2, not count >= n // 2.

  • Empty input: The function returns None without indexing the array.

  • One element: The base case returns that element.

  • Negative numbers: Values are compared directly, so negatives work normally.

  • No majority: Return None instead of returning an arbitrary candidate.

  • Do not mutate the input: The indexed implementation preserves the original array.

  • Verify candidates: A child range can lack a majority while the combined range has one.

17

How do you find the median of two sorted arrays?

The median of two sorted arrays can be found in logarithmic time by binary-searching for a partition where every element on the left is no greater than every element on the right. The left partition contains the lower-valued half of the combined elements, including one extra element when the total length is odd, so its maximum and the right partition’s minimum determine the median.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, and Combine

The algorithm follows the three divide-and-conquer steps:

  1. Divide: Conceptually split the combined sorted sequence into left and right partitions. Choose how many elements come from each input array.

  2. Conquer: Compare elements at the partition boundaries. If the partition is invalid, discard half of the possible choices and repeat.

  3. Combine: Once the partition is valid, combine the largest left-side value and smallest right-side value to calculate the median.

For candidate count (k = min(m,n)+1), the worst-case recurrence is:

[ T(k) = T(k/2) + Theta(1) ]

Here (a=1), (b=2), and (f(k)=Theta(1)=Theta(k^0)). In the common Master Theorem formulation, this is Case 2, giving (Theta(log k)) time.

The subproblems do not overlap: each comparison eliminates half of the remaining candidates. If a problem generated overlapping subproblems, memoization or dynamic programming would generally be more appropriate.

Why the Partition Works

Let array_one be the shorter array. The algorithm searches for an index i representing how many elements from array_one belong on the left. The corresponding index j in array_two is calculated so that the left partition contains:

left_size = (total_length + 1) // 2

The partition is valid when:

array_one[i - 1] <= array_two[j]
array_two[j - 1] <= array_one[i]

Once valid:

  • For an odd total length, the median is the largest value on the left.

  • For an even total length, the median is the average of the largest left value and smallest right value.

Complexity

Let (m) and (n) be the input lengths and (s=min(m,n)).

  • Best case: (O(1)), when the first tested partition is valid.

  • Average case: (O(log(s+2))) under the usual binary-search analysis.

  • Worst case: (O(log(s+2))).

  • Auxiliary space: (O(1)). There is no recursion stack, and the input arrays are not modified. Counting the input itself, total space is (O(m+n)).

Approach Time Extra Space When to use
Concatenate and sort (O((m+n)log(m+n))) (O(m+n)) Simple one-off implementation
Binary-search partition (O(log(s+2))) (O(1)) Efficient production solution

Code Example

def median_of_two_sorted_arrays(
    array_one: list[int], array_two: list[int]
) -> float:
    """Return the median of two nondecreasing integer lists."""
    if len(array_one) > len(array_two):
        array_one, array_two = array_two, array_one

    short_length = len(array_one)
    long_length = len(array_two)
    total_length = short_length + long_length

    if total_length == 0:
        raise ValueError("At least one array must contain an element")

    left_size = (total_length + 1) // 2
    low, high = 0, short_length
    negative_infinity = float("-inf")
    positive_infinity = float("inf")

    while low <= high:
        # Divide: choose how many elements from each array go on the left.
        i = (low + high) // 2
        j = left_size - i

        short_left = array_one[i - 1] if i > 0 else negative_infinity
        short_right = array_one[i] if i < short_length else positive_infinity
        long_left = array_two[j - 1] if j > 0 else negative_infinity
        long_right = array_two[j] if j < long_length else positive_infinity

        # Conquer: compare boundaries and eliminate half the candidates.
        if short_left <= long_right and long_left <= short_right:
            # Combine: derive the median from the valid partition.
            left_max = max(short_left, long_left)

            if total_length % 2 == 1:
                return float(left_max)

            right_min = min(short_right, long_right)
            return (left_max + right_min) / 2.0

        if short_left > long_right:
            high = i - 1
        else:
            low = i + 1

    raise ValueError("Inputs must be sorted in nondecreasing order")


if __name__ == "__main__":
    print(median_of_two_sorted_arrays([1, 3], [2, 4]))  # 2.5

For [1, 3] and [2, 4]:

  1. The required left partition contains two elements.

  2. The first candidate partition uses i = 1 and j = 1.

  3. The boundaries are valid: 1 <= 2 and 2 <= 3.

  4. The median is (2 + 3) / 2 = 2.5.

Common Pitfalls

  • Incorrect partition size: The left side must contain half the elements, with the extra element on the left for odd lengths.

  • Off-by-one errors: Carefully handle empty partitions and both array boundaries.

  • Wrong odd/even calculation: Odd totals return the middle value; even totals average two middle values.

  • Mutating input: This implementation only reads the arrays.

  • Ignoring empty input: Two empty arrays raise ValueError; one empty array works normally.

  • Special-value assumptions: Negative numbers and duplicates are supported because comparisons use ordinary numeric ordering.

  • Sortedness is a precondition: The function assumes nondecreasing input rather than validating every possible unsorted array.

  • Common follow-up: The same partition technique can find the k-th smallest element in two sorted arrays in (O(log(s+2))) time.

18

How does Divide & Conquer differ for External vs In-memory Sorting

Divide and Conquer is used by both in-memory and external sorting, but external merge sort changes the unit being sorted, the dominant resource, and the way sorted results are combined.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea: The Same Three Steps

Aspect In-memory merge sort External merge sort
Divide Recursively split the input into two halves. Partition the input into chunks that fit in RAM.
Conquer Recurse until each subproblem has at most one element. Sort each chunk in RAM and write the resulting sorted run to disk.
Combine Merge two sorted subarrays. Merge multiple sorted runs, usually with a k-way merge.

External sorting therefore remains divide and conquer; it changes the subproblem boundary from array halves to memory-sized chunks and makes disk I/O the primary concern.

Cost Model and Resources

  • In-memory sorting: The main costs are comparisons, data movement, and cache misses. Direct array access is O(1).

  • External sorting: The main cost is reading and writing blocks. Sequential I/O is much faster than random I/O, so minimizing complete passes is important.

  • Let N be the number of records, M the maximum number fitting in RAM, and P the number of records per I/O buffer or block.

  • A merge with k input buffers also needs an output buffer and a heap of size k; therefore k cannot simply equal M/P without accounting for the output buffer and other memory.

Recurrence and Complexity

  • In-memory merge sort: T(N) = 2T(N/2) + Θ(N). By Master Theorem Case 2, this gives Θ(N log N) comparisons in the best, average, and worst cases. It uses Θ(N) merge workspace plus a Θ(log N) recursion stack.

  • Balanced k-way merging: For fixed k, E(N) = kE(N/k) + Θ(N), also Master Theorem Case 2, giving Θ(N log N) comparison work. Run generation adds at most O(N log M) comparisons.

  • External I/O: With R = ⌈N/M⌉ initial runs, the number of merge passes is p = ⌈log_k R⌉ when R > 1, otherwise 0. Run generation reads and writes the data once, and each merge pass reads and writes it again. Total I/O is therefore Θ((N/P)(1 + p)).

  • The best, average, and worst external I/O counts are the same for fixed N, M, P, and k. CPU comparison work is Θ(N log N) on average and in the worst case; an adaptive internal sort can reduce the best-case run-generation work, while merge comparisons remain.

  • External sorting uses Θ(M) RAM and Θ(N) temporary disk space. These are auxiliary-space figures and exclude the original input; counting the input adds Θ(N) storage.

Divide and Conquer vs Dynamic Programming

Merge-sort subproblems are disjoint, so they do not overlap and no memoization is needed. Dynamic programming is preferable when recursive subproblems overlap and reuse the same results; external memo tables may also be expensive to access. Sorting is normally a divide-and-conquer problem rather than a dynamic-programming problem.

Practical Guidance

  • Double buffering overlaps reading the next block with processing the current block.

  • Replacement selection can produce longer initial runs, averaging about 2M records for randomly ordered input, thereby reducing merge passes.

  • Stability can be preserved by using a stable internal sort and resolving equal keys by earlier run order.

  • Parallelism may divide in-memory subproblems among workers or distribute external runs among nodes, but parallel sorting does not change the merge-pass cost model.

  • With 1 TB of data, a 1 GB run-generation limit, and 4 MB merge buffers, there are about 1000 initial runs. 256 buffers of 4 MB would take the whole 1 GB, so after the output buffer, heap and other overhead the fan-in is somewhat below 255; two merge passes are needed, in addition to run generation.

Common Pitfalls

  • Binary merging is valid but usually causes more passes than a higher-fan-in merge; it is not mandatory.

  • Forgetting the output buffer or heap can make the assumed fan-in k impossible.

  • Empty input produces no runs, one element needs no merge pass, and duplicate or negative keys require only the chosen comparator to handle them correctly.

  • Already sorted data may reduce comparisons with an adaptive internal sort but does not reduce external I/O passes.

  • For fault tolerance, checkpoint completed runs and merged outputs, then publish the final file atomically rather than regenerating all work.

19

How does Divide and Conquer work in the Cooley-Tukey FFT?

The radix-2 Cooley–Tukey FFT uses divide and conquer: it splits a length-(N) DFT into even- and odd-indexed DFTs, recursively solves them, and combines them with twiddle factors. The general Cooley–Tukey family recursively decomposes a transform using radices; for radix 2 and power-of-two (N), it changes a direct (O(N^2)) DFT into an (O(Nlog N)) FFT.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, and Combine

For an input (x) of length (N), where (N) is a power of two:

  1. Divide: Separate the samples into even-indexed and odd-indexed subsequences: [ E=[x_0,x_2,x_4,ldots], qquad O=[x_1,x_3,x_5,ldots] ]

  2. Conquer: Recursively compute the (N/2)-point DFTs (E[k]) and (O[k]).

  3. Combine: Use twiddle factors (W_N^k=e^{-i2pi k/N}) to construct the full transform: [ X[k]=E[k]+W_N^kO[k] ] [ X[k+N/2]=E[k]-W_N^kO[k] ]

The two subproblems contain disjoint samples, so their results are not recomputed.

Recurrence and Complexity

Each call creates two recursive problems of half the size and performs linear combining work:

[ T(N)=2T(N/2)+Theta(N) ]

Under the Master Theorem, this is Case 2 because (f(N)=Theta(N^{log_2 2})=Theta(N)). Therefore:

[ T(N)=Theta(Nlog N) ]

Measure Complexity Reason
Best-case time (O(Nlog N)) The same butterflies are performed regardless of input values
Average-case time (O(Nlog N)) Runtime does not depend on the input distribution
Worst-case time (O(Nlog N)) Recursion and butterfly operations are deterministic
Auxiliary space (O(N)) Copies, slices, intermediate results, and the recursion stack are included
Recursion stack (O(log N)) Each recursive call halves the input size
Caller-provided input Not counted The space figures describe auxiliary memory beyond the original sequence

A standard in-place iterative radix-2 FFT can use (O(1)) auxiliary space, excluding returned-output storage, and has no recursion stack.

Small Radix-2 Example

For (x=[1,2,3,4]):

  1. Divide into even samples [1, 3] and odd samples [2, 4].

  2. Conquer by computing their two-point DFTs:

  3. E = [4, -2]

  4. O = [6, -2]

  5. Combine:

  6. (X[0]=4+6=10)

  7. (X[1]=-2+(-i)(-2)=-2+2i)

  8. (X[2]=4-6=-2)

  9. (X[3]=-2-(-i)(-2)=-2-2i)

The result is [10, -2+2j, -2, -2-2j].

Comparison With Dynamic Programming

Classic divide-and-conquer subproblems generally do not overlap, so their results are not reused. FFT is a standard example because the even-indexed and odd-indexed transforms contain disjoint samples.

When recursive subproblems overlap and request the same results repeatedly, memoization or dynamic programming is usually more appropriate. For example, overlapping interval problems should use bottom-up dynamic programming or top-down memoization rather than plain recursion.

Code Example

from collections.abc import Sequence
from math import cos, pi, sin


def fft(
    values: Sequence[complex | int],
    *,
    inverse: bool = False,
) -> list[complex]:
    """Compute a radix-2 FFT or inverse FFT of a power-of-two length sequence."""
    size = len(values)

    if size == 0:
        raise ValueError("FFT input must not be empty.")
    if size & (size - 1):
        raise ValueError("Radix-2 FFT requires a power-of-two input length.")

    data = [complex(value) for value in values]
    sign = 1 if inverse else -1

    def transform(items: list[complex]) -> list[complex]:
        if len(items) == 1:
            return items

        half = len(items) // 2

        # Divide: separate even-indexed and odd-indexed samples.
        even_items = items[::2]
        odd_items = items[1::2]

        # Conquer: recursively transform both smaller sequences.
        even_result = transform(even_items)
        odd_result = transform(odd_items)

        # Combine: apply twiddle factors and form the butterfly pairs.
        combined = [0j] * len(items)
        for k in range(half):
            angle = sign * 2.0 * pi * k / len(items)
            twiddle = complex(cos(angle), sin(angle))
            twiddled_odd = twiddle * odd_result[k]

            combined[k] = even_result[k] + twiddled_odd
            combined[k + half] = even_result[k] - twiddled_odd

        return combined

    result = transform(data)

    # The inverse DFT requires division by N.
    if inverse:
        result = [value / size for value in result]

    return result


print(fft([1, 2, 3, 4]))
# Expected approximately: [(10+0j), (-2+2j), (-2+0j), (-2-2j)]

Common Pitfalls

  • Invalid length: This implementation rejects empty input and lengths that are not powers of two.

  • Incorrect twiddle sign: The forward transform uses a negative exponent; the inverse uses a positive exponent and divides by (N).

  • Off-by-one butterfly indexing: Each result pairs index k with k + half.

  • Input mutation: The implementation copies the input, so callers’ data is not modified.

  • Edge cases: A one-element input is valid. Duplicates, negative values, and already-sorted inputs are valid because sortedness is irrelevant. Disconnected graphs and cycles do not apply to FFT.

  • Numerical precision: Floating-point rounding errors accumulate for very large transforms, so high-precision or fixed-point arithmetic may be required.

  • Integer overflow: Python does not use fixed-width integers for these complex values. Fixed-point implementations in other languages must use sufficiently wide integer types.

  • Visited set: A visited set is not applicable because FFT follows a fixed recursive split that cannot cycle.

  • Typical follow-up: Interviewers may ask about non-power-of-two lengths, mixed-radix FFTs, zero-padding, Bluestein’s algorithm, numerical accuracy, or inverse-FFT normalization.

20

How to solve the Skyline Problem using divide and conquer?

The divide-and-conquer skyline merge recursively constructs the upper envelopes of two disjoint halves and then merges them. Treat each building as (left, right, height) with a half-open footprint [left, right); the result contains [x, height] points where the combined height changes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

The algorithm follows the three divide-and-conquer steps:

  1. Divide: Split the buildings into two approximately equal groups.

  2. Conquer: Recursively calculate each group’s skyline.

  3. Combine: Merge the two skylines by taking the maximum active height at every coordinate.

Because each half contains a disjoint set of buildings, these subproblems do not overlap.

For example, with buildings [(2, 9, 10), (3, 7, 15), (5, 12, 12)]:

Step Result
Base case: (2, 9, 10) [[2, 10], [9, 0]]
Base case: (3, 7, 15) [[3, 15], [7, 0]]
Base case: (5, 12, 12) [[5, 12], [12, 0]]
Merge the last two [[3, 15], [7, 12], [12, 0]]
Merge with the first [[2, 10], [3, 15], [7, 12], [12, 0]]

Correctness

  • Base case: One positive-height building produces its start point and the point where its height returns to zero. A zero-height building contributes no point.

  • Recursive step: Assuming both child skylines are correct, their combined height at any coordinate is the maximum of their heights.

  • Merge: The merge processes every child height change and retains a point only when the combined maximum changes. It therefore produces exactly the critical points of the combined skyline.

Complexity

The worst-case recurrence is:

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

The Θ(n) term is the cost of merging the child skylines. By the Master Theorem, Case 2, this gives T(n) = Θ(n log n).

Case Time Reason
Best Θ(n) Identical buildings keep every merged skyline constant-sized, though all leaves are still processed
Average O(n log n) upper bound A tighter average requires a specified input distribution
Worst Θ(n log n) Linear work occurs at each of Θ(log n) levels

Auxiliary space: O(n) in the worst case, excluding the input and returned result. It includes intermediate skylines and the O(log n) recursion stack. Best-case auxiliary space is O(log n) when intermediate skylines remain constant-sized. Including the input and result, total space is O(n) in the worst case.

Comparison with Other Approaches

Dynamic programming is not a natural fit because the recursive subproblems are disjoint. When the same subproblem would otherwise be recomputed, memoization is the better approach.

Approach Time Space When to use
Brute force: sort endpoints and scan every building per segment O(n²) O(n) Small inputs or verification only
Divide and conquer O(n log n) worst case O(n) auxiliary worst case General batch solution
Sweep line with a max-heap O(n log n) worst case O(n) When explicit interval events are convenient

Code Example

type Building = tuple[int, int, int]
type Skyline = list[list[int]]


def skyline(buildings: list[Building]) -> Skyline:
    """Return critical skyline points for [left, right) buildings."""

    for left, right, height in buildings:
        if left >= right:
            raise ValueError("Each building must satisfy left < right.")
        if height < 0:
            raise ValueError("Building height cannot be negative.")

    def solve(start: int, end: int) -> Skyline:
        if start > end:
            return []

        if start == end:
            left, right, height = buildings[start]
            if height == 0:
                return []
            return [[left, height], [right, 0]]

        middle = (start + end) // 2

        # Divide: select two disjoint groups of buildings.
        # Conquer: recursively construct each group's skyline.
        left_skyline = solve(start, middle)
        right_skyline = solve(middle + 1, end)

        # Combine: merge both skylines into their upper envelope.
        return merge_skyline(left_skyline, right_skyline)

    def merge_skyline(left_points: Skyline, right_points: Skyline) -> Skyline:
        merged: Skyline = []
        left_index = 0
        right_index = 0
        left_height = 0
        right_height = 0
        previous_height = 0

        while left_index < len(left_points) or right_index < len(right_points):
            if (
                right_index == len(right_points)
                or (
                    left_index < len(left_points)
                    and left_points[left_index][0] <= right_points[right_index][0]
                )
            ):
                x = left_points[left_index][0]
            else:
                x = right_points[right_index][0]

            # Apply all height changes occurring at this coordinate.
            if left_index < len(left_points) and left_points[left_index][0] == x:
                left_height = left_points[left_index][1]
                left_index += 1

            if right_index < len(right_points) and right_points[right_index][0] == x:
                right_height = right_points[right_index][1]
                right_index += 1

            current_height = max(left_height, right_height)

            # Keep only coordinates where the combined skyline changes.
            if current_height != previous_height:
                merged.append([x, current_height])
                previous_height = current_height

        return merged

    return solve(0, len(buildings) - 1)


example_buildings = [
    (2, 9, 10),
    (3, 7, 15),
    (5, 12, 12),
    (15, 20, 10),
    (19, 24, 8),
]

print(skyline(example_buildings))
# Expected: [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]

Common Pitfalls

  • Duplicate coordinates or buildings: Apply changes from both child skylines before calculating their maximum.

  • Empty input: Return an empty list without indexing the input.

  • One building: Include the transition back to height zero.

  • Invalid data: Reject reversed intervals and negative heights; zero-height buildings have no effect.

  • Negative coordinates: They are valid and require no special handling.

  • Input ordering: Unsorted and already sorted inputs work because the algorithm does not rely on ordering or modify the input.

  • Overlaps and gaps: Use the maximum height, and retain transitions to or from zero.

  • Common follow-up: Compare this approach with sorting buildings and sweeping with a max-heap.

21

How can recursive overhead be reduced in Divide & Conquer algorithms?

Recursive-call overhead can be reduced by replacing recursion with iteration, eliminating redundant subproblems, reducing allocations, and pruning unnecessary work. The most effective approach depends on whether the algorithm’s Divide, Conquer, and Combine phases can be expressed without a recursive call stack.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Main Strategies

  • Use iteration instead of recursion: Rewrite the algorithm with a loop or an explicit stack. This removes function-call and stack-frame overhead while preserving the same Divide and Conquer structure.

  • Use an explicit stack when necessary: If multiple branches must be postponed, store pending subproblems in a stack. The space remains proportional to the maximum number of pending states, often the recursion depth.

  • Eliminate overlapping subproblems: Memoization stores previously computed results. Traditional Divide & Conquer subproblems normally do not overlap; when they do, the algorithm is often better classified as dynamic programming.

  • Reduce per-call costs:

  • Pass indices instead of copying or slicing arrays.

  • Reuse buffers instead of allocating them in every call.

  • Combine computation into loops when separate recursive passes are unnecessary.

  • Prune unnecessary branches: Skip subproblems whose results cannot affect the answer, using bounds, feasibility checks, or dominance rules.

  • Use a small-input cutoff: For tiny inputs, switch to insertion sort, direct calculation, or another simpler algorithm instead of continuing to recurse.

  • Avoid relying on tail-call optimization: Python 3.12 does not provide guaranteed tail-call optimization, so tail recursion should be rewritten as a loop or an explicit-stack algorithm.

Recurrences and Complexity

A typical balanced Divide & Conquer algorithm has the recurrence:

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

The Θ(n) term represents the Combine phase. This is Master Theorem Case 2, giving Θ(n log n) total time. Recursion adds stack space:

  • Time: Θ(n log n) for balanced recursive implementations.

  • Auxiliary space: Θ(log n) for a balanced recursion stack.

  • Input counting: Input storage is excluded from auxiliary-space complexity.

These deterministic complexities do not differ between best, average, and worst input cases unless the underlying problem introduces data-dependent pruning.

An iterative equivalent generally retains the same asymptotic time complexity but removes stack-frame overhead. For exponentiation by squaring:

T(n) = T(⌊n/2⌋) + Θ(1), which solves to Θ(log n).

Comparing the Approaches

Approach Time Auxiliary Space When to Use
Balanced recursion Θ(n log n) Θ(log n) stack The recursive formulation is clearest
Iterative equivalent Θ(n log n) Potentially O(1) Call overhead is significant
Explicit-stack recursion Θ(n log n) O(h) for stack depth h Branches must be evaluated out of order
Memoized subproblems Θ(m) for m distinct states O(m) plus recursion stack Subproblems overlap
In-place Divide & Conquer Algorithm-dependent Often lower than copying Extra input-sized buffers are costly

Code Example

Exponentiation by squaring represents the recursive recurrence:

power(b, e) = power(b², ⌊e/2⌋) for even e.

The implementation below evaluates that recurrence iteratively:

def power(base: int, exponent: int) -> int:
    """Return base raised to a non-negative integer exponent."""
    if exponent < 0:
        raise ValueError("exponent must be non-negative")

    result = 1

    while exponent:
        # Divide: consume the current binary digit of the exponent.
        if exponent & 1:
            # Combine: include the current power when this digit is 1.
            result *= base

        exponent >>= 1

        # Conquer: prepare the squared power for the next digit.
        if exponent:
            base *= base

    return result


print(power(3, 4))  # 81

For power(3, 4), the steps are:

  1. Exponent 4 has binary representation 100.

  2. The first bit is 0, so result remains 1; the exponent becomes 2 and the base becomes 9.

  3. The next bit is 0, so result remains 1; the exponent becomes 1 and the base becomes 81.

  4. The final bit is 1, so result becomes 81.

Under the usual unit-cost arithmetic model, the function takes Θ(log n) time for exponent n > 0 and O(1) auxiliary space, excluding the input and growing output integer. It handles exponent 0 by returning 1, exponent 1 directly through the loop, and negative exponents by raising ValueError.

Common Pitfalls

  • Ignoring stack costs: A faster body cannot compensate for excessive recursion depth; use iteration when depth may exceed Python’s default limit of approximately 1,000.

  • Copying input data: Slicing inside every recursive call can change auxiliary space from O(log n) to O(n log n).

  • Applying memoization unnecessarily: Divide & Conquer subproblems usually do not overlap. Memoization is most useful when repeated states make dynamic programming appropriate.

  • Losing the algorithm structure: During optimization, preserve clear Divide, Conquer, and Combine phases and verify that pruning cannot discard a valid answer.

  • Ignoring edge cases: Handle empty ranges, single elements, duplicates, negative values, already-sorted inputs, cycles, or disconnected components when relevant to the particular algorithm.

22

How does tail recursion optimize Divide & Conquer algorithms?

Tail-call optimization (TCO) can reduce the recursion stack from O(h) to O(1) for eligible divide-and-conquer algorithms, where h is the recursion depth. It changes stack usage rather than the number of recursive calls or the algorithm’s asymptotic running time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Tail-Call Optimization Works

A recursive call is in tail position when its result is immediately returned and no combining, cleanup, or other pending work must occur after the call. A supporting compiler or runtime can then replace the current activation record with the callee’s record instead of retaining both.

The important requirements are:

  • Every reachable recursive call must be in tail position.

  • State required by the next call is supplied through parameters or an accumulator.

  • No work follows the recursive call.

  • An algorithm may contain several recursive branches, provided the call selected in each branch is in tail position.

TCO is a language or runtime feature, not a universal language guarantee. Python 3.12 does not optimize tail recursion, so an iterative version with O(1) auxiliary space or an explicit stack is preferable when recursion could become deep.

Divide, Conquer, and Combine

The three divide-and-conquer steps are:

  1. Divide: Split the problem into smaller subproblems.

  2. Conquer: Solve the subproblems, recursively when necessary.

  3. Combine: Merge or otherwise combine the subproblem results.

Binary search is an eligible example. It divides the search interval, recursively searches the only relevant half, and directly returns the result without later combining work. Its recurrence is:

T(n) = T(n/2) + O(1)

This is Master Theorem Case 1, producing O(log n) time because each call halves the remaining search range.

Binary-search form Best time Average time Worst time Auxiliary space When to use
Tail-call form O(1) O(log n) O(log n) O(1) In a runtime that guarantees TCO
Recursive form without TCO O(1) O(log n) O(log n) O(log n) When recursion depth is safely bounded

The auxiliary-space figures exclude the input but include the call stack where applicable.

Standard merge sort does not benefit from ordinary TCO because merging occurs after its recursive calls. Its recurrence is:

T(n) = 2T(n/2) + O(n)

This is Master Theorem Case 2 and gives O(n log n) best, average, and worst-case time. Its auxiliary space is O(n), including temporary arrays and the O(log n) recursion stack, while excluding the input.

Tail Recursion Versus Dynamic Programming

Divide and conquer normally creates non-overlapping subproblems, so the same subproblem is not repeatedly solved. TCO changes only how eligible calls consume stack space.

Dynamic programming or memoization is preferable when subproblems overlap because it avoids redundant computation. TCO and memoization are orthogonal: a tail-recursive algorithm can still memoize results, but memoization addresses repeated work while TCO addresses stack usage.

Practical Guidance and Edge Cases

  • Verify that the runtime actually guarantees TCO before relying on constant stack usage.

  • Rewrite every recursive path into tail position; optimizing only one branch does not guarantee O(1) stack space in the worst case.

  • In Python 3.12, prefer iteration or an explicit stack for potentially deep recursive algorithms.

  • Binary search requires sorted input. An unsorted input may produce an incorrect result; it does not cause undefined behavior in Python.

  • Empty and one-element inputs require correct interval boundaries.

  • Duplicate values may allow any matching index to be returned.

  • Negative values work when the data is sorted numerically.

  • Disconnected graphs and cycles are not applicable to binary search; they become relevant only when the divide-and-conquer algorithm traverses a graph.

Common Pitfalls

  • Assuming every language provides TCO—Python 3.12 does not.

  • Calling a recursive function tail-recursive when combining or cleanup work follows the call.

  • Claiming TCO reduces the number of recursive calls or improves asymptotic time complexity.

  • Ignoring call-stack space when reporting auxiliary complexity.

  • Forgetting to state whether input storage is included in the space analysis.

  • Overlooking that classic merge sort combines results after recursion and therefore is not tail-recursive in its standard form.

A common interview follow-up is to identify which divide, conquer, and combine operations prevent tail-call optimization, then derive the recurrence and space usage.

23

How do memoization and caching affect Divide & Conquer performance?

Memoization and caching can substantially improve Divide & Conquer when identical subproblems would otherwise be recomputed. For classical Divide & Conquer with non-overlapping subproblems, they usually add lookup and storage overhead without reducing the algorithmic work.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Affect the Algorithm

  • Memoization: A form of caching scoped to one computation. It stores a subproblem’s result under a key containing every input that affects that result.

  • Caching: A broader mechanism that may retain results across function calls or requests, subject to memory, eviction, and invalidation policies.

  • Cache hit: Returns a stored result rather than recomputing it.

  • Overhead: Every cache use requires key construction and lookup, plus additional memory for stored results.

Divide & Conquer has three steps:

  1. Divide: Split the input into smaller subproblems.

  2. Conquer: Recursively solve those subproblems.

  3. Combine: Combine their results into the final answer.

Memoization is most useful when two recursive conquer steps request the same subproblem. The first computes and stores it; later requests reuse that result.

Recurrences and the Master Theorem

Classical merge sort has:

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

Its recursive calls operate on different subarrays, so caching cannot eliminate either call. By the Master Theorem, Case 2, merge sort runs in Θ(n log n) time.

For a hypothetical algorithm whose two branches solve the identical subproblem:

  • Without caching: T(n) = 2T(n/2) + Θ(n), which is Master Theorem Case 2 and takes Θ(n log n).

  • With caching: the second branch becomes a hit, giving T(n) = T(n/2) + Θ(n). This is Master Theorem Case 3; the regularity condition holds, so the result is Θ(n).

Naive Fibonacci has T(n) = T(n - 1) + T(n - 2) + Θ(1), producing Θ(φⁿ) time, where φ ≈ 1.618. The Master Theorem does not directly apply because the subproblem sizes are not fixed fractions of n. Memoization computes only n + 1 distinct states, reducing the time to Θ(n).

Divide & Conquer Versus Dynamic Programming

Technique Recursive overlap Time Auxiliary space
Merge sort No Θ(n log n) in all cases: logarithmically many levels with linear work per level Θ(n): merge buffer, plus Θ(log n) stack
Naive Fibonacci Yes Θ(φⁿ) in all cases: the overlapping recursion tree expands exponentially Θ(n): recursion stack
Memoized Fibonacci Yes, but reused Θ(n) in all cases: each of the n + 1 states is computed once Θ(n): memo table plus recursion stack
Bottom-up Fibonacci No recursive calls Θ(n) in all cases: states are processed in one pass Θ(1): two rolling values

Classical Divide & Conquer normally has non-overlapping subproblems. When identical subproblems recur, memoization effectively converts the implementation into top-down dynamic programming. Bottom-up DP removes the recursion stack but may require a table unless only the most recent states are needed.

Performance and Space Considerations

  • For memoized Fibonacci with array-indexed storage, lookup is guaranteed O(1), so best, average, and worst-case time are all Θ(n).

  • A general hash-table cache has O(1) average-time lookup and O(n) worst-case lookup under pathological collisions; cache hits should not be described as guaranteed O(1).

  • A persistent cache can make a repeated identical request much faster, but a miss still performs the full computation. Total performance then depends on the request sequence and cache hit rate.

  • Auxiliary space includes the recursion stack but excludes the input by convention. Memoized Fibonacci uses Θ(n) auxiliary space; its Θ(1) input does not change the total. Merge sort excludes Θ(n) input space, while its auxiliary space is also Θ(n).

Common Pitfalls

  • Caching non-overlapping work: This adds overhead without eliminating recursive calls.

  • Incorrect cache keys: Omit any input that affects the result, and incorrect results may be returned.

  • Off-by-one errors: Base cases and cache-index bounds must be handled correctly; Fibonacci treats n = 0 and n = 1 as base cases.

  • Mutating inputs: If inputs change, cached keys or results must be invalidated.

  • Unbounded persistent caches: They can consume excessive memory and retain stale results.

  • Integer overflow: In fixed-width languages, use sufficiently wide types for indices and combined values.

  • Graph-like inputs: If recursion revisits nodes, maintain a visited set to avoid cycles.

  • Recursion depth: Memoized recursive Fibonacci can exceed Python’s default recursion limit near 1,000 frames; use bottom-up DP for large inputs.

  • Interview follow-up: Expect questions about subproblem overlap, the revised recurrence, cache keys, invalidation, and the change in stack and cache space.

24

Worst-case time complexity of Merge Sort, Quicksort, and Heapsort

In the worst case, Merge Sort and Heapsort run in O(n log n), while Quicksort runs in O(n²) when poor pivot selection repeatedly creates highly unbalanced partitions.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Complexity Comparison

Algorithm Best time Average time Worst time Auxiliary space, input excluded Reason
Merge Sort O(n log n) O(n log n) O(n log n) O(n), including O(log n) recursion stack Splitting and merging remain O(n) per level across O(log n) levels
Quicksort O(n log n) O(n log n) O(n²) O(log n) typical stack; O(n) worst-case recursive stack Balanced partitions give O(log n) levels; O(n) unbalanced partitions give n levels with O(n) work each
Heapsort O(n log n) O(n log n) O(n log n) O(1) Building the heap is O(n), followed by O(log n) work for each of O(n) removals

Merge Sort and Heapsort therefore have better worst-case guarantees. Quicksort is often faster in practice because of good locality and low overhead, especially with randomized or median-of-three pivot selection.

Divide, Conquer, and Combine

Merge Sort demonstrates all three steps:

  1. Divide: Split the array into two approximately equal halves.

  2. Conquer: Recursively sort both halves.

  3. Combine: Merge the sorted halves.

Its recurrence is:

T(n) = 2T(n/2) + O(n)

By the Master Theorem, Case 2, T(n) = O(n log n).

Quicksort follows a related pattern:

  • Divide: Partition around a pivot.

  • Conquer: Sort the partitions on either side.

  • Combine: The pivot is already in its final sorted position.

With an unbalanced pivot, its recurrence becomes:

T(n) = T(n - 1) + O(n)

This has the Master Theorem Case 1 pattern, where the nonrecursive work dominates, producing O(n²).

Heapsort is not a classic divide-and-conquer algorithm. It builds a max-heap in O(n), then repeatedly removes the maximum in O(log n).

Unlike dynamic programming, these divide-and-conquer subproblems do not overlap, so memoization is unnecessary. If subproblems repeatedly solve the same state, memoization or bottom-up dynamic programming is usually preferable.

Edge Cases and Space

  • All implementations correctly handle empty input, one element, duplicates, and negative numbers.

  • The implementations return new lists rather than mutating the input.

  • The Quicksort implementation uses an explicit stack, avoiding Python’s recursion-depth limit.

  • Its first-pivot policy demonstrates the worst case on already sorted or reverse-sorted input.

  • Merge Sort requires O(n) auxiliary storage even though its recursion depth is only O(log n).

  • Heapsort uses O(1) auxiliary storage when its output array is not counted as auxiliary space.

Common Pitfalls

  • Saying Quicksort is always O(n log n): that is not its worst-case guarantee.

  • Ignoring stack space when analyzing recursive Quicksort.

  • Using the first pivot on already sorted data, which creates the O(n²) case.

  • Adding memoization to Merge Sort or Quicksort: their subproblems do not overlap.

  • Forgetting that Heapsort’s heap construction is O(n), while each extraction is O(log n).

25

How do you determine Divide and Conquer space complexity?

The space complexity of a Divide and Conquer algorithm is determined from the maximum memory alive at one time, including temporary data and the recursion stack. The result should be labeled as either auxiliary space, which excludes the input, or total space, which includes it.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Space Complexity Model

Analyze peak memory rather than the total amount allocated over the program’s entire execution.

  • Auxiliary space: Extra memory excluding the input and any output that aliases the input.

  • Total space: Auxiliary space plus the input and separately allocated output.

  • Recursion stack: Include the maximum number of simultaneously active calls.

  • Temporary data: Count arrays, buffers, slices, tuples, and other values retained at the same time.

  • Allocation lifetime: Count memory that exists simultaneously, not memory allocated and released earlier.

If a function returns a new list while leaving the original input intact, that returned list is output space. If it sorts the original list and returns the same list, the output does not add another O(n) allocation.

Deriving the Space Recurrence

A Divide and Conquer algorithm has three phases:

  1. Divide: Split the problem into smaller subproblems.

  2. Conquer: Solve those subproblems, recursively when appropriate.

  3. Combine: Combine their results into the final result.

For each call, consider:

  • Space allocated by the current call, including local variables and temporary structures.

  • Space used by each child call.

  • Whether child calls execute sequentially or concurrently.

  • Whether child results or buffers remain alive simultaneously.

When child calls execute sequentially and release their memory before the next begins, their space costs are combined using the maximum. When their memory coexists, the costs are added. Parent-level allocations must also remain in the calculation until their children return.

For merge sort:

  • Time recurrence: T(n) = 2T(n/2) + O(n)

  • Master Theorem: This is Case 2, because f(n) = Θ(n), giving O(n log n) time.

  • Space: A shared merge buffer uses O(n), and the balanced recursion depth uses O(log n).

  • Auxiliary space: O(n) + O(log n) = O(n).

  • Total space: O(n) when the input is included because the output reuses the input list.

The per-level merge costs sum to O(n log n) cumulative copying work, not O(n log n) peak space. The implementation allocates only one O(n) buffer.

Common Algorithm Comparison

Algorithm Time: Best / Average / Worst Auxiliary space: Best / Average / Worst
Merge sort O(n log n) / O(n log n) / O(n log n) O(n) / O(n) / O(n)
Randomized recursive quicksort O(n log n) / expected O(n log n) / O(n²) O(log n) / expected O(log n) / O(n)
Recursive binary search O(log n) / O(log n) / O(log n) O(log n) / O(log n) / O(log n)
Iterative binary search O(log n) / O(log n) / O(log n) O(1) / O(1) / O(1)
  • Merge sort uses O(n) auxiliary memory for merging, while its balanced recursion contributes only O(log n) stack space.

  • Quicksort partitions in place, so its main space cost is the recursion stack: expected O(log n) and worst-case O(n) for sufficiently unbalanced partitions.

  • Binary search uses O(log n) stack space recursively but only O(1) auxiliary space when implemented iteratively.

Divide and Conquer Versus Dynamic Programming

Classic Divide and Conquer subproblems generally do not overlap, so each is computed independently. When subproblems do overlap, as in naive Fibonacci, memoization or dynamic programming is usually preferable because it avoids repeated computation.

For example:

  • Naive recursive Fibonacci uses O(n) recursion stack space and exponential time.

  • Bottom-up dynamic programming uses O(n) time and O(1) auxiliary space when only the final values are retained.

Common Pitfalls and Interview Tips

  • Forgetting the stack: Include O(log n) for balanced recursion and potentially O(n) for unbalanced recursion.

  • Counting cumulative work: O(n log n) copying work does not imply O(n log n) peak space.

  • Ignoring live temporaries: Include buffers and subproblem results that coexist.

  • Unclear input accounting: State whether the answer is auxiliary or total space.

  • Mutating the input: Copying the input first adds O(n) space.

  • Edge cases: Empty and one-element inputs still require an O(1) call frame; duplicates, negative values, and already sorted inputs do not change these asymptotic bounds.

  • Recursion limits: An unbalanced recursive implementation can approach Python’s default recursion limit, so an explicit stack may be preferable.

  • Typical follow-up: Interviewers commonly ask how memoization changes both the time and space complexity of overlapping subproblems.

26

Why is Divide and Conquer space-heavy, and how can it be reduced?

Divide and Conquer is not inherently space-heavy: its space usage depends on the recursion depth and the temporary data retained while combining subproblem results. Balanced recursion often uses O(log n) stack space, while operations such as merging can add O(n) auxiliary memory.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Space Is Used

The algorithm’s three steps are:

  1. Divide: Split the input into smaller subproblems.

  2. Conquer: Solve the subproblems recursively until reaching a base case.

  3. Combine: Merge or otherwise combine the subproblem results.

Space can be consumed in two ways:

  • Recursion stack: Every unfinished recursive call occupies stack space. A balanced binary recursion has depth O(log n), while an unbalanced recursion can have depth O(n).

  • Intermediate storage: Combine steps may allocate arrays, partitions, slices, or other temporary structures. Merge sort, for example, typically needs O(n) temporary storage even though its recursion stack is only O(log n).

Thus, Divide and Conquer is “space-heavy” only relative to an in-place or iterative alternative with smaller auxiliary-memory requirements.

Recurrence, Complexity, and Example

For merge sort:

  • Time recurrence: T(n) = 2T(n/2) + O(n)

  • Master Theorem: This is Case 2, because the work outside the recursive calls is linear, giving O(n log n) time.

  • Space recurrence: S(n) = S(n/2) + O(n), giving O(n) auxiliary space. This includes the O(log n) recursion stack and O(n) merge storage but excludes the caller-owned input.

Case Time Auxiliary space Reason
Best O(n log n) O(n) The balanced split and merge work remain linear per level
Average O(n log n) O(n) Merging processes all elements across O(log n) levels
Worst O(n log n) O(n) Balanced splitting keeps both recursion depth and temporary storage bounded

The auxiliary-space calculation includes the recursion stack. Counting the input and returned list as well still gives total space of O(n).

A small walkthrough is:

Step Values
Initial [5, 2, 4, 2, -1]
Divide [5, 2] and [4, 2, -1]
Conquer [2, 5] and [-1, 2, 4]
Combine [-1, 2, 2, 4, 5]

By contrast, an in-place quicksort needs only O(1) partition storage. Its recursive stack is O(log n) in the best and expected cases but O(n) in the worst case.

Comparison with Dynamic Programming

Approach Subproblem behavior Typical memory tradeoff
Divide and Conquer Subproblems generally do not overlap Temporary storage plus recursion stack
Memoized Dynamic Programming Subproblems may overlap, and computed states are cached A cache commonly proportional to the number of distinct states

Memoization is the better choice when the same subproblem would otherwise be solved repeatedly. It trades additional memory for reduced computation; it is not generally a way to reduce memory usage.

Strategies for Reducing Space

  • Partition or combine in place: Reuse the input array instead of creating new arrays. This can reduce auxiliary space to O(1) for partitioning operations.

  • Reuse buffers: Allocate one scratch buffer and use it across recursive calls instead of allocating separate buffers at each level.

  • Release intermediate results promptly: Merge or consume a subresult as soon as it is produced rather than retaining multiple complete results.

  • Eliminate unnecessary recursive frames: Process the smaller branch recursively and handle the larger branch in a tail position or loop. With suitable splits, this keeps the active stack at O(log n).

  • Use an explicit stack carefully: Iteration avoids Python’s recursion-depth limit, but storing every pending subproblem can consume more memory than the call stack.

  • Balance the recursion when possible: Balanced partitioning limits stack depth and prevents O(n) stack usage.

  • Avoid unnecessary memoization: Memoization saves time but generally increases auxiliary space.

Common Pitfalls

  • Reporting only O(log n) space for merge sort ignores its O(n) temporary storage.

  • Assuming every Divide and Conquer algorithm has logarithmic recursion depth.

  • Confusing auxiliary space with total space; auxiliary space includes the recursion stack but excludes the caller-owned input.

  • Believing that an explicit stack always uses less memory than recursion; it may retain many pending states.

  • Using deeply recursive Python code without considering Python’s default recursion limit.

  • Expecting interviewers to ask about the time recurrence, space recurrence, Master Theorem case, input mutation, and an in-place alternative.

27

How can Divide & Conquer algorithms be parallelized?

Divide-and-conquer parallelism executes independent subproblems concurrently and then combines their results. It is effective when the branches have little shared state, each branch contains enough work to justify scheduling overhead, and the combine step is cheap or independently parallelizable.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Pattern

A parallel divide-and-conquer algorithm retains the same three phases:

  1. Divide: Split the input into smaller subproblems.

  2. Conquer: Process independent subproblems concurrently on separate workers.

  3. Combine: Merge the subproblem results into the final answer.

Merge sort is a standard example: its two halves can be sorted concurrently before they are merged. Quicksort can similarly process independent partitions recursively. Binary search has less parallelism because each branch depends on the previous comparison, although speculative execution can evaluate possible branches.

Parallelization can use local threads, processes, GPUs, or distributed machines. The dividing line is usually determined by data locality, available processors, communication cost, and whether the combine operation can also be distributed.

Complexity and Parallel Cost

For merge sort, the sequential recurrence is:

T(n) = 2T(n/2) + O(n)

This is Master Theorem Case 2, yielding O(n log n) time because the linear combine work occurs at each of O(log n) levels.

Let p = min(max_workers, n):

Implementation Best, Average and Worst Elapsed Time Total Work Auxiliary Space
Sequential merge sort O(n log n) for every input order O(n log n) O(n)
Parallel chunks with serial combine O((n/p) log(n/p + 1) + n log(p + 1)) O(n log n) O(n)

The shown implementation parallelizes chunk sorting but performs the final multiway merge in the coordinator. Its auxiliary space includes chunk copies, serialized worker data, merge buffers, and the O(log n) recursion stack; the original input is not counted.

Parallel work is total CPU work, while parallel span is elapsed time with sufficient processors. A recursive merge-sort design that also parallelizes merges commonly has O(log² n) span using standard parallel merging; stronger sorting-network models can achieve O(log n) depth.

Speedup is S₁(n) / Sₚ(n) and is bounded by the processor count and Amdahl’s Law. Parallel efficiency is:

E = W / (p × T_span)

where W is work, p is the processor count, and T_span is elapsed time.

Relationship to Dynamic Programming

Divide-and-conquer subproblems usually do not overlap, so branches can be computed independently. Dynamic-programming subproblems often overlap and have dependencies between states; memoization prevents repeated computation, while synchronization and dependency management make naive parallelization harder. Some dynamic programs still parallelize independent states or wavefronts.

Code Example

This implementation divides the input into equal chunks, sorts them concurrently with recursive merge sort, and combines the sorted chunks using heapq.merge.

from concurrent.futures import ProcessPoolExecutor
from heapq import merge
from multiprocessing import get_context
from typing import Sequence


def _merge(left: list[int], right: list[int]) -> list[int]:
    """Merge two sorted lists."""
    merged: list[int] = []
    left_index = right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged


def _merge_sort(values: list[int]) -> list[int]:
    """Sort one chunk using divide and conquer."""
    if len(values) <= 1:
        return values.copy()

    # Divide: split into independent halves.
    midpoint = len(values) // 2
    left_values = values[:midpoint]
    right_values = values[midpoint:]

    # Conquer: solve both subproblems.
    left_sorted = _merge_sort(left_values)
    right_sorted = _merge_sort(right_values)

    # Combine: merge the sorted subproblem results.
    return _merge(left_sorted, right_sorted)


def parallel_merge_sort(
    values: Sequence[int],
    max_workers: int = 4,
) -> list[int]:
    """Sort integers using processes and divide and conquer."""
    if max_workers < 1:
        raise ValueError("max_workers must be at least 1")

    items = list(values)
    if len(items) <= 1:
        return items

    worker_count = min(max_workers, len(items))
    base_size, extra = divmod(len(items), worker_count)
    chunks: list[list[int]] = []
    start = 0

    for chunk_index in range(worker_count):
        chunk_size = base_size + (1 if chunk_index < extra else 0)
        chunks.append(items[start:start + chunk_size])
        start += chunk_size

    # The spawn context is safe across platforms.
    context = get_context("spawn")
    with ProcessPoolExecutor(
        max_workers=worker_count,
        mp_context=context,
    ) as executor:
        sorted_chunks = list(executor.map(_merge_sort, chunks))

    # Combine: merge all sorted chunks into the final result.
    return list(merge(*sorted_chunks))


if __name__ == "__main__":
    result = parallel_merge_sort([5, -2, 5, 0, 3], max_workers=2)
    print(result)  # [-2, 0, 3, 5, 5]

Walkthrough with two workers:

  1. Divide: [5, -2, 5, 0, 3] becomes [5, -2, 5] and [0, 3].

  2. Conquer: The workers produce [-2, 5, 5] and [0, 3].

  3. Combine: heapq.merge produces [-2, 0, 3, 5, 5].

Common Pitfalls

  • Python GIL: Pure-Python CPU-bound threads do not provide process-level parallelism in standard CPython; use processes instead. Native extensions may release the GIL and permit thread parallelism.

  • Small inputs: Process creation and serialization can dominate runtime, so use a sequential threshold.

  • Shared state: Avoid workers mutating shared data; pass inputs and return independent results.

  • Expensive combine: Parallelizing only the recursive calls may provide little benefit when merging dominates.

  • Edge cases: The implementation handles empty input, one element, duplicates, negative values, and already sorted input.

  • Follow-ups: Interviewers commonly ask about work versus span, Amdahl’s Law, granularity, and dynamic-programming dependencies.

28

Which divide and conquer algorithm benefits from distributed computing?

Distributed merge sort is a divide-and-conquer algorithm that benefits from distributed computing because partitions can be sorted concurrently and the sorted results can then be merged. It is most useful when parallel workers, data locality, or distributed storage make coordination worthwhile.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Distributed merge sort follows the three phases of divide and conquer:

  1. Divide: Split the input into approximately equal partitions and assign them to workers.

  2. Conquer: Each worker independently applies merge sort to its partition, producing a sorted sequence.

  3. Combine: Merge the sorted sequences into one sorted result. A heap-based merge can combine p sorted partitions in O(n log p) time when p ≥ 2.

For ordinary serial merge sort, the recurrence is:

T(n) = 2T(n/2) + O(n)

The two recursive calls divide the problem, while the O(n) term represents merging the sorted halves. This is Master Theorem Case 2, yielding O(n log n) time.

Distributed Execution and Complexity

For n elements and p balanced workers:

  • Best case: O(n log n) total work, because merge sort processes every level even when the input is already sorted.

  • Average case: O(n log n) total work.

  • Worst case: O(n log n) total work.

  • Parallel local-sorting time: O((n/p)(1 + log(n/p))), because each worker sorts a partition of approximately n/p elements.

  • Centralized combine time: O(n log(max(2, p))), because each output element may require comparing heap entries from up to p sorted partitions.

  • Serial CPU work: O(n log n), because distribution changes scheduling rather than eliminating the comparisons required by merge sort.

  • Communication: O(n) for the centralized variant when each partition is transferred to a worker and each sorted partition is returned once. A multi-level merge tree may transfer O(n log p) data.

The aggregate auxiliary space is O(n): parent-side partition and result copies use O(n), all workers together use O(n) transient space, and the merge heap uses O(p). Each worker’s recursion stack is O(1 + log(n/p)). These figures exclude the input; including it still gives O(n) total space.

Comparison with Other Approaches

Approach Time Space When to Use
Naive comparison sorting O(n²) O(1) auxiliary Small inputs or simple teaching examples
Serial merge sort O(n log n) O(n) auxiliary One machine with predictable performance
Distributed merge sort O(n log n) total work, with potentially lower wall-clock time O(n) aggregate Large datasets that can be partitioned across workers

Merge sort differs from dynamic programming because its recursive subproblems operate on disjoint partitions and do not overlap. If equivalent subproblems are solved repeatedly, dynamic programming with memoization is generally preferable.

Edge Cases

  • Empty input: Produces an empty result with no sorting work.

  • One element: Produces the same element without changing its order.

  • Duplicates: Preserves every occurrence and orders equal values consistently.

  • Negative numbers: Uses normal numeric ordering.

  • Already sorted input: Remains correct and still requires O(n log n) total work.

  • Disconnected graphs and cycles: Not applicable because merge sort processes values rather than traversing graphs.

Interview Tips

  • State the three phases explicitly: divide, conquer, combine.

  • Distinguish lower potential wall-clock time from unchanged total asymptotic work.

  • Mention partition balance, serialization, network latency, and merge-stage bottlenecks as practical limits.

  • Watch for off-by-one errors when splitting and merging partitions.

  • In languages with fixed-width integers, avoid overflow in midpoint calculations such as (left + right) // 2.

  • Do not mutate the caller’s input unless mutation is explicitly required.

  • A visited set is not applicable because this algorithm does not traverse graphs.

  • Expect follow-ups about distributed merge trees, external sorting, fault tolerance, and how to minimize network transfer.

29

How does randomized pivot selection improve Quicksort's average performance?

Randomized pivot selection makes Quicksort’s partitions approximately balanced on average, reducing the chance that a fixed input order repeatedly produces highly unbalanced partitions. A random pivot gives an expected time complexity of O(n log n) for any fixed input ordering, while the worst case remains O(n²).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Randomization Helps

Quicksort uses three steps:

  1. Divide: Select a pivot and partition elements into groups smaller than, equal to, and larger than the pivot.

  2. Conquer: Recursively sort the smaller and larger partitions.

  3. Combine: No merging is required because the array is partitioned and sorted in place.

With a fixed pivot rule, an adversarial or unfortunate input can produce unbalanced partitions. For example, always selecting the first element causes repeatedly unbalanced partitions on an already sorted array.

Selecting the pivot uniformly at random removes the input’s ability to consistently force bad splits. The pivot’s rank is uniformly distributed, so the expected recursion depth is logarithmic. Randomization does not guarantee balanced partitions; it makes poor partitions unlikely while preserving the possibility of a worst case.

Complexity and Recurrence

For distinct keys:

  • Best case: O(n log n), when partitions are consistently balanced.

  • Average case: O(n log n) expected over the algorithm’s random choices.

  • Worst case: O(n²), when pivots repeatedly produce extremely unbalanced partitions.

  • Expected auxiliary space: O(log n), including the recursion stack.

  • Worst-case auxiliary space: O(n), including the recursion stack.

The input array’s own storage is not counted because Quicksort sorts it in place.

For an ideal balanced split, the recurrence is:

T(n) = 2T(n/2) + O(n)

This is Master Theorem Case 2, giving O(n log n).

For random pivots, the more precise expected recurrence is:

E[T(n)] = (2/n) × Σ T(k) + O(n), for k from 0 to n-1

Solving this recurrence also gives expected O(n log n).

The implementation below uses three-way partitioning. Consequently, an array containing only duplicate values—such as [3, 3, 3, 3]—takes O(n) rather than degrading to O(n²).

Divide and Conquer vs. Dynamic Programming

Approach Subproblem behavior Typical use
Divide and conquer Subproblems are usually independent and do not overlap Quicksort, merge sort, Karatsuba multiplication
Dynamic programming Subproblems overlap and repeatedly need the same result Fibonacci numbers, shortest paths, knapsack

If Quicksort’s subproblems overlapped significantly, memoization would be preferable to recomputing them. For example, memoized Fibonacci calculation is dynamic programming, while recursively calculating it without caching is naive recursion.

Step-by-Step Example

Suppose the randomly selected pivot is 3:

Stage Array or partition
Initial array [5, 1, 3, 2, 4]
Partition around 3 Smaller: [2, 1], Equal: [3], Larger: [4, 5]
Sort smaller partition [1, 2]
Sort larger partition [4, 5]
Final array [1, 2, 3, 4, 5]

Only the smaller and larger partitions are processed recursively. The equal partition is already sorted.

Code Example

from random import randrange


def randomized_quicksort(values: list[int]) -> list[int]:
    """Sort values in place in ascending order and return the same list."""

    def sort(left: int, right: int) -> None:
        if left >= right:
            return

        # Divide: choose a uniformly random pivot and partition in three groups.
        pivot_index = randrange(left, right + 1)
        values[pivot_index], values[right] = values[right], values[pivot_index]
        pivot = values[right]

        lower = left
        current = left
        upper = right

        while current <= upper:
            if values[current] < pivot:
                values[lower], values[current] = values[current], values[lower]
                lower += 1
                current += 1
            elif values[current] > pivot:
                values[current], values[upper] = values[upper], values[current]
                upper -= 1
            else:
                current += 1

        # Conquer: recursively sort the smaller-than and greater-than partitions.
        sort(left, lower - 1)
        sort(upper + 1, right)

        # Combine: no merging is needed because partitioning was done in place.

    sort(0, len(values) - 1)
    return values


numbers = [3, -1, 3, 2, 3]
print(randomized_quicksort(numbers))  # [-1, 2, 3, 3, 3]

Common Pitfalls and Interview Tips

  • Worst-case recursion depth: The recursive version can reach O(n) depth and exceed Python’s default recursion limit of about 1,000. An explicit stack is safer for guaranteed support.

  • Input mutation: This implementation sorts the supplied list in place. Passing values.copy() preserves the caller’s list but requires an additional O(n) space.

  • Duplicates: Ordinary two-way partition schemes can degrade to O(n²) when all values are equal; three-way partitioning avoids that.

  • Edge cases: Empty and one-element lists are handled immediately. Negative values and already sorted inputs work correctly.

  • Expected versus guaranteed: Randomization provides expected O(n log n), not an unconditional guarantee for every execution.

  • Common follow-up: Interviewers may ask why the worst case remains O(n²), how to detect it, or how an introspective or median-of-three pivot strategy compares with random selection.

30

When is Divide & Conquer not the best algorithm choice?

Divide & Conquer is not the best choice when recursive subproblems overlap, when decomposition or combination costs more than a simpler method, or when the problem has a more natural greedy or direct solution. Standard Divide & Conquer expects independent subproblems; repeated work on the same inputs usually indicates that dynamic programming would be more appropriate.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

When Divide & Conquer Is a Poor Fit

  • Overlapping subproblems: Multiple recursive branches repeatedly calculate the same values. Dynamic programming with memoization or tabulation avoids this repeated work.

  • A simpler direct solution exists: If the result can be computed in one pass, recursion may add unnecessary overhead.

  • The greedy choice is optimal: Problems such as interval scheduling or Huffman coding often have efficient greedy algorithms, whereas Divide & Conquer would create unnecessary subproblems.

  • Combining subproblems is expensive: A recursive algorithm can spend more time merging results than an alternative formulation.

  • The problem does not decompose naturally: Forcing an artificial division into subproblems can make an algorithm harder to understand without improving its complexity.

  • The splits are badly unbalanced: If each level performs nearly linear work, the total time may be quadratic rather than logarithmic.

Fibonacci: The Overlapping-Subproblem Example

Fibonacci is defined by:

F(n) = F(n - 1) + F(n - 2)

with base cases:

F(0) = 0 and F(1) = 1

The three Divide & Conquer steps are:

  1. Divide: Split F(n) into F(n - 1) and F(n - 2).

  2. Conquer: Recursively calculate both smaller values.

  3. Combine: Add the two results.

The problem is that the subproblems overlap. Calculating F(5) initially requires F(4) and F(3). Calculating F(4) then requires F(3) again, while F(3) requires F(2) and F(1). Without memoization, the same Fibonacci values are repeatedly recalculated.

Memoization stores each computed value and reuses it on later calls. Bottom-up dynamic programming provides the same improvement by calculating the values iteratively in increasing order.

Recurrence and Complexity

The naive recurrence is:

T(n) = T(n - 1) + T(n - 2) + O(1)

The Master Theorem does not apply because the subproblem sizes do not decrease by a fixed fraction. This recurrence grows exponentially, with T(n) = O(φ^n), where φ is the golden ratio.

Approach Best time Average time Worst time Auxiliary space
Naive recursive Fibonacci O(φ^n) O(φ^n) O(φ^n) O(n) recursion stack
Memoized Fibonacci O(n) O(n) O(n) O(n) cache plus O(n) stack
Bottom-up Fibonacci O(n) O(n) O(n) O(n) table or O(1) with two variables

These bounds assume unit-cost arithmetic. The input is one integer and is not counted in auxiliary space.

Walkthrough for F(5)

  1. Divide F(5) into F(4) and F(3).

  2. Divide F(4) into F(3) and F(2).

  3. Divide the first F(3) into F(2) and F(1).

  4. Observe that F(2) is needed again while calculating F(3).

  5. Memoization computes F(2) once and reuses that result.

  6. Combining the results produces F(5) = 5.

Practical Decision Guide

A representative recurrence with expensive combination is:

T(n) = 2T(n/2) + O(n²)

This is Master Theorem Case 3, producing Θ(n²) time. With balanced recursion, the recursion stack uses Θ(log n) auxiliary space, excluding the input. If a direct scan can solve the same problem in Θ(n) time and O(1) auxiliary space, Divide & Conquer is not the better choice.

The key interview distinction is:

  • Divide & Conquer: Independent subproblems; combine their results after solving them.

  • Dynamic programming: Overlapping subproblems; reuse previously computed results.

  • Greedy algorithm: Repeatedly make a locally optimal choice that can be proven to produce a globally optimal result.

Common Pitfalls

  • Off-by-one errors: Preserve the correct base cases and stopping conditions.

  • Invalid input: Define whether negative values, empty collections, or other invalid inputs are rejected.

  • Recursion depth: Recursive algorithms may exceed Python’s default recursion limit of roughly 1,000; use bottom-up dynamic programming or an explicit stack when necessary.

  • Mutating input: State whether the algorithm rearranges or modifies the supplied data.

  • Repeated graph states: In graph-based Divide & Conquer problems, track visited nodes when recursion could revisit them.

  • Integer overflow: Fixed-width languages may overflow; Python integers are arbitrary-precision.

  • Interview follow-up: Be ready to identify overlapping subproblems, derive the recurrence, explain why the Master Theorem applies or does not apply, and compare Divide & Conquer with dynamic programming and greedy algorithms.

31

How is Divide and Conquer used outside computer science?

Divide and Conquer is a universal problem-solving paradigm that breaks complex problems into smaller, independent subproblems, solves them recursively, and combines the results. It appears naturally in mathematics, physics, engineering, biology, and organizational strategy wherever a large task can be decomposed into similar, manageable parts.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Mathematical Foundations

  • Numerical integration: Adaptive quadrature (e.g., Simpson’s rule) recursively subdivides intervals until the error estimate falls below a threshold.

  • Root finding: The bisection method halves the search interval each step — a direct D&C application on a continuous domain.

  • Polynomial multiplication: Karatsuba algorithm (1960) reduces O(n²) to O(n^log₂3) by splitting coefficients; Toom-Cook and FFT-based methods extend this further.

  • Matrix multiplication: Strassen’s algorithm (1969) divides matrices into blocks, using 7 multiplications instead of 8, achieving O(n^log₂7).

Scientific Computing & Physics

  • Fast Fourier Transform (FFT): Cooley-Tukey FFT recursively splits a DFT of size N into two DFTs of size N/2, enabling O(N log N) signal processing, spectral analysis, and convolution.

  • N-body simulation: Barnes-Hut algorithm groups distant particles into a single multipole approximation, reducing O(N²) force calculations to O(N log N).

  • Multigrid methods: For solving PDEs, problems are restricted to coarser grids (divide), solved there (conquer), and interpolated back (combine).

  • Quantum mechanics: Density matrix renormalization group (DMRG) iteratively truncates Hilbert space by dividing the system into blocks.

Engineering & Signal Processing

  • Image compression: JPEG uses DCT on 8×8 blocks (divide), quantizes coefficients (conquer), and entropy-codes (combine). Wavelet transforms (e.g., JPEG 2000) apply D&C across scales.

  • Circuit design: Hierarchical layout partitions a chip into modules, routes each recursively, then stitches interconnects.

  • Control systems: Model predictive control solves a large optimization by decomposing into smaller horizon subproblems (often via ADMM, a D&C-related method).

Business, Operations & Social Systems

  • Project management: Work Breakdown Structure (WBS) decomposes a project into deliverables, then work packages, then tasks — each estimated and scheduled independently.

  • Supply chain optimization: Large network flow problems are decomposed by region or product line (Dantzig-Wolfe decomposition), solved separately, and coordinated via master problem.

  • Organizational hierarchy: Companies divide into divisions → departments → teams → individuals; decisions propagate up (combine) and directives down (divide).

  • Parallel manufacturing: Assembly lines split a product into subassemblies built in parallel, then integrated.

Biological & Natural Systems

  • DNA sequencing: Shotgun sequencing fragments the genome, sequences reads independently, and assembles overlaps (divide → conquer → combine).

  • Protein folding: Domain-based prediction folds structural domains separately, then assembles tertiary structure.

  • Neural processing: The visual cortex processes features (edges, motion, color) in parallel pathways (divide), then integrates in higher areas (combine).

  • Evolutionary algorithms: Island models run independent subpopulations (divide), migrate best individuals (combine), mimicking D&C.

Interview Tips

  • Recognize the pattern: Interviewers may describe a real-world scenario (e.g., “how would you count votes in a national election?”) and expect you to name D&C: precincts → districts → states → national.

  • Distinguish from DP: If subproblems overlap (e.g., computing Fibonacci, shortest paths with shared subpaths), D&C repeats work — DP/memoization is correct.

  • Communication: Explicitly label the three phases — “First we divide the region into zones, then each team counts independently (conquer), finally we sum the totals (combine).”

  • Scalability talk: Mention that D&C enables parallelism (MapReduce, MPI) because subproblems are independent — a key reason it dominates distributed systems.

  • Edge cases in nature: Non-uniform subdivisions (adaptive mesh), load imbalance (some subproblems harder), and combine-step bottlenecks (Amdahl’s law) appear in every field.

Comparison: D&C vs. Dynamic Programming in Non-CS Contexts

Aspect Divide & Conquer Dynamic Programming
Subproblem overlap None (independent) Extensive (shared)
Memoization needed No Yes (critical)
Example FFT, mergesort Sequence alignment, Viterbi
Natural fit Hierarchical, recursive structure Sequential decisions with state
32

How does divide and conquer count inversions in an array?

An inversion is a pair of indices ((i,j)) where (i<j) but (a[i]>a[j]). Divide and conquer counts these pairs efficiently by recursively sorting two halves and counting inversions that cross between them during the merge.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm follows three steps:

  1. Divide: Split the array into two approximately equal halves.

  2. Conquer: Recursively count inversions entirely within each half.

  3. Combine: Merge the sorted halves and count inversions crossing between them.

During the merge, compare the next unmerged element from each sorted half:

  • If left_value <= right_value, take the left element. It cannot form an inversion with any remaining right-side element because those elements are at least as large.

  • Otherwise, take the right element. It is smaller than every remaining element in the left half, so it contributes mid - left inversions.

The <= comparison ensures equal values are not counted as inversions.

Recurrence and Complexity

The recurrence is:

[ T(n)=2T(n/2)+O(n) ]

  • 2T(n/2): recursively process both halves.

  • O(n): merge the halves and count cross-half inversions.

By the Master Theorem, this is Case 2, where (f(n)=Theta(n^{log_2 2})), giving:

  • Time: (Theta(nlog n)) in the best, average and worst cases. Sorted, reverse-sorted and random inputs have the same asymptotic cost.

  • Auxiliary space: (O(n)), including the working array and merge buffer. The recursion stack adds (O(log n)). The original input is not counted or modified.

Comparison with Brute Force and Dynamic Programming

Approach Time Extra space When to use
Check every pair (O(n^2)) (O(1)) Small arrays or conceptual explanation
Divide and conquer with merge sort (O(nlog n)) (O(n)) General inversion counting
Memoized dynamic programming Depends on the state design Usually (O(n)) or more When subproblems overlap and are recomputed

Divide and conquer subproblems generally do not overlap. If an algorithm repeatedly solves the same subproblem, memoization or another dynamic programming technique is usually preferable.

Example Walkthrough

For [3, 1, 2]:

Step Ranges or merge operation Inversions added
Divide [3, 1, 2] becomes [3] and [1, 2] —
Divide [1, 2] becomes [1] and [2] —
Combine Merge [1] and [2] 0
Combine Merge [3] with [1, 2] 2
Result — 2

The two inversions are ((3,1)) and ((3,2)), where each pair denotes the values at an earlier and later index.

Code Example

def count_inversions(values: list[int]) -> int:
    """Return the number of strict inversions without modifying values."""
    working = values.copy()
    buffer = [0] * len(working)

    def sort_and_count(left: int, right: int) -> int:
        # Base case: zero or one element cannot contain an inversion.
        if right - left <= 1:
            return 0

        # Divide: split this range into two halves.
        middle = left + (right - left) // 2

        # Conquer: count inversions within each half.
        left_inversions = sort_and_count(left, middle)
        right_inversions = sort_and_count(middle, right)

        # Combine: merge the sorted halves and count cross inversions.
        left_index = left
        right_index = middle
        write_index = left
        inversions = left_inversions + right_inversions

        while left_index < middle and right_index < right:
            if working[left_index] <= working[right_index]:
                buffer[write_index] = working[left_index]
                left_index += 1
            else:
                buffer[write_index] = working[right_index]
                inversions += middle - left_index
                right_index += 1
            write_index += 1

        while left_index < middle:
            buffer[write_index] = working[left_index]
            left_index += 1
            write_index += 1

        while right_index < right:
            buffer[write_index] = working[right_index]
            right_index += 1
            write_index += 1

        for index in range(left, right):
            working[index] = buffer[index]

        return inversions

    return sort_and_count(0, len(working))


print(count_inversions([3, 1, 2]))  # Expected output: 2
print(count_inversions([]))         # Expected output: 0
print(count_inversions([2, 2, 1]))   # Expected output: 2

Common Pitfalls

  • Off-by-one errors: The merge uses a half-open range [left, right), and cross inversions add middle - left_index, not middle - left_index + 1.

  • Incorrect duplicate handling: Use left_value <= right_value; otherwise equal elements produce false inversions.

  • Mutating the caller’s input: Copying the input makes the function safer. If mutation is acceptable, sorting directly in the caller’s list can avoid the extra copy.

  • Ignoring edge cases: Empty and single-element arrays return 0; duplicates and negative numbers are handled naturally.

  • Recursion depth: Recursion depth is (O(log n)), so it is normally safe below Python’s default recursion limit.

33

How can Divide and Conquer compute a convex hull efficiently?

A divide-and-conquer convex hull algorithm splits sorted points into two halves, recursively computes each half’s boundary, and linearly combines their lower and upper chains. It guarantees O(n log n) time, including sorting, and is preferable when the input contains many points.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

The algorithm maintains two ordered chains for each recursive subproblem:

  • Lower chain: boundary from the lexicographically smallest point to the largest point along the bottom.

  • Upper chain: boundary between the same endpoints along the top.

The orientation of three points is determined by the cross product:

cross(a, b, c) = (b.x - a.x)(c.y - a.y) - (b.y - a.y)(c.x - a.x)

A positive result is a counterclockwise turn, while a negative result is a clockwise turn. Collinear intermediate points are removed.

Divide, Conquer, and Combine

  1. Divide: Split the sorted points into two approximately equal halves.

  2. Conquer: Recursively compute the lower and upper chains for both halves.

  3. Combine: Concatenate corresponding child chains and rebuild each chain with a linear stack, removing turns that violate convexity.

Only a child’s lower-chain vertices can contribute to the parent’s lower chain; upper-chain vertices are handled analogously. Thus, the combine step processes at most O(n) points.

Compared with dynamic programming, these divide-and-conquer subproblems do not overlap. If an algorithm repeatedly solves the same subproblems, memoization would be preferable.

Approach Time Space When to use
Exhaustive candidate-edge checks O(n³) O(n) Small teaching examples
Gift wrapping O(nh) O(h) When the final hull is very small
Divide and conquer O(n log n) O(n) General, predictable performance

Here, h is the number of hull vertices.

Complexity

The recurrence is:

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

This is Master Theorem Case 2, because f(n) = Θ(n) = n^(log₂2). Therefore, T(n) = Θ(n log n). Sorting the points also costs Θ(n log n).

  • Best, average, and worst-case time: O(n log n).

  • Auxiliary space: O(n), excluding the original input but including temporary chains, the returned hull, and the O(log n) recursion stack.

Example Walkthrough

For (0,0), (0,2), (1,1), (2,0), (2,2):

State Lower chain Upper chain
Left half: (0,0), (0,2) (0,0), (0,2) (0,0), (0,2)
Right half after recursion (1,1), (2,0), (2,2) (1,1), (2,2)
Final combined chains (0,0), (2,0), (2,2) (0,0), (0,2), (2,2)

Joining the lower chain with the reversed upper chain produces the counterclockwise hull:

(0,0) → (2,0) → (2,2) → (0,2)

Code Example

Point = tuple[float, float]


def _cross(origin: Point, first: Point, second: Point) -> float:
    """Return the orientation of three points."""
    return (
        (first[0] - origin[0]) * (second[1] - origin[1])
        - (first[1] - origin[1]) * (second[0] - origin[0])
    )


def _build_chain(points: list[Point], *, upper: bool) -> list[Point]:
    """Build one convex chain from points already sorted lexicographically."""
    chain: list[Point] = []

    for point in points:
        while len(chain) >= 2:
            turn = _cross(chain[-2], chain[-1], point)

            if (turn >= 0 if upper else turn <= 0):
                chain.pop()
            else:
                break

        chain.append(point)

    return chain


def _hull_chains(
    points: list[Point], start: int, end: int
) -> tuple[list[Point], list[Point]]:
    """Recursively return lower and upper hull chains."""
    count = end - start

    if count == 0:
        return [], []
    if count == 1:
        return [points[start]], [points[start]]
    if count == 2:
        pair = [points[start], points[start + 1]]
        return pair, pair.copy()

    middle = start + count // 2

    # Divide: split the sorted points into two halves.
    # Conquer: recursively compute both chains for each half.
    left_lower, left_upper = _hull_chains(points, start, middle)
    right_lower, right_upper = _hull_chains(points, middle, end)

    # Combine: rebuild the parent's chains in linear time.
    lower = _build_chain(left_lower + right_lower, upper=False)
    upper = _build_chain(left_upper + right_upper, upper=True)

    return lower, upper


def convex_hull_dc(points: list[Point]) -> list[Point]:
    """Return the convex hull vertices in counterclockwise order."""
    unique_points = sorted(set(points))
    size = len(unique_points)

    if size == 0:
        return []
    if size == 1:
        return unique_points

    lower, upper = _hull_chains(unique_points, 0, size)

    # Combine the lower and reversed upper chains into one boundary.
    hull = lower[:-1] + list(reversed(upper))
    if hull[-1] == hull[0]:
        hull.pop()

    return hull


if __name__ == "__main__":
    points = [(0, 2), (0, 0), (1, 1), (2, 0), (2, 2)]
    print(convex_hull_dc(points))
    # Expected output: [(0, 0), (2, 0), (2, 2), (0, 2)]

Common Pitfalls and Interview Tips

  • Duplicate points: Remove duplicates before recursion so they do not create zero-length edges.

  • Collinear points: This implementation keeps only the two extreme endpoints when every point is collinear. State this policy during the interview.

  • Empty and single-point inputs: Return [] and the single point respectively.

  • Off-by-one errors: Carefully handle the midpoint, chain slices, and shared endpoints when joining the upper and lower chains.

  • Input mutation: sorted(set(points)) creates a new collection and leaves the caller’s list unchanged.

  • Integer overflow: In fixed-width languages, coordinate differences and cross products may require a wider integer type.

  • Typical follow-ups: Ask about the recurrence, why child hulls are sufficient, handling negative coordinates, producing either clockwise or counterclockwise order, and choosing divide and conquer over the O(nh) gift-wrapping algorithm.

34

Which real-world application benefits from divide and conquer?

A real-world example is sorting large transaction datasets for reconciliation or ranked reporting. Divide and conquer, particularly merge sort, reduces the sorting time from quadratic to (O(n log n)), making the improvement substantial for large collections.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Real-World Application

Suppose a payment platform must order millions of transactions by amount or timestamp. A naive comparison sort may require (O(n^2)) operations, whereas merge sort requires only (O(n log n)). The same principle appears in database sorting, batch-processing pipelines, and external sorting systems where records are merged from disk-backed runs.

Merge sort is also stable: records with equal keys retain their original relative order. This matters when transactions are ordered by multiple criteria, such as amount first and timestamp second.

Divide, Conquer, and Combine

The algorithm follows the three defining steps:

  1. Divide: Split the input into two approximately equal halves.

  2. Conquer: Recursively sort each half until each subproblem contains at most one element.

  3. Combine: Merge the two sorted halves into one sorted result.

For example, sorting [5, 2, 4, 6, 1, 3] proceeds as follows:

Stage Values
Divide [5, 2, 4] and [6, 1, 3]
Conquer left [2, 4, 5]
Conquer right [1, 3, 6]
Combine [1, 2, 3, 4, 5, 6]

Unlike dynamic programming, merge sort’s subproblems do not overlap: each recursive call operates on a separate portion of the input. If independently calculated subproblems repeatedly solve the same problem, memoized dynamic programming is usually more appropriate.

Complexity

The recurrence is:

[ T(n) = 2T(n/2) + O(n) ]

The (O(n)) term represents combining the sorted halves. By the Master Theorem, this is Case 2, so:

[ T(n) = O(n log n) ]

  • Best case: (O(n log n))

  • Average case: (O(n log n))

  • Worst case: (O(n log n))

  • Auxiliary space: (O(n)), excluding the input, for slices and merged lists

  • Recursion stack: (O(log n)), included within the total (O(n)) auxiliary space

Comparison

Approach Best time Average time Worst time Space When to use
Naive comparison sort (O(n)) (O(n^2)) (O(n^2)) (O(1)) Tiny arrays or simple educational examples
Merge sort (O(n log n)) (O(n log n)) (O(n log n)) (O(n)) Large datasets, stable sorting, external sorting

Common Pitfalls

  • Off-by-one errors: The base case must handle zero and one element before splitting.

  • Mutating the input: A typical merge sort implementation returns a new list, leaving the caller’s list unchanged.

  • Incorrect merge boundaries: Copy any unconsumed elements from either half after the main loop.

  • Stability errors: Compare with <=, not <, when equal values must retain their left-side order.

  • Unnecessary implementation in production: Python’s sorted() and list.sort() are usually faster and adaptive. Use custom merge sort when illustrating the algorithm, requiring stable custom logic, or implementing external merge sort.

35

How to solve maximum subarray with divide and conquer

The divide and conquer approach solves the maximum subarray problem by recursively splitting the array into halves, finding the maximum subarray in each half, and then combining results to account for subarrays crossing the midpoint.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm follows three steps: - Divide: Split the array into two halves at the midpoint. - Conquer: Recursively find the maximum subarray in each half. - Combine: Compute the maximum subarray that crosses the midpoint and take the largest of the three values.

The recurrence relation is T(n) = 2T(n/2) + O(n). The O(n) term comes from the linear scan to find the crossing subarray. By the Master Theorem, this is Case 2 because a = 2, b = 2, and f(n) = Θ(n^log_b a) = Θ(n). Thus the total time complexity is O(n log n).

Unlike dynamic programming, where subproblems overlap and memoization is used, divide and conquer here solves independent subproblems. For this specific problem, Kadane’s algorithm is the optimal O(n) solution, but divide and conquer is a general technique that can be adapted to variants where subproblems do not overlap.

Walkthrough Example

Consider the array [1, -2, 3, 4, -5, 6]: 1. Split at midpoint 2: left [1, -2, 3], right [4, -5, 6]. 2. Recursively solve left: maximum is 3 (subarray [3]). 3. Recursively solve right: maximum is 6 (subarray [6]). 4. Compute crossing subarray: start at 3, extend left to [-2, 1] and right to [4, -5, 6]. 5. Left crossing sum: 3 (max from 3 to 1 is 3). 6. Right crossing sum: 5 (max from 4 to 6 is 5). 7. Crossing total: 3 + 5 = 8. 8. Final result: max(3, 6, 8) = 8.

Complexity Analysis

  • Time: O(n log n) for best, average, and worst cases. The recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n) by the Master Theorem.

  • Space: O(log n) for the recursion stack. The input array is not counted.

Code Example

def max_subarray_divide_conquer(nums: list[int]) -> int:
    """Return the maximum sum of any contiguous subarray using divide and conquer.

    The array is split at the midpoint; the result is the maximum of the
    left half, the right half, and the maximum crossing subarray.
    """
    def helper(left: int, right: int) -> int:
        # Base case: a single element is the maximum subarray of itself.
        if left == right:
            return nums[left]
        # Divide: find the midpoint.
        mid = left + (right - left) // 2
        # Conquer: solve the left and right halves.
        left_max = helper(left, mid)
        right_max = helper(mid + 1, right)
        # Combine: find the maximum subarray crossing the midpoint.
        cross_max = max_crossing_subarray(nums, left, mid, right)
        return max(left_max, right_max, cross_max)

    def max_crossing_subarray(nums: list[int], left: int, mid: int, right: int) -> int:
        # Include the midpoint in the left sum.
        left_sum = nums[mid]
        current_sum = nums[mid]
        for i in range(mid - 1, left - 1, -1):
            current_sum += nums[i]
            left_sum = max(left_sum, current_sum)
        # Include the midpoint + 1 in the right sum.
        right_sum = nums[mid + 1]
        current_sum = nums[mid + 1]
        for j in range(mid + 2, right + 1):
            current_sum += nums[j]
            right_sum = max(right_sum, current_sum)
        return left_sum + right_sum

    if not nums:
        return 0
    return helper(0, len(nums) - 1)

# Example call:
# print(max_subarray_divide_conquer([1, -2, 3, 4, -5, 6]))  # Output: 8

Common Pitfalls

  • Off-by-one errors in the midpoint calculation can cause infinite recursion or missed elements.

  • Forgetting to handle the empty input case, which should return 0 or raise an error.

  • Ignoring the crossing subarray, which is essential for correctness.

  • Assuming the recursion depth is always safe; for very large arrays, Python’s default limit is sufficient because depth is log n.

36

Find the median of two sorted arrays using divide and conquer

The median of two sorted arrays can be found with divide and conquer by searching for a partition where every element in the combined left partition is no greater than every element in the combined right partition. The median is then the maximum element of the left partition, or the average of the lower and upper middle elements when the combined length is even.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Assume a and b are already sorted in ascending order. For a requested rank k:

  1. Divide: Binary-search the possible number of elements taken from the shorter array.

  2. Conquer: Compare the boundary elements of both partitions. If the partition is invalid, discard the impossible half of the search range and recurse.

  3. Combine: Once the partition is valid, the kth smallest element is the maximum of the two left-partition boundaries.

For an odd total length, find the middle element. For an even total length, find the lower and upper middle elements and average them.

The recurrence is:

T(s) = T(s / 2) + O(1)

Here, s is the number of possible partition positions. By the Master Theorem, this is Case 2 (since f(n) = Θ(1) = Θ(n^{log_b a}) with a=1, b=2), giving O(log s) time.

  • No overlapping subproblems: Unlike dynamic programming, the recursive calls here operate on disjoint search ranges, so memoization is not needed. When subproblems do overlap, dynamic programming with memoization is the better approach.

Complexity

Let m = len(a) and n = len(b).

  • Time: Best, average, and worst case are all O(log(min(m, n) + 2)). Each recursive step discards approximately half of the partition candidates.

  • Auxiliary space: O(log(min(m, n) + 2)), including the recursion stack. The input arrays are not counted and are not modified.

  • If one array is empty, the algorithm returns the appropriate element from the other array in O(1) time.

Approach Comparison

Approach Time Auxiliary space When to use
Concatenate and sort O((m + n) log(m + n)) O(m + n) Simple baseline or when arrays are not already sorted
Linear merge O(m + n) O(1) When a straightforward linear solution is sufficient
Partition binary search using divide and conquer O(log(min(m, n) + 2)) O(log(min(m, n) + 2)) When both arrays are sorted and efficient selection matters

Code Example

def median_two_sorted_arrays(a: list[int], b: list[int]) -> float:
    """Return the median of two nondecreasing integer arrays."""
    total = len(a) + len(b)

    if total == 0:
        raise ValueError("At least one array must contain an element")

    # Use the shorter array for the binary-searched partition.
    if len(a) > len(b):
        a, b = b, a

    m, n = len(a), len(b)

    def find_kth(k: int) -> int:
        # Valid partition positions for the shorter array.
        lower = max(0, k - n)
        upper = min(k, m)

        def search(left: int, right: int) -> int:
            if left > right:
                raise RuntimeError("No valid partition found")

            # Divide: choose the middle candidate partition.
            partition_a = (left + right) // 2
            partition_b = k - partition_a

            left_a = a[partition_a - 1] if partition_a > 0 else float("-inf")
            right_a = a[partition_a] if partition_a < m else float("inf")
            left_b = b[partition_b - 1] if partition_b > 0 else float("-inf")
            right_b = b[partition_b] if partition_b < n else float("inf")

            # Conquer: discard the half containing an invalid partition.
            if left_a > right_b:
                return search(left, partition_a - 1)

            if left_b > right_a:
                return search(partition_a + 1, right)

            # Combine: the kth element is the largest left boundary.
            return int(max(left_a, left_b))

        return search(lower, upper)

    lower_k = (total + 1) // 2
    upper_k = (total + 2) // 2

    lower_middle = find_kth(lower_k)

    if total % 2 == 1:
        return float(lower_middle)

    upper_middle = find_kth(upper_k)
    return (lower_middle + upper_middle) / 2.0


# Expected output: 2.5
print(median_two_sorted_arrays([1, 3], [2, 4]))

Walkthrough

For a = [1, 3] and b = [2, 4], the combined length is 4.

Rank Candidate partition in a Partition in b Result
k = 2 ‘[1] [3]‘ ‘[2] [4]‘ 2
k = 3 ‘[1, 3] []‘ ‘[2] [4]‘ 3

The lower middle value is 2, the upper middle value is 3, and the median is (2 + 3) / 2 = 2.5.

Common Pitfalls

  • Empty arrays: One empty array is supported, but two empty arrays have no median and should raise an error.

  • Odd versus even length: Even length requires two middle elements; averaging only one is incorrect.

  • Duplicates and negative numbers: The non-strict <= boundary comparisons handle both correctly.

  • Partition boundaries: Accessing partition - 1 or partition without checking whether the index is valid is a common off-by-one mistake.

  • Input requirements: The caller must provide sorted arrays; the algorithm does not sort them.

  • Interview follow-up: Be ready to explain why the maximum of the left boundaries is the kth element and why only one recursive branch is searched.

37

How do you implement divide-and-conquer merging for k sorted lists?

Divide and conquer merges the lists in balanced rounds: divide the problem into pairs of sorted subproblems, merge each pair with two pointers, and combine those results into the next round. The algorithm preserves duplicates, does not mutate the input lists, and runs in (O(N log k)) time when (N) is the total number of elements.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, and Combine

The three divide-and-conquer steps are:

  1. Divide: Treat each input list as an independent subproblem and group the subproblems into pairs.

  2. Conquer: Merge each pair of sorted lists using two pointers. The smaller current element is appended to the result, and its pointer advances.

  3. Combine: Collect the merged results into the next level. Repeat until only one list remains.

This implementation uses iterative rounds rather than recursion, so there is no recursion-depth risk.

Complexity

Let (N) be the total number of elements and (k) the number of lists.

  • Time: Best, average, and worst-case bounds are (O(N log k)) for (k geq 2), assuming every list is nonempty. Each level processes every element once, and there are (O(log k)) levels.

  • Single list: When (k = 1), the time is (O(N)) to copy the list.

  • Empty lists: If empty lists are allowed, list bookkeeping adds overhead, giving (O((N + k)log k)).

  • Space: (O(N + k)), including intermediate merged lists and the returned output. The input storage is not counted. The recursion stack is (O(1)) because the implementation is iterative.

For (k) equal-length lists of fixed length (m), (N=mk), and the recurrence is:

[ T(k)=2T(k/2)+Theta(mk)=2T(k/2)+Theta(k) ]

This is Master Theorem Case 2, because (f(k)=Theta(k)=Theta(k^{log_2 2})). It gives (O(klog k)), tight as (Theta(Nlog k)). With unequal list lengths, the general worst-case upper bound (O(Nlog k)) follows because each of the (O(log k)) levels copies at most (N) elements.

Walkthrough

For the lists [[1, 4, 7], [2, 5, 8], [3, 6, 9]]:

Round Lists being merged Result
1 [1, 4, 7] and [2, 5, 8] [1, 2, 4, 5, 7, 8]
1 [3, 6, 9] is carried forward [3, 6, 9]
2 [1, 2, 4, 5, 7, 8] and [3, 6, 9] [1, 2, 3, 4, 5, 6, 7, 8, 9]

Code Example

from typing import TypeVar

T = TypeVar("T")


def merge_two_sorted(left: list[T], right: list[T]) -> list[T]:
    """Merge two sorted lists into a new sorted list."""
    merged: list[T] = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged


def merge_k_sorted_lists(lists: list[list[T]]) -> list[T]:
    """Merge k sorted lists without mutating the input lists."""
    if not lists:
        return []

    current = list(lists)

    if len(current) == 1:
        return current[0].copy()

    # Divide: group the independent subproblems into pairs.
    while len(current) > 1:
        next_level: list[list[T]] = []

        for list_index in range(0, len(current), 2):
            left = current[list_index]

            if list_index + 1 == len(current):
                # Carry an unpaired list into the next level.
                next_level.append(left)
                continue

            right = current[list_index + 1]

            # Conquer: merge each pair using two pointers.
            next_level.append(merge_two_sorted(left, right))

        # Combine: merged subproblems form the next level.
        current = next_level

    return current[0].copy()


example = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print(merge_k_sorted_lists(example))
# Expected output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Comparison with Other Approaches

Approach Time Extra space When to use
Concatenate and sort (O(N log N)) (O(N)) Simple baseline when the lists’ sorted order is not exploited
Min-heap merge (O(N log k)) (O(k)), excluding output Many lists when low auxiliary memory is important
Pairwise divide and conquer (O(N log k)) (O(N + k)) When a clear balanced recursive structure is preferred

Unlike dynamic programming, the subproblems here do not overlap: each element belongs to exactly one list. Memoization would therefore add overhead without saving repeated work.

Common Pitfalls

  • Mutating the input: Reusing or sorting the original lists can surprise callers; the implementation creates new merged lists.

  • Empty input: [] returns [], while [[], []] also returns [].

  • One list or one element: [[5]] returns [5], and a single input list is copied rather than returned by reference.

  • Sorted-input precondition: Every input list must already be sorted; the algorithm does not sort an individual list.

  • Duplicates and negative values: The <= comparison preserves duplicates and correctly handles negative numbers.

  • Off-by-one errors: Check both pointers before accessing an element and append any remaining suffix.

  • Integer overflow: In languages such as Java or C++, use sufficiently large integer types when values can exceed the range of smaller types.

  • Follow-up questions: Interviewers commonly ask about the (O(N log k)) recurrence, heap-based merging, stability, and whether the algorithm can be parallelized.

38

How does divide and conquer solve maximum subarray

The Divide and Conquer approach solves the Maximum Subarray Problem by recursively splitting the array into halves, finding the maximum subarray in each half, and then combining results by checking the maximum subarray that crosses the midpoint. This yields a O(n log n) time solution.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Divide: Split the array into two halves at the midpoint.

  • Conquer: Recursively find the maximum subarray sum in the left half and the right half.

  • Combine: Find the maximum subarray sum that crosses the midpoint, then return the largest of the three values.

The key insight is that the optimal subarray either lies entirely in the left half, entirely in the right half, or crosses the midpoint.

Complexity Analysis

  • Time: T(n) = 2T(n/2) + O(n). By the Master Theorem, case 2 (a=2, b=2, f(n)=Θ(n)), the solution is O(n log n) for best, average, and worst cases.

  • Space: O(log n) for the recursion stack. The input array is not counted as extra space.

  • Comparison with Dynamic Programming: Kadane’s algorithm solves this in O(n) time and O(1) space. Divide and Conquer subproblems do not overlap, so memoization is not beneficial. When subproblems overlap, dynamic programming with memoization is the better approach.

Approach Time Space When to use
Brute force O(n^2) O(1) Small arrays, simplicity
Divide & Conquer O(n log n) O(log n) Teaching, parallelizable
Kadane’s (DP) O(n) O(1) Optimal, production

Step-by-Step Walkthrough

Consider nums = [1, -2, 3, 4, -1, 2]. 1. Split at mid index 2: left [1, -2, 3], right [4, -1, 2]. 2. Left half: recursively find max subarray. Split left at mid index 1: left-left [1, -2], left-right [3]. Max left sum is 3 (from [3]). 3. Right half: recursively find max subarray. Split right at mid index 4: right-left [4, -1], right-right [2]. Max right sum is 5 (from [4, -1, 2]). 4. Crossing subarray: compute max suffix sum of left half ending at mid (index 2) and max prefix sum of right half starting at mid+1 (index 3). Left suffix max = 3 (from [3]). Right prefix max = 5 (from [4, -1, 2]). Max crossing sum = 3 + 5 = 8 (from [3, 4, -1, 2]). 5. Result: max(3, 5, 8) = 8.

Code Example

def max_subarray_divide_and_conquer(nums: list[int]) -> int:
    """Return the maximum sum of a contiguous subarray using divide and conquer."""
    def helper(left: int, right: int) -> int:
        # Base case: single element
        if left == right:
            return nums[left]
        # Divide: find midpoint
        mid = (left + right) // 2
        # Conquer: recursively solve left and right halves
        left_max = helper(left, mid)
        right_max = helper(mid + 1, right)
        # Combine: find max crossing subarray
        # Left part of crossing subarray
        left_sum = float('-inf')
        current_sum = 0
        for i in range(mid, left - 1, -1):
            current_sum += nums[i]
            left_sum = max(left_sum, current_sum)
        # Right part of crossing subarray
        right_sum = float('-inf')
        current_sum = 0
        for i in range(mid + 1, right + 1):
            current_sum += nums[i]
            right_sum = max(right_sum, current_sum)
        cross_max = left_sum + right_sum
        # Return the maximum of the three
        return max(left_max, right_max, cross_max)

    if not nums:
        return 0
    return helper(0, len(nums) - 1)

# Example call
nums = [1, -2, 3, 4, -1, 2]
print(max_subarray_divide_and_conquer(nums))  # Output: 8

Common Pitfalls

  • Off-by-one errors: Ensure the crossing subarray includes the midpoint correctly.

  • Empty input: Handle empty arrays explicitly to avoid index errors.

  • All negative numbers: The algorithm correctly returns the maximum single element, not zero.

  • Recursion depth: For very large inputs, consider iterative alternatives or increase recursion limit.

  • Follow-up: Interviewers often ask for Kadane’s algorithm (O(n) time) as an optimal solution.

39

How do you construct a binary tree from preorder and inorder traversals?

The standard construction uses divide and conquer: select the next preorder value as the root, locate it in inorder to divide the tree into left and right subtrees, recursively build both, and combine them under the root. This approach assumes every node value is unique; duplicate values can make the tree ambiguous.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, and Combine

  • Divide: The first unprocessed value in preorder is the root. Its position in inorder separates the left subtree from the right subtree.

  • Conquer: Recursively apply the same process to the inorder segments before and after the root.

  • Combine: Attach the two constructed subtrees to the root.

A preorder-to-inorder index map allows each root lookup to take O(1) average time. Unlike dynamic programming, these recursive subproblems occupy disjoint inorder ranges and do not overlap, so memoization is normally unnecessary.

Recurrence and Complexity

If the left subtree contains k nodes, the expected recurrence is:

T(n) = T(k) + T(n - k - 1) + O(1)

For a balanced tree, this becomes T(n) = 2T(n/2) + O(1), which is Master Theorem Case 1, giving Θ(n). The general recurrence also totals Θ(n) expected work because every node is created once.

Case Time Reason
Best O(n) Every node is processed once.
Average/expected O(n) Dictionary lookup is O(1) on average.
Conservative worst case O(n²) Pathological dictionary hash collisions can make individual lookups O(n).

Space complexity: O(n), including the O(n) output tree and index map. The recursion stack is O(h), where h is the tree height in edges, and reaches O(n) for a completely skewed tree. Input storage is not counted.

Root lookup strategy Time Extra space When to use
Scan inorder for every root O(n²) worst case O(h) Simplicity only
Precomputed inorder index map O(n) expected O(n) Standard efficient solution

Walkthrough

Given preorder [3, 9, 20, 15, 7] and inorder [9, 3, 15, 20, 7]:

Step Preorder root Relevant inorder segment Result
1 3 [9, 3, 15, 20, 7] Root 3 splits into [9] and [15, 20, 7].
2 9 [9] 9 becomes the left child of 3.
3 20 [15, 20, 7] 20 becomes the right child of 3.
4 15 [15] 15 becomes the left child of 20.
5 7 [7] 7 becomes the right child of 20.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class TreeNode:
    value: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
    """Build a binary tree from unique preorder and inorder traversal values."""
    if len(preorder) != len(inorder):
        raise ValueError("Preorder and inorder must have the same length.")

    if not preorder:
        return None

    inorder_positions: dict[int, int] = {}
    for index, value in enumerate(inorder):
        if value in inorder_positions:
            raise ValueError("Tree values must be unique for unambiguous construction.")
        inorder_positions[value] = index

    if len(set(preorder)) != len(preorder):
        raise ValueError("Tree values must be unique for unambiguous construction.")

    if set(preorder) != set(inorder):
        raise ValueError("Preorder and inorder must contain the same values.")

    preorder_index = 0

    def build(left: int, right: int) -> TreeNode | None:
        nonlocal preorder_index

        if left > right:
            return None

        if preorder_index >= len(preorder):
            raise ValueError("Traversals do not form a valid binary tree.")

        root_value = preorder[preorder_index]
        root_position = inorder_positions.get(root_value)

        if root_position is None or not left <= root_position <= right:
            raise ValueError("Traversals do not form a valid binary tree.")

        # Divide: the root position splits the current inorder interval.
        preorder_index += 1

        # Conquer: build the left and right subtrees recursively.
        left_child = build(left, root_position - 1)
        right_child = build(root_position + 1, right)

        # Combine: attach both subtrees to the current root.
        return TreeNode(root_value, left_child, right_child)

    return build(0, len(inorder) - 1)


tree = build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
print(tree.value, tree.left.value, tree.right.value)
# Expected output: 3 9 20

Common Pitfalls

  • Duplicate values: The same traversals may describe multiple trees. The code rejects duplicates rather than choosing an arbitrary tree.

  • Incorrect boundaries: The inorder range is inclusive; the left child ends at root_position - 1, and the right begins at root_position + 1.

  • Repeated linear searches: Calling inorder.index(root_value) at every level changes expected time to O(n²).

  • Recursion depth: A skewed tree with more than roughly 1,000 nodes can exceed Python’s default recursion limit. Use an explicit-stack implementation for such inputs rather than relying on a larger recursion limit.

  • Mutating input: The implementation does not modify either traversal array.

  • Common follow-up: Interviewers may ask for duplicate handling, validation of malformed traversals, an iterative construction, or how to serialize the resulting tree back into preorder and inorder.

40

Build a binary tree from inorder and postorder traversal arrays

To construct a binary tree from inorder and postorder traversals, you use the last element of the postorder array as the root, locate it in the inorder array to split left and right subtrees, and recursively repeat the process.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm follows the three classic Divide & Conquer steps:

  • Divide: The last element of the current postorder range is the root. Find its index in the inorder range to determine the boundary between left and right subtrees.

  • Conquer: Recursively build the left subtree using the left inorder and postorder ranges, then build the right subtree using the right ranges.

  • Combine: Attach the returned left and right subtrees to the root node.

Example trace with inorder = [4, 2, 5, 1, 6, 3, 7] and postorder = [4, 5, 2, 6, 7, 3, 1]: 1. Root is 1 (last of postorder). Index in inorder is 3. 2. Left subtree: inorder[0..2] = [4, 2, 5], postorder[0..2] = [4, 5, 2]. 3. Right subtree: inorder[4..6] = [6, 3, 7], postorder[3..5] = [6, 7, 3]. 4. Recursion continues until ranges are empty.

Recurrence and Complexity

With a hash map for index lookups, the split step is O(1):

T(n) = 2T(n/2) + O(1)

This is Case 1 of the Master Theorem (a=2, b=2, f(n)=O(1) < n^{log_2 2} = n).

  • Time Complexity: O(n) average and worst case.

  • Space Complexity: O(n) auxiliary space for the hash map and recursion stack. The recursion stack is O(log n) for balanced trees and O(n) for skewed trees.

Comparison with Dynamic Programming

Divide & Conquer solves this because subproblems are disjoint; each node belongs to exactly one subtree range.

Approach Subproblems Overlap? Best For
Divide & Conquer Unique index ranges No This problem
Dynamic Programming Overlapping states Yes Problems like matrix chain

Code Example

from typing import List, Optional

class TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    """Build a binary tree from inorder and postorder traversal arrays."""
    if not inorder or len(inorder) != len(postorder):
        return None

    # Map values to indices for O(1) lookup
    index_map = {val: i for i, val in enumerate(inorder)}

    def helper(left: int, right: int, post_left: int, post_right: int) -> Optional[TreeNode]:
        # Base case: no elements to build from
        if left > right:
            return None

        # Divide: root is the last element of the current postorder range
        root_val = postorder[post_right]
        root = TreeNode(root_val)

        # Find root index in inorder to split left and right subtrees
        in_index = index_map[root_val]

        # Conquer: recursively build left and right subtrees
        left_size = in_index - left
        root.left = helper(left, in_index - 1, post_left, post_left + left_size - 1)
        root.right = helper(in_index + 1, right, post_left + left_size, post_right - 1)

        # Combine: root already has left and right attached
        return root

    return helper(0, len(inorder) - 1, 0, len(postorder) - 1)

# Example call:
# root = build_tree([4, 2, 5, 1, 6, 3, 7], [4, 5, 2, 6, 7, 3, 1])
# root.val == 1, root.left.val == 2, root.right.val == 3

Common Pitfalls

  • Off-by-one errors: Calculating the postorder boundaries for the right subtree is error-prone; verify with a small example.

  • Recursion depth: Python’s default recursion limit is ~1000. Skewed trees (e.g., sorted inputs) can exceed this.

  • Input validity: The arrays must have the same length and contain unique values; duplicates break the hash map lookup.

  • Naive slicing: Using list slicing inside the recursion copies arrays, degrading time complexity to O(n log n) for balanced trees and O(n²) for skewed trees.

41

Convert a Sorted Array to a Height-Balanced BST Using Divide and Conquer

A height-balanced binary search tree can be constructed from a sorted array by selecting the middle element as the root and recursively building its left and right subtrees. Choosing the midpoint at every level keeps the resulting subtree heights within one level of each other.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, and Combine

The divide-and-conquer process has three steps:

  1. Divide: Select the middle element of the current sorted range as the root.

  2. Conquer: Recursively construct the BST from the elements before and after the midpoint.

  3. Combine: Attach the two recursively constructed subtrees to the root.

Unlike merge sort, the combine step links existing trees rather than merging arrays.

For [-3, 0, 0, 4, 8], the recursive construction is:

Range Midpoint Value Left Range Right Range
0..4 0 0..1 3..4
0..1 -3 Empty 1..1
1..1 0 Empty Empty
3..4 4 Empty 4..4
4..4 8 Empty Empty

The resulting tree has five nodes and height 2 measured in edges. Its in-order traversal restores the original sorted sequence.

BST and Balance Properties

The implementation preserves the sorted order:

  • Values in the left subtree are less than or equal to the root.

  • Values in the right subtree are greater than or equal to the root.

  • Duplicate values are allowed in either subtree. If a strict BST is required, reject or remove duplicates first.

  • For every node, the heights of its left and right subtrees differ by at most one.

The relevant edge cases are handled as follows:

  • Empty input returns None.

  • A one-element input returns a single-node tree.

  • Duplicate values are preserved according to the midpoint placement.

  • Negative integers are accepted.

  • Already sorted input works normally, while an unsorted array raises ValueError.

Complexity

The construction recurrence is:

T(n) = 2T(n/2) + O(1)

Here, a = 2, b = 2, and f(n) = O(1), so Master Theorem Case 2 applies. The total construction time is O(n), with a tight bound of Θ(n).

  • Best case: O(n) because every element becomes a node.

  • Average case: O(n) because every element becomes a node regardless of the sorted input’s distribution.

  • Worst case: O(n) because every element becomes a node.

  • Auxiliary space: O(log n) for the recursion stack.

  • Output space: O(n) when the returned tree is included. The input array is not counted as auxiliary space.

Divide and Conquer Versus Dynamic Programming

Approach Subproblems Reuses Results? Typical Use
Divide and conquer Independent or non-overlapping No Merge sort, BST construction, Karatsuba multiplication
Dynamic programming Often overlapping Yes, through memoization or tabulation Fibonacci sequence, shortest paths, knapsack

Here, the left and right subproblems do not overlap. If an algorithm repeatedly solved the same subproblems, memoization would generally be preferable.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class TreeNode:
    value: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def sorted_array_to_bst(values: list[int]) -> TreeNode | None:
    """Build a height-balanced BST from a sorted list of integers."""
    for index in range(1, len(values)):
        if values[index] < values[index - 1]:
            raise ValueError("Input must be sorted in nondecreasing order")

    def build(left: int, right: int) -> TreeNode | None:
        if left > right:
            return None

        middle = (left + right) // 2
        root = TreeNode(values[middle])  # Divide: choose the midpoint

        left_root = build(left, middle - 1)  # Conquer: build left subtree
        right_root = build(middle + 1, right)  # Conquer: build right subtree

        root.left = left_root  # Combine: attach left subtree
        root.right = right_root  # Combine: attach right subtree
        return root

    return build(0, len(values) - 1)


def inorder_values(root: TreeNode | None) -> list[int]:
    """Return the tree's values using an in-order traversal."""
    result: list[int] = []

    def visit(node: TreeNode | None) -> None:
        if node is None:
            return
        visit(node.left)
        result.append(node.value)
        visit(node.right)

    visit(root)
    return result


def tree_height(root: TreeNode | None) -> int:
    """Return the tree height measured in edges."""
    if root is None:
        return 0
    return 1 + max(tree_height(root.left), tree_height(root.right))


example = sorted_array_to_bst([-3, 0, 0, 4, 8])
print(inorder_values(example))  # [-3, 0, 0, 4, 8]
print(tree_height(example))      # 2

Common Pitfalls

  • Off-by-one errors: Use left > right for the empty range and call build(0, len(values) - 1).

  • Duplicate values: Define whether equality is allowed on either or both sides of a node.

  • Incorrect midpoint: Prefer (left + right) // 2 to avoid floating-point arithmetic.

  • Mutating the input: The implementation only reads values; it does not sort or modify it.

  • Height convention: The example measures height in edges, so a tree containing one node has height 0.

  • Recursion depth: The recursion depth is O(log n), well below Python’s default recursion limit for realistic array sizes.

42

How do you convert a sorted linked list into a height-balanced BST?

The divide-and-conquer approach repeatedly selects the middle element of the sorted linked list as the root, recursively converts the left and right portions into subtrees, and links those subtrees to the root. Because each recursive split is based on list size, the resulting binary search tree (BST) is height-balanced.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, and Combine

The three steps are:

  1. Divide: Find the middle node of the current sorted-list segment. The nodes before it form the left subtree, and the nodes after it form the right subtree.

  2. Conquer: Recursively build the left and right subtrees.

  3. Combine: Assign the recursively built subtrees to the middle node’s left and right pointers.

For a segment containing n nodes, this implementation chooses the node at zero-based index n // 2. Therefore, the left subtree receives n // 2 nodes and the right subtree receives the remaining nodes.

Because the list is already sorted:

  • Every value in the left subtree is less than or equal to the root value.

  • Every value in the right subtree is greater than or equal to the root value.

  • Recursively applying the same rule preserves the BST property.

For example, with [1, 2, 3, 4, 5, 6, 7]:

Level List segment Selected root Remaining segments
1 [1, 2, 3, 4, 5, 6, 7] 4 [1, 2, 3], [5, 6, 7]
2 [1, 2, 3] 2 [1], [3]
2 [5, 6, 7] 6 [5], [7]
3 [1], [3], [5], [7] Each element Empty segments

The resulting tree has the root 4, children 2 and 6, and leaf nodes 1, 3, 5, and 7.

Complexity

Let T(n) be the time required to build the tree from n linked-list nodes.

  • Recurrence: T(n) = 2T(n/2) + O(n)

  • The O(n) term comes from traversing the linked-list segment to locate its midpoint.

  • By the Master Theorem, this is Case 2, so the result is O(n log n).

  • Best case: O(n log n)

  • Average case: O(n log n)

  • Worst case: O(n log n)

  • Auxiliary space: O(log n) for the recursion stack, excluding the input list and output tree.

  • Output space: O(n) for the resulting BST.

  • If the input is counted: O(n) total space.

The recursion depth is O(log n), so it does not approach Python’s default recursion limit for ordinary tree sizes.

Comparison with Dynamic Programming

Approach Subproblem behavior Typical use
Divide and conquer Subproblems generally do not overlap Merge sort and this linked-list-to-BST conversion
Dynamic programming with memoization Subproblems overlap and are recomputed without caching Fibonacci numbers, shortest paths, and many optimization problems

Memoization is unnecessary here because the left and right linked-list segments are disjoint.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class ListNode:
    value: int
    next: ListNode | None = None


@dataclass(slots=True)
class TreeNode:
    value: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def build_bst_from_sorted_list(head: ListNode | None) -> TreeNode | None:
    """Build a height-balanced BST from a sorted linked list."""

    def build(start: ListNode | None, count: int) -> TreeNode | None:
        if count <= 0:
            return None

        # Locate the middle node in the current linked-list segment.
        midpoint = start
        for _ in range(count // 2):
            midpoint = midpoint.next

        # Divide: define the left and right list segments.
        left_count = count // 2
        right_count = count - left_count - 1
        left_start = start
        right_start = midpoint.next

        # Conquer: recursively build both subtrees.
        left_root = build(left_start, left_count)
        right_root = build(right_start, right_count)

        # Combine: attach both subtrees to the middle node.
        return TreeNode(midpoint.value, left_root, right_root)

    list_length = 0
    current = head
    while current is not None:
        list_length += 1
        current = current.next

    return build(head, list_length)


def inorder_values(root: TreeNode | None) -> list[int]:
    """Return the BST values in sorted order."""
    if root is None:
        return []

    return (
        inorder_values(root.left)
        + [root.value]
        + inorder_values(root.right)
    )


head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
root = build_bst_from_sorted_list(head)
print(inorder_values(root))
# Expected output: [1, 2, 3, 4, 5]

Common Pitfalls

  • Off-by-one errors: Carefully define whether the midpoint is inclusive and calculate the right subtree size as count - left_count - 1.

  • Mutating the input: This implementation does not change the linked-list links; it creates new TreeNode objects from the list values.

  • Duplicate values: The code uses a non-strict BST convention, so equal values may appear in both subtrees. If duplicates must go only right, group equal keys or use a key-plus-tie-breaker comparison.

  • Empty or one-element lists: An empty list returns None; a one-element list produces a single-node tree.

  • Negative values and already sorted input: Both are handled naturally because ordering depends only on list position.

  • Cycles: The input is assumed to be a valid, acyclic sorted linked list. A cyclic list must be detected separately before conversion.

43

How can you implement a divide-and-conquer sort for a linked list?

Divide-and-conquer linked-list sorting is implemented with merge sort: split the list into two halves, recursively sort each half, and merge the sorted halves. This achieves O(n log n) time while using only O(log n) additional space for the recursion stack.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

The algorithm has three steps:

  1. Divide: Find the middle of the list using slow and fast pointers, then disconnect the two halves.

  2. Conquer: Recursively sort each half until each list contains at most one element.

  3. Combine: Merge the two sorted lists by repeatedly selecting the smaller head node.

The recurrence is:

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

The Θ(n) term comes from finding the midpoint and merging the lists. By the Master Theorem, this is Case 2, so the total running time is Θ(n log n).

Unlike dynamic programming, divide and conquer does not reuse overlapping subproblem results. Merge sort’s recursive subproblems are independent, so memoization is unnecessary. If subproblems overlap heavily, memoization or tabulation is usually more appropriate.

Complexity

Case Time Reason
Best O(n log n) Splitting and merging still process the list at each level
Average O(n log n) The recurrence is balanced regardless of input order
Worst O(n log n) Each level processes n nodes, and there are log n levels
  • Auxiliary space: O(log n), including the recursion stack.

  • Input storage: The input linked-list nodes are reused and are not counted as additional space.

  • The merge operation itself uses O(1) extra space because it only changes next pointers.

For comparison, a brute-force approach such as repeatedly selecting the minimum remaining node takes O(n²) time, while merge sort takes O(n log n).

Example Walkthrough

For 4 -> 1 -> 3 -> 2:

  1. Divide into 4 -> 1 and 3 -> 2.

  2. Recursively sort the halves into [1, 4] and [2, 3].

  3. Merge [1, 4] and [2, 3].

  4. The final list is 1 -> 2 -> 3 -> 4.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class ListNode:
    value: int
    next: ListNode | None = None


def sort_linked_list(head: ListNode | None) -> ListNode | None:
    """Sort a linked list in ascending order using merge sort."""
    if head is None or head.next is None:
        return head

    # Divide: find the midpoint and split the list into two halves.
    slow = head
    fast = head.next

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    left = head
    right = slow.next
    slow.next = None

    # Conquer: recursively sort both independent halves.
    left_sorted = sort_linked_list(left)
    right_sorted = sort_linked_list(right)

    # Combine: merge the two sorted halves.
    return merge_sorted_lists(left_sorted, right_sorted)


def merge_sorted_lists(
    left: ListNode | None,
    right: ListNode | None,
) -> ListNode | None:
    """Merge two sorted linked lists into one sorted linked list."""
    dummy = ListNode(0)
    tail = dummy

    while left is not None and right is not None:
        # Using <= keeps the merge stable for equal values.
        if left.value <= right.value:
            tail.next = left
            left = left.next
        else:
            tail.next = right
            right = right.next

        tail = tail.next

    # At most one list still contains nodes.
    tail.next = left if left is not None else right
    return dummy.next


# Example call
nodes = [ListNode(value) for value in [4, 1, 3, 2]]
for current, next_node in zip(nodes, nodes[1:]):
    current.next = next_node

result = sort_linked_list(nodes[0])
# Expected output: 1 -> 2 -> 3 -> 4

Common Pitfalls

  • Forgetting to disconnect the halves: After finding the midpoint, slow.next must be set to None; otherwise, merging can create cycles.

  • Using list.pop(0) or list.insert(0, x): These are O(n) operations and are unnecessary for linked-list sorting.

  • Converting the list to an array: This adds O(n) auxiliary space and hides the linked-list pointer manipulation being tested.

  • Ignoring duplicate values: The implementation uses <= during merging, making the sort stable.

  • Handling edge cases: Empty lists, single nodes, duplicate values, negative values, and already sorted lists are supported without special cases.

  • Interview follow-up: Be ready to explain why the midpoint is found with two pointers, why the merge is O(n), and why the recursion depth is only O(log n).

44

How do you search a 2D Matrix II with divide and conquer?

A divide-and-conquer search for a 2D Matrix II divides the matrix’s row range, searches the middle row with binary search, and recursively or iteratively examines the remaining row ranges. It exploits the fact that every row and every column is sorted in ascending order.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

Assume an m × n rectangular matrix where:

  • Every row is sorted from left to right.

  • Every column is sorted from top to bottom.

The algorithm uses three steps:

  1. Divide: Select the middle row of the current row interval.

  2. Conquer:

  3. If target is smaller than the middle row’s first element, search only the upper half. Lower rows have first elements at least as large.

  4. If target is larger than the middle row’s last element, search only the lower half. Upper rows have last elements no larger.

  5. Otherwise, binary-search the middle row. If it is absent, both remaining halves may contain the target.

  6. Combine: Treat a match in any searched region as success.

For m rows and n columns, the balanced recurrence is:

T(m, n) = 2T(m / 2, n) + O(log n)

For fixed n, this is Master Theorem Case 1, giving O(m log n) time.

Code Example

The implementation uses an explicit stack rather than recursion, avoiding Python’s recursion-depth limit for matrices with many rows.

from bisect import bisect_left


def search_matrix_ii(matrix: list[list[int]], target: int) -> bool:
    """Search a rectangular row- and column-sorted matrix using divide and conquer."""
    if not matrix or not matrix[0]:
        return False

    row_count = len(matrix)
    column_count = len(matrix[0])

    if any(len(row) != column_count for row in matrix):
        raise ValueError("Matrix rows must all have the same length")

    # Explicit stack of row intervals still to search.
    pending: list[tuple[int, int]] = [(0, row_count - 1)]

    while pending:
        top, bottom = pending.pop()
        if top > bottom:
            continue

        # Divide: choose the middle row.
        middle = (top + bottom) // 2
        row = matrix[middle]
        first = row[0]
        last = row[-1]

        if target < first:
            # Conquer: only the upper half can contain the target.
            pending.append((top, middle - 1))

        elif target > last:
            # Conquer: only the lower half can contain the target.
            pending.append((middle + 1, bottom))

        else:
            # Conquer: the target is within this row's value range.
            index = bisect_left(row, target)
            if index < column_count and row[index] == target:
                return True

            # Combine: search both remaining row ranges.
            pending.append((middle + 1, bottom))
            pending.append((top, middle - 1))

    return False


matrix = [
    [1, 4, 7, 11],
    [2, 5, 8, 12],
    [3, 6, 9, 16],
    [10, 13, 14, 17],
]

print(search_matrix_ii(matrix, 13))  # Expected output: True

Complexity

Approach Time Auxiliary space When to use
Brute-force scan O(mn) O(1) Simple implementation or unsorted data
Row-range divide and conquer O(m log n) O(log m) Required D&C solution; avoids scanning every cell
Staircase search O(m + n) O(1) Fastest general solution, but it is not divide and conquer

For the implemented algorithm:

  • Best case: O(log n) when the target is found in the first inspected row.

  • Average case: Depends on the input distribution; O(m log n) is the safe bound without further assumptions.

  • Worst case: O(m log n), because each row may be binary-searched at most once.

  • Auxiliary space: O(log m) for the explicit stack; O(1) for each binary search.

  • Including the input: O(mn + log m) space.

Walkthrough

For target = 13:

  1. The initial row interval is rows 0..3; the middle row is row 1, containing [2, 5, 8, 12].

  2. Since 13 > 12, the upper half is discarded.

  3. The next interval is rows 2..3; row 2 is [3, 6, 9, 16]. The target is within its range but is not present.

  4. The remaining lower interval contains row 3, [10, 13, 14, 17], where binary search finds 13.

Common Pitfalls

  • Empty input: The function returns False for an empty matrix or a matrix with no columns.

  • Rectangularity: Every row must have the same length; jagged matrices violate the Matrix II assumptions.

  • Duplicates and negative numbers: Comparison and bisect_left handle both correctly.

  • Already sorted input: This is a required precondition, not an edge case requiring special handling.

  • Mutating input: The algorithm does not modify the matrix.

  • One-element matrices: They work with the same logic.

  • Disconnected graphs and cycles: These concepts do not apply to matrix searching.

  • Dynamic programming: D&C subproblems here do not overlap; memoization is unnecessary. If repeated states occur in another formulation, memoization is usually preferable.

45

How can divide and conquer count smaller numbers after each array element?

Use a modified merge sort to count, for each position, how many later elements are strictly smaller. The divide-and-conquer method recursively sorts two halves and counts cross-half pairs while merging them, achieving (O(n log n)) time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm follows the three standard divide-and-conquer steps:

  1. Divide: Split the array into two halves.

  2. Conquer: Recursively count smaller elements within each half and sort each half.

  3. Combine: Merge the sorted halves while counting cross-half pairs.

During the merge, both halves are sorted by value. Maintain right_smaller_count, the number of elements from the right half that have already been merged because they are smaller than the current left-half element.

  • If the current left value is less than or equal to the current right value, add right_smaller_count to the left element’s result.

  • Otherwise, merge the right element and increment right_smaller_count.

The comparison is strict, so equal values are not counted.

Example Walkthrough

For nums = [5, 2, 6, 1]:

  1. Divide: [5, 2] and [6, 1].

  2. Conquer:

  3. In [5, 2], 5 has one smaller element after it: 2.

  4. In [6, 1], 6 has one smaller element after it: 1.

  5. The recursive counts are therefore [1, 0, 1, 0].

  6. Combine: The right half contains 1, which is smaller than both 5 and 2. Add one to each of their counts.

  7. The final result is [2, 1, 1, 0].

Complexity

The recurrence is:

[ T(n) = 2T(n/2) + O(n) ]

This is Master Theorem Case 2, since the recursive work is linear and the combine step is linear. Therefore, the time complexity is (O(n log n)).

Case Time
Best (O(n log n))
Average (O(n log n))
Worst (O(n log n))
  • Auxiliary space: (O(n)) for the sorted tuples and merged lists.

  • Recursion stack: (O(log n)), included in the (O(n)) auxiliary-space bound.

  • Input space: The input array is not counted as auxiliary space. If input and output are included, total space remains (O(n)).

A brute-force implementation would compare every pair:

Approach Time Extra space When to use
Pairwise comparison (O(n^2)) (O(1)) Small arrays or simple demonstrations
Divide and conquer (O(n log n)) (O(n)) General-purpose efficient solution

Code Example

def count_smaller_after_self(nums: list[int]) -> list[int]:
    """Return the count of strictly smaller elements after each element."""
    counts = [0] * len(nums)
    items = [(value, index) for index, value in enumerate(nums)]

    def divide_and_conquer(
        segment: list[tuple[int, int]],
    ) -> list[tuple[int, int]]:
        if len(segment) <= 1:
            return segment

        middle = len(segment) // 2

        # Divide
        left_segment = segment[:middle]
        right_segment = segment[middle:]

        # Conquer
        left = divide_and_conquer(left_segment)
        right = divide_and_conquer(right_segment)

        # Combine
        merged: list[tuple[int, int]] = []
        left_index = 0
        right_index = 0
        right_smaller_count = 0

        while left_index < len(left) and right_index < len(right):
            if left[left_index][0] <= right[right_index][0]:
                counts[left[left_index][1]] += right_smaller_count
                merged.append(left[left_index])
                left_index += 1
            else:
                merged.append(right[right_index])
                right_smaller_count += 1
                right_index += 1

        while left_index < len(left):
            counts[left[left_index][1]] += right_smaller_count
            merged.append(left[left_index])
            left_index += 1

        while right_index < len(right):
            merged.append(right[right_index])
            right_index += 1

        return merged

    divide_and_conquer(items)
    return counts


print(count_smaller_after_self([5, 2, 6, 1]))  # [2, 1, 1, 0]

Comparing with Dynamic Programming

Divide-and-conquer is appropriate here because the recursive subproblems operate on disjoint halves and do not overlap. If a problem repeatedly solves the same overlapping subproblems, memoization or another dynamic-programming technique is usually a better fit.

Common Pitfalls

  • Use <=, not <, when merging equal values; the problem asks for strictly smaller elements.

  • Preserve the original index with each value so counts are returned in input order.

  • Include the (O(log n)) recursion stack in the space analysis.

  • Handle empty input with [], one-element input with [0], duplicates correctly, and negative values without special treatment.

  • Already sorted input in ascending order produces all-zero counts.

  • Disconnected graphs and cycles are not applicable because this algorithm operates on a one-dimensional array.

  • A common follow-up is to ask how the same problem could be solved using a Fenwick tree or a value-indexed DP table.

46

How can Divide & Conquer count subarray sums within bounds?

Divide and Conquer counts subarrays whose sums fall within an inclusive range by recursively splitting the prefix-sum array, counting valid pairs in each half, then counting pairs that cross the midpoint with a two-pointer sweep.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Let prefix[k] be the sum of the first k elements (prefix[0]=0). Every subarray sum equals prefix[j] - prefix[i] with i < j. The problem becomes: count pairs (i, j) such that lower ≤ prefix[j] - prefix[i] ≤ upper.

  • Divide: Split the prefix array into left and right halves.

  • Conquer: Recursively count valid pairs in each half and sort the halves.

  • Combine: For each j in the right half, the valid i in the left half satisfy prefix[j] - upper ≤ prefix[i] ≤ prefix[j] - lower. Because both halves are sorted, two pointers can count these i in linear time. Finally, merge the two sorted halves.

Complexity and Comparison

Recurrence: T(n) = 2T(n/2) + O(n)
Master Theorem Case 2 → O(n log n) time (best, average, worst).
Space: O(n) auxiliary (temporary merge array + O(log n) recursion stack); input not counted.

Approach Time Extra space When to use
Brute force O(n²) O(1) Tiny arrays or verification
Divide & Conquer O(n log n) O(n) Large arrays, optimal comparison-based

Unlike dynamic programming, the subproblems here are disjoint; if subproblems overlapped, memoization would be better.

Code Example

from typing import List

def count_range_sum(nums: List[int], lower: int, upper: int) -> int:
    """Return the number of subarrays with sum in [lower, upper] inclusive."""
    if not nums:
        return 0

    # Build prefix sums: prefix[0]=0, prefix[i]=sum(nums[:i])
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)

    def merge_sort_count(lo: int, hi: int) -> int:
        # Count valid pairs in prefix[lo:hi] and sort this slice in place.
        if hi - lo <= 1:          # 0 or 1 element → no pairs
            return 0

        mid = (lo + hi) // 2
        count = merge_sort_count(lo, mid) + merge_sort_count(mid, hi)

        # --- Combine: count crossing pairs ---
        # For each right index r, find left indices l with
        # prefix[r] - upper <= prefix[l] <= prefix[r] - lower
        l_low = l_high = lo
        for r in range(mid, hi):
            while l_low < mid and prefix[l_low] < prefix[r] - upper:
                l_low += 1
            while l_high < mid and prefix[l_high] <= prefix[r] - lower:
                l_high += 1
            count += l_high - l_low

        # --- Merge the two sorted halves ---
        merged = []
        i, j = lo, mid
        while i < mid and j < hi:
            if prefix[i] <= prefix[j]:
                merged.append(prefix[i])
                i += 1
            else:
                merged.append(prefix[j])
                j += 1
        merged.extend(prefix[i:mid])
        merged.extend(prefix[j:hi])
        prefix[lo:hi] = merged
        return count

    return merge_sort_count(0, len(prefix))


# Example
print(count_range_sum([1, 2, 3], 3, 5))  # 3  (subarrays: [1,2], [3], [2,3])

Walkthrough for [1,2,3], bounds [3,5]
Prefix = [0,1,3,6]
1. Split into [0,1] and [3,6].
2. Left half [0,1]: split [0] and [1] → base cases return 0. Combine: for right value 1, valid left values in [1-5, 1-3] = [-4, -2] → none. Merge → [0,1].
3. Right half [3,6]: split [3] and [6] → base cases return 0. Combine: for right value 6, valid left in [6-5, 6-3] = [1,3] → left value 3 qualifies → count 1 (subarray [3]). Merge → [3,6].
4. Top combine: left [0,1], right [3,6]. For right 3: left in [3-5, 3-3] = [-2,0] → 0 qualifies → count 1 ([1,2]). For right 6: left in [1,3] → 1 qualifies → count 1 ([2,3]). Total = 0+0+1+1+1 = 3.

Edge Cases

  • Empty input: returns 0.

  • One element: counted if its value lies in [lower, upper].

  • Duplicates: each distinct (i,j) pair is counted separately.

  • Negative numbers: prefix sums are not monotonic, but the algorithm only requires sorted halves, which merge sort provides.

  • Already sorted input: still O(n log n) because the algorithm sorts prefix sums, not the original array.

Common Pitfalls

  • Treating lower/upper as exclusive bounds.

  • Forgetting that the prefix array has length n+1; the recursion must run on prefix, not nums.

  • Using list.pop(0) or list.insert(0, x) during merge (O(n²)); always merge into a new list.

  • Omitting the recursion stack from space complexity.

  • Assuming the original array must be sorted; only prefix sums are sorted internally.

47

How can divide and conquer find the top K frequent elements?

Use randomized quickselect as a divide-and-conquer strategy. Count each element’s frequency, partition the distinct elements around a pivot, and continue only with the partition containing the Kth-ranked element.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The implementation follows the three divide-and-conquer steps:

  1. Divide: Partition candidates into elements ranked above the pivot, the pivot itself, and elements ranked below it. Ranking uses descending frequency, then ascending element value as the tie-breaker.

  2. Conquer: Continue searching only with the partition that can contain the Kth-ranked candidate.

  3. Combine: After finding that candidate, collect every candidate ranked at least as highly and sort the result.

For a balanced branch, the recurrence is:

T(u) = T(u/2) + Θ(u)

This is Master Theorem Case 3, producing Θ(u) selection time. For uniformly random pivots, the expected recurrence is:

E[T(u)] = (1/u) Σ E[T(j)] + Θ(u)

where j ranges from 0 to u - 1; this also gives Θ(u) expected selection time. The worst case is T(u) = T(u - 1) + Θ(u) = Θ(u²).

Complexity and Alternatives

Let n be the array length, u the number of distinct elements, and k the requested result size. For 1 ≤ k < u:

  • Best case: Θ(n + k log k)—the first pivot is the required rank, and the selected elements are sorted afterward.

  • Expected case, averaging over pivot choices: Θ(n + k log k)—random pivoting gives expected linear selection, followed by sorting the output.

  • Worst case: Θ(n + u² + k log k)—unfortunate pivots repeatedly discard only one candidate.

  • Counting frequencies: Θ(n) time.

  • Combining the result: Θ(u) time.

  • Auxiliary space: O(u), including the frequency map, candidate list, result, and sort workspace. The iterative search uses O(1) selection stack space and avoids Python’s recursion-depth limit. Input space is not counted; including it gives O(n).

If k is at least the number of distinct values, the code returns all distinct values in Θ(n + u log u) time. If k <= 0, it returns immediately in Θ(1) time.

Approach Time Auxiliary space When to use
Repeatedly scan for each frequency O(nk) O(k) Small inputs or simple demonstrations
Count and sort all elements Θ(n + u log u) O(u) When simplicity matters or k is close to u
Divide-and-conquer quickselect Expected Θ(n + k log k) O(u) Large inputs with a moderate k

Dynamic programming is not a natural fit because the selection subproblems do not overlap. When recursive subproblems overlap, memoization or tabulation is usually better, as with recursive Fibonacci.

Code Example

from collections import Counter
from random import choice


def top_k_frequent(values: list[int], k: int) -> list[int]:
    """Return the k most frequent values, breaking ties by ascending value."""
    if k <= 0:
        return []

    counts = Counter(values)
    candidates = list(counts.items())  # (value, frequency)

    if k >= len(candidates):
        candidates.sort(key=lambda item: (-item[1], item[0]))
        return [value for value, _ in candidates]

    def select_rank_key(
        items: list[tuple[int, int]],
        left: int,
        right: int,
        target: int,
    ) -> tuple[int, int]:
        while left <= right:
            pivot_index = choice(range(left, right + 1))
            pivot_value, pivot_count = items[pivot_index]
            pivot_key = (-pivot_count, pivot_value)

            # Divide: partition the range around the pivot key.
            less = left
            current = left
            greater = right

            while current <= greater:
                value, count = items[current]
                current_key = (-count, value)

                if current_key < pivot_key:
                    items[less], items[current] = items[current], items[less]
                    less += 1
                    current += 1
                elif current_key > pivot_key:
                    items[current], items[greater] = items[greater], items[current]
                    greater -= 1
                else:
                    current += 1

            # Conquer: search only the partition containing the target rank.
            if target < less:
                right = less - 1
            elif target <= greater:
                return pivot_key
            else:
                target -= greater - left + 1
                left = greater + 1

        raise RuntimeError("Target rank is outside the candidate range")

    selected_key = select_rank_key(candidates, 0, len(candidates) - 1, k - 1)

    # Combine: gather and order all candidates ranked at least as highly.
    selected = [
        item
        for item in candidates
        if (-item[1], item[0]) <= selected_key
    ]
    selected.sort(key=lambda item: (-item[1], item[0]))

    return [value for value, _ in selected]


result = top_k_frequent([1, 1, 2, 2, 3, 3, 3, 4], 2)
print(result)  # [3, 1]

Example Walkthrough

For [1, 1, 2, 2, 3, 3, 3, 4] with k = 2:

Rank Element Frequency Rank key
0 3 3 (-3, 3)
1 1 2 (-2, 1)
2 2 2 (-2, 2)
3 4 1 (-1, 4)

If the pivot is 1, the divide step separates it from the candidates above and below its rank. Since the target is rank 1 and the pivot occupies that rank, the conquer step stops. The combine step collects and sorts [3, 1].

Common Pitfalls

  • Define tie behavior explicitly; this implementation prefers the smaller value when frequencies are equal.

  • Handle k <= 0, empty input, a single occurrence, one distinct value, duplicates, negative values, and k greater than the number of distinct values.

  • Input order, including already sorted input, does not affect the result.

  • Use Counter, not a set, because a set discards occurrence counts.

  • Adjust the target rank when discarding partitions during the right-side search.

  • Avoid recursion because pathological pivot sequences can exceed Python’s default recursion limit; this version uses iteration.

  • A heap-based selection is a useful alternative when k is very small, but randomized quickselect is generally faster when k is moderate.

48

How do you find the kth largest element using divide and conquer?

Kth-largest selection uses a divide-and-conquer strategy similar to quicksort, but it recurses—or iterates—only into the partition that can contain the requested element. This is commonly implemented as Quickselect, with expected linear time and a quadratic worst case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For an array of n elements, the kth largest element has the same value as the element at zero-based index n - k in the sorted array.

Quickselect uses three steps:

  1. Divide: Choose a pivot and partition the active range into values smaller than the pivot, equal to the pivot, and greater than the pivot.

  2. Conquer: Continue searching only in the partition that could contain the target index.

  3. Combine: Once the target index lies in the equal-pivot partition, return that value.

A three-way partition is useful because it groups duplicates together and avoids repeatedly searching through equal values.

Complexity

Case Time Reason
Best O(n) The first pivot directly identifies the target partition.
Average/expected O(n) Random pivots keep the expected amount of remaining work linear.
Worst O(n²) Every pivot is repeatedly an extreme value, so the active range shrinks by one element each time.

The auxiliary space is O(1) because the implementation below is iterative and uses no recursion stack. If the input array is counted, total space is O(n). The input array is modified in place.

For an ideally balanced partition, the recurrence is:

T(n) = T(n/2) + O(n)

This is Master Theorem Case 2, since a = 1, b = 2, and f(n) = Θ(n), giving T(n) = Θ(n). In the worst case, the recurrence is T(n) = T(n - 1) + O(n), which expands to Θ(n²).

Comparison with Other Approaches

Approach Time Extra space When to use
Sort and index O(n log n) O(n) for Python’s built-in sorting When the entire sorted order is also needed.
Heap O(n log k) for k >= 2; O(n) for k = 1 O(k) When maintaining the top k elements is more important than one-off selection.
Randomized Quickselect O(n) expected O(1) When only one order statistic is required.

Quickselect differs from dynamic programming because its recursive subproblems do not overlap: after partitioning, only one side is searched. Memoization is preferable when the same subproblem may be requested repeatedly.

Code Example

from random import randrange


def kth_largest(values: list[int], k: int) -> int:
    """Return the kth largest value, where k is 1-based."""
    if not values:
        raise ValueError("values must not be empty")
    if not 1 <= k <= len(values):
        raise ValueError("k must be between 1 and len(values)")

    target_index = len(values) - k
    left, right = 0, len(values) - 1

    while left <= right:
        # Divide: choose a pivot and partition the active range.
        pivot_index = randrange(left, right + 1)
        values[pivot_index], values[right] = values[right], values[pivot_index]
        pivot = values[right]

        less_end = left
        scan = left
        greater_start = right

        # Dutch National Flag partition:
        # [left, less_end) < pivot
        # [less_end, greater_start] == pivot
        # (greater_start, right] > pivot
        while scan <= greater_start:
            if values[scan] < pivot:
                values[less_end], values[scan] = values[scan], values[less_end]
                less_end += 1
                scan += 1
            elif values[scan] > pivot:
                values[scan], values[greater_start] = (
                    values[greater_start],
                    values[scan],
                )
                greater_start -= 1
            else:
                scan += 1

        # Conquer: keep only the partition containing target_index.
        if target_index < less_end:
            right = less_end - 1
        elif target_index > greater_start:
            left = greater_start + 1
        else:
            # Combine: the target is in the equal-pivot partition.
            return values[target_index]

    raise RuntimeError("unreachable: target partition was lost")


numbers = [3, 1, 4, 1, 5, 9, 2, 6]
print(kth_largest(numbers, 3))  # Expected output: 5

For the example, the sorted order is [1, 1, 2, 3, 4, 5, 6, 9]. The third largest element is 5.

Common Pitfalls

  • Empty input: Raises ValueError.

  • One element: Returns that element when k = 1.

  • Duplicates: The three-way partition groups equal values correctly.

  • Negative numbers: Comparisons work normally; no special handling is needed.

  • Already sorted input: Random pivots still provide expected O(n) performance.

  • Off-by-one errors: k is one-based, while target_index = len(values) - k is zero-based.

  • Mutation: The implementation rearranges the input list. Use values.copy() if the original order must be preserved.

  • Partition boundaries: Incorrect less_end or greater_start updates can cause elements to be discarded or searched repeatedly.

  • Integer overflow: Python integers do not overflow; in fixed-width languages, use an index type wide enough for the array size.

  • Visited set: Not applicable because this is an array-selection algorithm, not a graph traversal.

  • Worst-case behavior: Adversarial input can trigger O(n²) runtime; randomization makes this unlikely in practice.

  • Typical follow-up: Interviewers may ask how to preserve the input, answer repeated order-statistic queries, or adapt the algorithm to find several order statistics.

49

How does a divide-and-conquer range tree count ships in a rectangle?

A divide-and-conquer range tree counts ships whose coordinate points lie inside an axis-aligned rectangle. Each ship is represented by (x, y), and the rectangle is defined by inclusive bottom_left and top_right coordinates.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

The algorithm first sorts ships by x and recursively divides them into two balanced groups. Each node stores the sorted y coordinates of its ships.

For a query:

  1. Ignore nodes completely outside the rectangle’s x range.

  2. For nodes completely inside the x range, use two binary searches to count y coordinates within the rectangle.

  3. Recursively visit partially covered nodes.

Divide, Conquer, and Combine

  • Divide: Split the x-sorted ships into two halves.

  • Conquer: Build a range-tree node for each half.

  • Combine: Merge the children’s sorted y lists into the parent’s sorted list.

The build recurrence is:

B(n) = 2B(n/2) + O(n)

The O(n) term merges the two y lists. By the Master Theorem, Case 2, construction takes O(n log n) time.

Unlike dynamic programming, these subproblems do not overlap, so memoization is unnecessary.

Example Walkthrough

Suppose the ships are (1,2), (2,3), (4,1), (5,5), and (7,4). Query the rectangle with bottom_left=(2,1) and top_right=(5,5).

  • The root divides the x-sorted ships around x=4.

  • The left side contributes (2,3).

  • The right side contributes (4,1) and (5,5).

  • (1,2) and (7,4) are outside the x range.

The result is 3.

Complexity

Let n be the number of ships and q the number of rectangle queries.

Operation Best Average Worst Reason
Build O(n log n) O(n log n) O(n log n) Each of O(log n) levels merges O(n) y-values
One query O(log n) O(log² n) O(log² n) O(log n) covered nodes may each require binary searches
q queries O(q log² n) O(q log² n) O(q log² n) Each query is independent

Additional space is O(n log n), including the stored y-lists and O(log n) recursion stack. The input is excluded from this count; including it remains O(n log n).

Approach Query time Extra space When to use
Brute-force scan O(n) O(1) One or few rectangles
Divide-and-conquer range tree O(log² n) O(n log n) Many rectangle queries

Code Example

from __future__ import annotations

from bisect import bisect_left, bisect_right
from collections.abc import Sequence
from dataclasses import dataclass

Point = tuple[int, int]


@dataclass(slots=True)
class _RangeNode:
    min_x: int
    max_x: int
    ys: list[int]
    left: _RangeNode | None = None
    right: _RangeNode | None = None


def count_ships_in_rectangle(
    ships: Sequence[Point],
    top_right: Point,
    bottom_left: Point,
) -> int:
    """Count ship points inside an inclusive axis-aligned rectangle."""
    x_max, y_max = top_right
    x_min, y_min = bottom_left

    if x_min > x_max or y_min > y_max:
        raise ValueError(
            "top_right must be greater than or equal to bottom_left "
            "in both coordinates"
        )

    if not ships:
        return 0

    # Sorting creates a copy, so the caller's input is not mutated.
    ordered = sorted(ships)

    def merge_sorted(left: list[int], right: list[int]) -> list[int]:
        merged: list[int] = []
        left_index = right_index = 0

        while left_index < len(left) and right_index < len(right):
            if left[left_index] <= right[right_index]:
                merged.append(left[left_index])
                left_index += 1
            else:
                merged.append(right[right_index])
                right_index += 1

        merged.extend(left[left_index:])
        merged.extend(right[right_index:])
        return merged

    def build(left_index: int, right_index: int) -> _RangeNode:
        if left_index == right_index:
            point_x, point_y = ordered[left_index]
            return _RangeNode(point_x, point_x, [point_y])

        # Divide: split the x-sorted ships into two halves.
        middle = (left_index + right_index) // 2

        # Conquer: recursively build both subtree indexes.
        left_node = build(left_index, middle)
        right_node = build(middle + 1, right_index)

        # Combine: merge both children's sorted y-values.
        merged_ys = merge_sorted(left_node.ys, right_node.ys)

        return _RangeNode(
            min_x=left_node.min_x,
            max_x=right_node.max_x,
            ys=merged_ys,
            left=left_node,
            right=right_node,
        )

    def query(node: _RangeNode) -> int:
        if node.max_x < x_min or node.min_x > x_max:
            return 0

        if x_min <= node.min_x and node.max_x <= x_max:
            return (
                bisect_right(node.ys, y_max)
                - bisect_left(node.ys, y_min)
            )

        # A partially covered internal node always has both children.
        assert node.left is not None and node.right is not None
        return query(node.left) + query(node.right)

    root = build(0, len(ordered) - 1)
    return query(root)


ships = [(1, 2), (2, 3), (4, 1), (5, 5), (7, 4)]
result = count_ships_in_rectangle(
    ships,
    top_right=(5, 5),
    bottom_left=(2, 1),
)
print(result)  # 3

Common Pitfalls

  • Define whether rectangle boundaries are inclusive; this implementation includes them.

  • Empty input returns 0; one ship, negative coordinates, duplicates, and already sorted input work correctly.

  • Duplicate coordinates represent separate ships and are counted because duplicate y values remain in the merged lists.

  • The example helper builds the tree for one query. For many rectangles, separate construction from querying so the same root can be reused.

  • Swapping x and y or treating the rectangle as exclusive causes off-by-one errors.

  • Assuming a sorted input and mutating it in place can corrupt later queries.

  • Ignoring the O(n log n) storage cost can make the range tree unsuitable for memory-constrained systems.

  • Interviewers commonly ask about dynamic insertions, deletions, multiple rectangles, or alternatives such as Fenwick trees and k-d trees.

50

How to balance an unbalanced BST using divide and conquer

To balance a Binary Search Tree using divide and conquer, perform an in-order traversal to obtain the values in sorted order, then recursively split them at the midpoint to construct a new height-balanced tree. This produces a balanced BST while preserving the original values.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm follows the three divide-and-conquer steps:

  1. Divide: Traverse the BST in order and collect its values into a nondecreasing array.

  2. Conquer: Recursively split the array at its midpoint and construct the two subtrees.

  3. Combine: Make the midpoint value the root and attach the recursively constructed subtrees.

Because every subarray is split near its midpoint, the resulting tree satisfies the AVL balance condition: at every node, the left and right subtree heights differ by at most one.

The construction recurrence is:

T(n) = 2T(n/2) + O(1)

Here, a = 2, b = 2, and f(n) = O(1). By the Master Theorem, this is Case 1, so construction takes Θ(n) time. Including the O(n) in-order traversal, total time is O(n).

Walkthrough

For the values [1, 2, 3, 4, 5, 6, 7]:

  1. In-order traversal produces [1, 2, 3, 4, 5, 6, 7].

  2. The midpoint is 4, so it becomes the root.

  3. [1, 2, 3] is divided around 2, producing the left subtree.

  4. [5, 6, 7] is divided around 6, producing the right subtree.

  5. Recursion continues until every value is placed.

The resulting tree has height 2, counting edges, which is the minimum possible height for seven nodes.

Complexity

Aspect Complexity Reason
Time O(n) in the best, average, and worst cases Traversal visits every node, and construction creates every node
Auxiliary space O(n) The sorted array uses O(n); traversal and construction stacks also fit within this bound

The input tree and returned tree are not counted as auxiliary space. With iterative traversal, its explicit stack is O(h), where h can be O(n); the recursive construction stack is only O(log n).

Divide and Conquer vs Dynamic Programming

Divide-and-conquer subproblems here are independent and do not overlap: each recursive call handles a distinct subarray. Dynamic programming or memoization is preferable when subproblems overlap and would otherwise be recomputed, such as with the recursive Fibonacci algorithm.

Code Example

from __future__ import annotations


class TreeNode:
    def __init__(
        self,
        val: int = 0,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def balance_bst(root: TreeNode | None) -> TreeNode | None:
    """Return a height-balanced BST containing the same values as root."""
    sorted_values: list[int] = []
    stack: list[TreeNode] = []
    current = root

    # Divide: collect values in sorted order with iterative in-order traversal.
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left

        current = stack.pop()
        sorted_values.append(current.val)
        current = current.right

    def build_balanced(left: int, right: int) -> TreeNode | None:
        if left > right:
            return None

        # Divide: choose the middle element as this subtree's root.
        midpoint = left + (right - left) // 2
        node = TreeNode(sorted_values[midpoint])

        # Conquer: independently build both halves.
        left_root = build_balanced(left, midpoint - 1)
        right_root = build_balanced(midpoint + 1, right)

        # Combine: attach the conquered subtrees to the root.
        node.left = left_root
        node.right = right_root
        return node

    return build_balanced(0, len(sorted_values) - 1)


# Example: the unbalanced BST 1 -> 2 -> 3
root = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
balanced = balance_bst(root)
print(balanced.val, balanced.left.val, balanced.right.val)
# Expected output: 2 1 3

Common Pitfalls

  • Off-by-one errors: left + (right - left) // 2 handles the empty and single-element ranges correctly.

  • Recursion depth: The traversal is iterative, so a deeply skewed input does not exhaust Python’s recursion limit; construction recurses only O(log n) levels.

  • Mutating input: This implementation creates a new tree. An in-place algorithm can rewire existing nodes, commonly through AVL rotations, although rotations are not the only possible method.

  • Edge cases: Empty input returns None; a single-node input produces a new one-node tree; negative values are handled normally; an already balanced tree is rebuilt with the same values.

  • Duplicates: Every occurrence is preserved, but a side-specific duplicate convention, such as allowing equal keys only on the right, may not be preserved. Strict-BST inputs should use unique keys.

  • Interviewer follow-ups: Expect questions about AVL rotations, the Day–Stout–Warren in-place rebalancing algorithm, and the O(n) auxiliary-space cost of this sorted-array approach.

51

How do divide and conquer and a BIT create a sorted array?

Use divide and conquer to coordinate-compress the values, then use a Binary Indexed Tree (Fenwick tree) to maintain their multiplicities while instructions add or remove elements. The final sorted array is reconstructed by repeatedly finding the smallest value still present.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Divide, Conquer, and Combine

Assume each instruction is either:

  • ("add", value): inserts one occurrence of value.

  • ("remove", value): removes one occurrence of value.

The function below applies the complete sequence and returns the final sorted array.

The divide-and-conquer part sorts the distinct values so each value can receive a one-based Fenwick-tree position:

  1. Divide: Split the values into two approximately equal halves.

  2. Conquer: Recursively sort each half.

  3. Combine: Merge the sorted halves.

The merge-sort recurrence is:

T(u) = 2T(u/2) + O(u)

This is Master Theorem Case 2, giving Θ(n log n) time for the n referenced values (duplicates included); deduplication afterwards leaves u distinct values.

How the Fenwick Tree Works

After coordinate compression, each position represents one distinct value:

  • add: increment the frequency at that value’s rank.

  • remove: decrement the frequency, rejecting an invalid removal.

  • kth(k): use Fenwick-tree binary lifting to find the rank of the k-th smallest present element in O(log u) time.

Reconstructing the result by requesting ranks 1, 2, ..., p produces a sorted array and naturally supports duplicates.

This is not a dynamic-programming problem: the divide-and-conquer subproblems do not overlap, so memoization would add no benefit. If a variant repeatedly asks for the same range or count state, overlapping subproblems would make memoization or dynamic programming appropriate.

Complexity

Let n be the number of instructions, u the number of distinct referenced values, and p the number of elements in the final array.

Metric Complexity Reason
Best, average, worst time O(n log(n + 1)) Compression, updates, and reconstruction all use logarithmic-time operations
Auxiliary space O(n) Merge-sort buffers over all n values, plus O(u) for the Fenwick tree, coordinates, and frequencies, and an O(log n) recursion stack
Output space O(p) The returned sorted array
Total space including output O(n + p) Input is not counted or modified
Approach Time Extra space When to use
Sort only the final values O(n log n) O(n) Static final output only
Divide and conquer with a BIT O(n log n) O(u + p) Dynamic counts, removals, and order-statistic queries

Example Walkthrough

Instructions:

("add", 5), ("add", -2), ("add", 5), ("remove", -2), ("add", 0)

The compressed values are [-2, 0, 5].

Instruction Frequencies for [-2, 0, 5]
Add 5 [0, 0, 1]
Add -2 [1, 0, 1]
Add 5 [1, 0, 2]
Remove -2 [0, 0, 2]
Add 0 [0, 1, 2]

The final sorted array is [0, 5, 5].

Code Example

from typing import Literal

Instruction = tuple[Literal["add", "remove"], int]


class _FenwickTree:
    def __init__(self, size: int) -> None:
        self._size = size
        self._tree = [0] * (size + 1)

    def add(self, index: int, delta: int) -> None:
        while index <= self._size:
            self._tree[index] += delta
            index += index & -index

    def prefix_sum(self, index: int) -> int:
        total = 0
        while index > 0:
            total += self._tree[index]
            index -= index & -index
        return total

    def total(self) -> int:
        return self.prefix_sum(self._size)

    def kth(self, order: int) -> int:
        """Return the one-based rank containing the order-th element."""
        if not 1 <= order <= self.total():
            raise ValueError("order is outside the tree's frequencies")

        index = 0
        step = 1 << (self._size.bit_length() - 1)

        while step > 0:
            candidate = index + step
            if candidate <= self._size and self._tree[candidate] < order:
                order -= self._tree[candidate]
                index = candidate
            step >>= 1

        return index + 1


def _merge_sort(values: list[int]) -> list[int]:
    if len(values) <= 1:
        return values.copy()

    # Divide: split the values into two halves.
    middle = len(values) // 2

    # Conquer: recursively sort each half.
    left = _merge_sort(values[:middle])
    right = _merge_sort(values[middle:])

    # Combine: merge the sorted halves.
    merged: list[int] = []
    left_index = right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged


def create_sorted_array(instructions: list[Instruction]) -> list[int]:
    """Apply add/remove instructions and return the final sorted array."""
    if not instructions:
        return []

    sorted_values = _merge_sort([value for _, value in instructions])

    coordinates: list[int] = []
    for value in sorted_values:
        if not coordinates or value != coordinates[-1]:
            coordinates.append(value)

    ranks = {value: index for index, value in enumerate(coordinates, start=1)}
    frequencies = [0] * (len(coordinates) + 1)
    fenwick = _FenwickTree(len(coordinates))

    for operation, value in instructions:
        rank = ranks[value]

        if operation == "add":
            frequencies[rank] += 1
            fenwick.add(rank, 1)
        elif operation == "remove":
            if frequencies[rank] == 0:
                raise ValueError(f"cannot remove absent value: {value}")
            frequencies[rank] -= 1
            fenwick.add(rank, -1)
        else:
            raise ValueError(f"unknown operation: {operation}")

    result: list[int] = []
    for order in range(1, fenwick.total() + 1):
        rank = fenwick.kth(order)
        result.append(coordinates[rank - 1])

    return result


instructions: list[Instruction] = [
    ("add", 5),
    ("add", -2),
    ("add", 5),
    ("remove", -2),
    ("add", 0),
]

print(create_sorted_array(instructions))  # [0, 5, 5]

Common Pitfalls

  • Off-by-one errors: Fenwick-tree indexes are one-based, while Python list indexes are zero-based.

  • Duplicate values: Store frequencies rather than treating every occurrence as a distinct coordinate.

  • Invalid removals: Never allow a Fenwick-tree frequency to become negative.

  • Empty input: Return an empty list before constructing the tree.

  • Input mutation: This implementation copies and sorts values without modifying instructions.

  • Overflow: Python integers do not overflow, but fixed-width languages need sufficiently large counters.

  • Recursion depth: Merge sort uses only O(log n) stack frames, well below Python’s default recursion limit.

  • Common follow-up: Explain how kth works, add an insert or kth instruction, or discuss how coordinate compression supports negative and very large values. A visited set is not applicable because this algorithm does not traverse a graph.

52

How to sort an array using Divide and Conquer

Divide and Conquer sorting breaks a problem into smaller subproblems, solves them recursively, and combines their results. A standard implementation is Merge Sort, which guarantees O(n log n) time regardless of input order.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Merge Sort follows three steps at every recursive level:

  1. Divide: Split the array into two approximately equal halves.

  2. Conquer: Recursively sort each half. A half containing zero or one element is already sorted.

  3. Combine: Merge the two sorted halves by repeatedly comparing their first unmerged elements.

The implementation below uses <=, so equal elements retain their original relative order and the sort is stable.

Recurrence and Complexity

The recurrence is:

T(n) = 2T(n/2) + O(n)

Each level performs O(n) merging work, and there are O(log n) levels. This is Master Theorem Case 2, giving O(n log n) time.

Approach Best time Average time Worst time Space When to use
Naive bubble sort O(n) O(n²) O(n²) O(1) auxiliary Tiny arrays or teaching only; repeated adjacent comparisons drive the quadratic cost
Merge Sort O(n log n) O(n log n) O(n log n) O(n) auxiliary, including the O(log n) recursion stack Predictable worst-case performance and stable sorting; linear work occurs across O(log n) levels

The input array itself is not counted as auxiliary space. Temporary lists created by slicing and merging account for the O(n) space.

Comparison with Dynamic Programming

Divide and Conquer and Dynamic Programming both solve smaller problems recursively, but they differ in how results are reused.

Feature Divide and Conquer Dynamic Programming
Subproblems Usually independent and non-overlapping Often overlap
Strategy Solve recursively and combine Solve once and reuse stored results
Example Merge Sort, Quicksort Fibonacci, Knapsack

If recursive subproblems overlap substantially, memoization is generally more appropriate than recomputing them.

Example Walkthrough

For [4, 1, 3, 2]:

  1. Divide: Split it into [4, 1] and [3, 2].

  2. Conquer: Sort each pair, producing [1, 4] and [2, 3].

  3. Combine: Merge those sorted halves into [1, 2, 3, 4].

Code Example

def merge(left: list[int], right: list[int]) -> list[int]:
    """Merge two sorted integer lists into one sorted list."""
    merged: list[int] = []
    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])
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


def merge_sort(arr: list[int]) -> list[int]:
    """Return a sorted list using the Divide and Conquer strategy."""
    # Base case: empty and single-element lists are already sorted.
    if len(arr) <= 1:
        return arr

    # Divide: split the list into two halves.
    middle = len(arr) // 2
    left_half = arr[:middle]
    right_half = arr[middle:]

    # Conquer: recursively sort each half.
    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)

    # Combine: merge the sorted halves.
    return merge(sorted_left, sorted_right)


print(merge_sort([4, 1, 3, 2]))
# Output: [1, 2, 3, 4]

Common Pitfalls

  • Off-by-one errors: An incorrect midpoint or merge boundary can drop elements or cause infinite recursion.

  • Mutating input: This implementation returns a new sorted list and leaves the original unchanged.

  • Edge cases: Empty and single-element lists terminate immediately; duplicates and negative numbers work without special cases. Already-sorted input still takes O(n log n) time.

  • Integer overflow: Python integers do not overflow, but fixed-width languages must use size and index types that can represent the array length.

  • Graph-specific concerns: Disconnected graphs and cycles are not applicable to array sorting. Likewise, no visited set is needed; visited sets matter in graph traversals.

  • Follow-up: Interviewers commonly ask for an in-place alternative such as Quicksort, its average and worst-case behavior, or Merge Sort’s space trade-offs.

53

How to generate a Beautiful Array with Divide and Conquer?

A Beautiful Array is a permutation of the integers from 1 through n in which no three indices i < j < k form an arithmetic progression; that is, A[i] + A[k] != 2 * A[j]. Divide and conquer constructs a beautiful array by recursively building a beautiful array for a smaller power of two, then mapping it to odd and even values and concatenating the results.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The construction has three steps:

  1. Divide: Reduce the problem size by half. For a target size that is a power of two, recursively construct a beautiful array of half the size.

  2. Conquer: The base case is size 1, which is trivially beautiful ([1]). The recursive call returns a beautiful array of the smaller size.

  3. Combine: Transform the smaller beautiful array into two blocks: an odd block (2 * value - 1) and an even block (2 * value). Concatenate the odd block followed by the even block to form a beautiful array of the current size.

To handle arbitrary n, find the smallest power of two M ≥ n, build the beautiful array of size M, and return its first n elements. A prefix of a beautiful array remains beautiful because any three elements in the prefix also appear in the full array.

Divide and Conquer vs Dynamic Programming: This construction follows the divide-and-conquer paradigm because subproblems (different sizes) do not overlap; each recursive call works on a distinct size. Dynamic programming would be useful if subproblems overlapped, but here memoization is unnecessary.

Step-by-Step Example

For n = 5, the smallest power of two is 8:

Size Recursive Array Odd Block Even Block Combined Array
1 [1] [1] [2] [1, 2]
2 [1, 2] [1, 3] [2, 4] [1, 3, 2, 4]
4 [1, 3, 2, 4] [1, 5, 3, 7] [2, 6, 4, 8] [1, 5, 3, 7, 2, 6, 4, 8]

Taking the first five elements produces:

[1, 5, 3, 7, 2]

Correctness

Assume the recursively generated array B is beautiful.

  • Transforming B into 2 * B - 1 preserves the beautiful-array property. If three transformed values formed an arithmetic progression, dividing their differences by two would produce an arithmetic progression in B.

  • The same argument applies to 2 * B.

  • In the combined array, suppose A[i] + A[k] == 2 * A[j]. The right-hand side is even, so A[i] and A[k] have the same parity. Because odd and even values form separate contiguous blocks, A[j] must be in the same block. Mapping that block back to B would create an arithmetic progression in B, contradicting its beauty.

Thus, the combined array is beautiful. The base case [1] is trivially beautiful, so the construction is correct by induction.

Complexity

Let M be the smallest power of two greater than or equal to n.

  • Time: O(n) in the best, average, and worst cases. Each level performs linear work, and M < 2n.

  • Space: O(n) total, including the returned array and temporary odd and even lists. The recursion stack adds O(log n) space.

  • Input accounting: The input is one integer, so it occupies O(1) space and is not copied.

The recurrence is:

T(M) = T(M / 2) + Θ(M)

This is Master Theorem Case 3, because Θ(M) asymptotically dominates M^(log₂ 1) = 1. Therefore, T(M) = Θ(M) = Θ(n).

Code Example

def beautiful_array(n: int) -> list[int]:
    """Return a beautiful permutation of the integers from 1 through n."""
    if n <= 0:
        return []

    def build(size: int) -> list[int]:
        if size == 1:
            return [1]

        # Divide: reduce the problem size by half.
        half_size = size // 2

        # Conquer: recursively construct a beautiful source array.
        source = build(half_size)

        # Combine: map the source into odd and even blocks, then concatenate.
        odd_values = [2 * value - 1 for value in source]
        even_values = [2 * value for value in source]
        return odd_values + even_values

    target_size = 1
    while target_size < n:
        target_size *= 2

    return build(target_size)[:n]


print(beautiful_array(5))  # Expected output: [1, 5, 3, 7, 2]

Common Pitfalls

  • Incorrect target size: The recursive construction requires a power-of-two size. Use the smallest power of two greater than or equal to n, not merely n.

  • Truncating too early: Truncate only after constructing the complete power-of-two array; an arbitrary incomplete parity block may not satisfy the property.

  • Incorrect complexity claim: The algorithm processes M elements, where M < 2n, so its time is O(n), not O(n log n).

  • Off-by-one errors: The loop must continue while target_size < n, ensuring target_size is at least n.

  • Edge cases: n <= 0 returns an empty list; n = 1 returns [1]; duplicates and negative values are never produced. Input ordering, graphs, disconnected components, and cycles are not applicable to this numerical construction.

  • Integer overflow: Python integers do not overflow. In languages with fixed-width integers, the multiplication 2 * value requires a sufficiently large type.

54

How does divide and conquer support dynamic LIS updates and queries?

Dynamic LIS with arbitrary point updates can be implemented by updating the stored sequence immediately and recomputing the exact answer with CDQ divide and conquer and a Fenwick tree for prefix-maximum queries. This gives O(1) updates and O(n log² n) for an uncached query; claiming an O(log n) end-to-end update for arbitrary point changes would be inaccurate.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Assume the operations are:

  • update(index, value): replace one element.

  • query(): return the LIS length of the entire current sequence.

For a fixed sequence, define:

dp[i] = 1 + max(dp[j]) over all j < i for which values[j] < values[i].

CDQ divide and conquer processes the index range as follows:

  1. Divide: split [left, right] at its midpoint.

  2. Conquer: recursively finalize the DP values in the left half.

  3. Combine: insert left-half candidates into a Fenwick tree, then recursively finalize the right half using those candidates.

The Fenwick tree stores maximum DP values indexed by compressed element values. Querying through rank - 1 enforces a strictly increasing subsequence.

The runtime recurrence is:

T(n) = 2T(n/2) + O(n log n)

The generalized Master Theorem Case 2, where f(n) = Θ(n log n), gives T(n) = Θ(n log² n).

Ordinary D&C assumes disjoint subproblems. LIS DP has many overlapping predecessor transitions, so CDQ plus Fenwick is more appropriate than repeatedly calculating the same transitions. For genuinely repeated recursive states, memoization remains the better refinement.

Approach Comparison

Approach Work after an update Query time Space When to use
Brute-force DP O(n²) O(n²) O(n) Small or educational cases
CDQ plus Fenwick O(n log² n) recomputation O(n log² n) O(n) Required divide-and-conquer solution
Patience sorting O(n log n) recomputation O(n log n) O(n) Static or append-only LIS
Patience sorting with appends O(log n) amortized O(1) O(n) Frequent append-only updates

Complexity

  • Update: O(1), because it changes one element and invalidates the cached result.

  • Uncached query: O(n log² n) in the best, average and worst cases.

  • Cached query: O(1) until the next update.

  • Space: O(n) auxiliary space for compressed ranks, DP values and the Fenwick tree. The recursion stack contributes O(log n). The caller-owned input is excluded, while the class maintains its own O(n) copy.

Code Example

class FenwickMax:
    """Fenwick tree for prefix maximum queries."""

    def __init__(self, size: int) -> None:
        self._size = size
        self._tree = [0] * (size + 1)

    def update(self, index: int, value: int) -> None:
        while index <= self._size:
            self._tree[index] = max(self._tree[index], value)
            index += index & -index

    def query(self, index: int) -> int:
        result = 0
        while index > 0:
            result = max(result, self._tree[index])
            index -= index & -index
        return result


class DynamicLIS:
    """Support point updates and whole-sequence LIS-length queries."""

    def __init__(self, values: list[int]) -> None:
        self._values = values.copy()
        self._cached_result: int | None = None

    def update(self, index: int, value: int) -> None:
        if not 0 <= index < len(self._values):
            raise IndexError("index out of range")

        self._values[index] = value
        self._cached_result = None

    def query(self) -> int:
        if self._cached_result is None:
            self._cached_result = self._compute_lis()
        return self._cached_result

    def _compute_lis(self) -> int:
        if not self._values:
            return 0

        ordered_values = sorted(set(self._values))
        rank = {value: index + 1 for index, value in enumerate(ordered_values)}
        ranks = [rank[value] for value in self._values]

        dp = [0] * len(self._values)
        fenwick = FenwickMax(len(ordered_values))

        def cdq(left: int, right: int) -> None:
            if left == right:
                dp[left] = 1 + fenwick.query(ranks[left] - 1)
                return

            middle = (left + right) // 2

            # Divide: select the midpoint of this index range.
            # Conquer: finalize DP values in the left half.
            cdq(left, middle)

            # Combine: make left-half candidates available to the right half.
            for index in range(left, middle + 1):
                fenwick.update(ranks[index], dp[index])

            # Conquer: finalize the right half with combined candidates.
            cdq(middle + 1, right)

        cdq(0, len(self._values) - 1)
        return max(dp)


dynamic_lis = DynamicLIS([3, 10, 2, 1, 20])
print(dynamic_lis.query())  # 3

dynamic_lis.update(2, 15)
print(dynamic_lis.query())  # 4

After the update, the sequence is [3, 10, 15, 1, 20]. Its DP values are [1, 2, 3, 1, 4], so [3, 10, 15, 20] is an LIS of length 4.

Common Pitfalls

  • Query rank - 1, not rank; otherwise equal values incorrectly extend a strictly increasing subsequence.

  • Coordinate compression correctly supports negative numbers and duplicates.

  • Empty input returns 0, and a one-element sequence returns 1.

  • An arbitrary point update can invalidate many later DP values; a Fenwick tree alone does not support efficient deletion or replacement of such maxima.

  • Do not use list.pop(0) or list.insert(0, value); both are O(n).

  • A common follow-up asks about append-only updates. In that case, patience sorting provides O(log n) amortized insertion and an O(1) LIS-length query.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 54 Divide & Conquer answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects