Algorithm Design Techniques — Divide & Conquer, Transform & Conquer Guide

In this tutorial, you'll learn about Algorithm Design Techniques. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Algorithm design techniques are general strategies for solving computational problems. Rather than memorizing thousands of algorithms, you learn these patterns — Divide And Conquer, transform and conquer, greedy, Dynamic Programming, Backtracking, and brute force — and apply them to new problems.

What You'll Learn

You will learn the major algorithm design paradigms: Divide And Conquer, transform and conquer (including presorting and reduction), decrease and conquer, and brute force with practical examples of each.

Why It Matters

Understanding algorithm design techniques turns you from a programmer who copies solutions into one who creates them. When facing a novel problem, these patterns give you a starting point and a systematic approach.

Real-World Use

DodaZIP's compression engine combines multiple design techniques: Huffman coding (greedy) for symbol encoding, LZ77 (decrease and conquer) for dictionary compression, and the overall pipeline follows a transform-and-conquer approach — transform the data into a more compressible form, then compress it.

Algorithm Design Classification

graph TD
    AD[Algorithm Design] --> DC[Divide & Conquer]
    AD --> TC[Transform & Conquer]
    AD --> DEC[Decrease & Conquer]
    AD --> G[Greedy]
    AD --> DP[Dynamic Programming]
    AD --> BT[Backtracking]
    AD --> BF[Brute Force]
    DC --> MS[Merge Sort]
    DC --> QS[Quick Sort]
    DC --> BS[Binary Search]
    TC --> PS[Presorting]
    TC --> R[Reduction]
    DEC --> IS[Insertion Sort]
    DEC --> GCD[Euclid's GCD]
    G --> HUFF[Huffman Coding]
    style AD fill:#4a90d9,stroke:#333,color:#fff

Divide And Conquer

Break a problem into smaller subproblems, solve recursively, combine results:

def max_subarray_divide_conquer(arr):
    if len(arr) == 1:
        return arr[0]
    mid = len(arr) // 2
    left_max = max_subarray_divide_conquer(arr[:mid])
    right_max = max_subarray_divide_conquer(arr[mid:])
    cross_max = max_crossing_sum(arr, mid)
    return max(left_max, right_max, cross_max)

def max_crossing_sum(arr, mid):
    left_sum = float('-inf')
    total = 0
    for i in range(mid - 1, -1, -1):
        total += arr[i]
        left_sum = max(left_sum, total)
    right_sum = float('-inf')
    total = 0
    for i in range(mid, len(arr)):
        total += arr[i]
        right_sum = max(right_sum, total)
    return left_sum + right_sum

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Max subarray sum:", max_subarray_divide_conquer(arr))

Expected output:

Max subarray sum: 6

function maxSubarrayDivideConquer(arr) {
    if (arr.length === 1) return arr[0];
    const mid = Math.floor(arr.length / 2);
    const leftMax = maxSubarrayDivideConquer(arr.slice(0, mid));
    const rightMax = maxSubarrayDivideConquer(arr.slice(mid));
    const crossMax = maxCrossingSum(arr, mid);
    return Math.max(leftMax, rightMax, crossMax);
}

function maxCrossingSum(arr, mid) {
    let leftSum = -Infinity, total = 0;
    for (let i = mid - 1; i >= 0; i--) {
        total += arr[i];
        leftSum = Math.max(leftSum, total);
    }
    let rightSum = -Infinity;
    total = 0;
    for (let i = mid; i < arr.length; i++) {
        total += arr[i];
        rightSum = Math.max(rightSum, total);
    }
    return leftSum + rightSum;
}

console.log("Max subarray sum:", maxSubarrayDivideConquer([-2, 1, -3, 4, -1, 2, 1, -5, 4]));

Expected output:

Max subarray sum: 6

Transform and Conquer

Transform the problem into a different form that is easier to solve.

Presorting

Sort the data first, then solve the problem on sorted data:

# Without presorting: O(n²)
def find_duplicates_brute(arr):
    duplicates = set()
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                duplicates.add(arr[i])
    return list(duplicates)

# With presorting: O(n log n)
def find_duplicates_presort(arr):
    arr.sort()
    duplicates = []
    for i in range(1, len(arr)):
        if arr[i] == arr[i - 1]:
            if not duplicates or duplicates[-1] != arr[i]:
                duplicates.append(arr[i])
    return duplicates

arr = [4, 3, 2, 7, 8, 2, 3, 1]
print("Brute force:", find_duplicates_brute(arr))
print("Presort:", find_duplicates_presort(arr))

Expected output:

Brute force: [2, 3]
Presort: [2, 3]

Reduction

Transform problem A into problem B, solve B, transform back:

# Finding closest pair of points — reduce to sorting
def closest_pair(points):
    # Sort by x-coordinate
    points.sort(key=lambda p: p[0])
    min_dist = float('inf')
    for i in range(len(points) - 1):
        dist = ((points[i][0] - points[i + 1][0])**2 +
                (points[i][1] - points[i + 1][1])**2)**0.5
        min_dist = min(min_dist, dist)
    return min_dist

points = [(1, 2), (3, 4), (5, 6), (7, 8)]
print("Closest distance:", closest_pair(points))

Expected output:

Closest distance: 2.8284271247461903

Decrease and Conquer

Reduce the problem to a smaller instance, solve the smaller one.

Insertion Sort (Decrease by One)

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([5, 3, 1, 4, 2]))

Expected output:

[1, 2, 3, 4, 5]

Euclid's GCD (Decrease by Variable)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print("GCD(48, 18):", gcd(48, 18))

Expected output:

GCD(48, 18): 6

Brute Force

Try all possibilities. Rarely optimal but always works:

# Brute force string matching
def brute_force_search(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            return i
    return -1

print("Brute force pattern at:", brute_force_search("hello world", "world"))

Expected output:

Brute force pattern at: 6

Choosing the Right Technique

Complexity Comparison

Common Pitfalls

1. Applying DP When Greedy Works

If the problem has the greedy choice property, DP is overkill. Activity selection is O(n log n) with greedy versus O(n²) with DP.

2. Using Divide And Conquer When Subproblems Overlap

Divide And Conquer works for non-overlapping subproblems (merge sort). For overlapping subproblems (Fibonacci), use DP.

3. Premature Optimization

Start with brute force or a straightforward solution. Optimize only after correctness is verified and performance is measured.

4. Ignoring the Transform Step

Sometimes the hardest part is finding the right transformation. Presorting is the most common and powerful transformation.

5. Not Recognizing Reduction Opportunities

Many unfamiliar problems can be reduced to known ones. The traveling salesman problem reduces to finding a Hamiltonian cycle. Recognizing reductions saves enormous effort.

Practice Questions

1. Identify which design technique is best for: finding the mode of an array of integers.

2. Transform the problem "find if any two numbers in an array sum to target" using presorting.

3. Reduce the problem "find the longest word in a dictionary that can be built from given letters" to a sorting problem.

4. Challenge: Implement the closest pair of points problem using Divide And Conquer (O(n log n)), then compare its performance with the brute force O(n²) version on random point sets of varying sizes.

5. Real-world task: DodaZIP's compression pipeline uses multiple design techniques. Write a function that analyzes a given algorithm (as a function) by running it on inputs of increasing sizes and determining which design technique it most likely uses based on its empirical time complexity.

What's Next

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.