Skip to content
Hello Python
Algorithm1 Practice4 Interview

Divide and Conquer

Split a problem into independent subproblems, solve them recursively, and combine results. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Divide and Conquer when the prompt's constraints and required operations match this shape: Split a problem into independent subproblems, solve them recursively, and combine results.

Pybit demonstrates Divide and Conquer in a professional Python interview workspace.
On this page · Split into Independent Subproblems

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Divide and Conquer Code Labs

Split into Independent Subproblems

Divide and conquer works when a problem can be partitioned into smaller independent instances of the same contract. The base case must be complete, and every recursive call must receive a strictly smaller input.

Define the Merge Contract

Before recursing, say what each call returns. The merge step may interleave sorted halves, combine counts, or attach reconstructed subtrees, but it must use only the promised sub-results and preserve every original element.

Trace Recursive Range Splits

Reference
def divide_merge_trace(length):
    ranges = []
    def visit(left, right):
        if left >= right:
            return
        ranges.append([left, right])
        if right - left == 1:
            return
        mid = (left + right) // 2
        visit(left, mid)
        visit(mid, right)
    visit(0, length)
    return ranges
Practice

Implement divide_merge_trace(length). Return all non-empty half-open ranges [left, right] visited by a balanced root-left-right split, stopping at ranges of length one.

Public tests

  • Trace base cases and balanced splits

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Merge Two Sorted Halves

Reference
def merge_sorted_halves(left, right):
    merged = []
    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
Practice

Implement merge_sorted_halves(left, right). Return all values in sorted order without mutating either already-sorted input.

Public tests

  • Merge boundaries and duplicate values

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Account for Recursion Costs

Write a recurrence. Balanced halves with linear merging give T(n) = 2T(n/2) + O(n) = O(n log n). Python slices copy, so pass indexes when extra copying would add hidden time or space. Recursion also consumes stack frames.

Choose Divide and Conquer or Iteration

Use divide and conquer when subproblems are naturally independent and the combine is clear. Prefer iteration for a simple linear dependency or when Python recursion depth is a risk. Dynamic programming is different: it is valuable when subproblems overlap and should be cached.

Explain It in an Interview

Say: “The base case is complete, the split covers the input without overlap, and each recursive call satisfies the same return contract. The merge reconstructs the full answer.” Then solve the recurrence and count stack and slicing costs. Build Tree from Inorder and Postorder(opens in a new tab) is a representative partition-by-index transfer problem.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Divide and Conquer proof does not depend on a minor Python release.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Divide and Conquer complete workflowO(n)O(n)When one traversal identifies the root and another partitions left from right, index ranges avoid copying subarrays at each recursive call. Each frame describes matching node sets, and the inorder root offset determines the exact left-subtree size in preorder.

Space

O(n) for the focused Partition Traversal Ranges implementation.

Assumptions

  • The preorder start identifies the frame root, and its inorder position uniquely splits left and right node sets. Using the left-set size to partition preorder creates two smaller matching frames until every node is assigned.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Divide and Conquer invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Each recursive result is correct for its own subrange.
  3. The combine step preserves every required item and relation across subranges.
  4. When one traversal identifies the root and another partitions left from right, index ranges avoid copying subarrays at each recursive call. Preserve this claim after every transition.
  5. Each frame describes matching node sets, and the inorder root offset determines the exact left-subtree size in preorder. Preserve this claim after every transition.

When To Use Or Avoid Divide and Conquer

Use It When

  • Use Divide and Conquer when this precondition is stated or can be proved: The input can be split into smaller independent subproblems with a correct combine operation.
  • Use it when this maintained state removes repeated work: Each recursive result is correct for its own subrange.

Choose Another Tool When

  • Avoid Divide and Conquer when this precondition is absent: The input can be split into smaller independent subproblems with a correct combine operation.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The input can be split into smaller independent subproblems with a correct combine operation.

Avoid

def partition_traversal_ranges(preorder, inorder):
    pass

Use instead

def partition_traversal_ranges(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    frames = []
    def partition(pre_left, pre_right, in_left, in_right):
        if pre_left >= pre_right:
            return
        frames.append([pre_left, pre_right, in_left, in_right])
        root_index = positions[preorder[pre_left]]
        left_size = root_index - in_left
        partition(pre_left + 1, pre_left + 1 + left_size, in_left, root_index)
        partition(pre_left + 1 + left_size, pre_right, root_index + 1, in_right)
    partition(0, len(preorder), 0, len(inorder))
    return frames

Where you will hit this: Partition Traversal Ranges(opens in a new tab)

Breaking the state transition

Omits one position from both preorder child boundaries, producing incorrect or nonshrinking recursive frames.

Prevent it: Preserve this proof obligation: The subproblems cover the original input without omission, and the combine step restores the full contract.

Avoid

def partition_traversal_ranges(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    frames = []
    def partition(pl, pr, il, ir):
        if pl >= pr: return
        frames.append([pl, pr, il, ir])
        root = positions[preorder[pl]]
        left_size = root - il
        partition(pl + 1, pl + left_size, il, root)
        partition(pl + left_size, pr, root + 1, ir)
    partition(0, len(preorder), 0, len(inorder))
    return frames

Use instead

def partition_traversal_ranges(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    frames = []
    def partition(pre_left, pre_right, in_left, in_right):
        if pre_left >= pre_right:
            return
        frames.append([pre_left, pre_right, in_left, in_right])
        root_index = positions[preorder[pre_left]]
        left_size = root_index - in_left
        partition(pre_left + 1, pre_left + 1 + left_size, in_left, root_index)
        partition(pre_left + 1 + left_size, pre_right, root_index + 1, in_right)
    partition(0, len(preorder), 0, len(inorder))
    return frames

Where you will hit this: Partition Traversal Ranges(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n).

Avoid

def partition_traversal_ranges(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    frames = []
    def partition(pl, pr, il, ir):
        if pl >= pr: return
        frames.append([pl, pr, il, ir])
        root = positions[preorder[pl]]
        left_size = root - il
        partition(pl + 1, pl + left_size, il, root)
        partition(pl + left_size, pr, root + 1, ir)
    partition(0, len(preorder), 0, len(inorder))
    return frames

Use instead

def partition_traversal_ranges(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    frames = []
    def partition(pre_left, pre_right, in_left, in_right):
        if pre_left >= pre_right:
            return
        frames.append([pre_left, pre_right, in_left, in_right])
        root_index = positions[preorder[pre_left]]
        left_size = root_index - in_left
        partition(pre_left + 1, pre_left + 1 + left_size, in_left, root_index)
        partition(pre_left + 1 + left_size, pre_right, root_index + 1, in_right)
    partition(0, len(preorder), 0, len(inorder))
    return frames

Where you will hit this: Build Tree from Inorder and Postorder(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.