Divide & Conquer | LIZIU DSA

Why Master Divide & Conquer?

🍕

Pizza Party Planning

Need to feed 100 people? Don't make one giant pizza! Make 10 smaller ones in parallel - it's faster and easier. That's divide & conquer: break big problems into manageable pieces!

📚

Organizing a Library

Sorting millions of books? Split them by category, sort each category separately, then merge back together. Much faster than sorting everything at once!

🔍

Finding a Word in Dictionary

Don't start from page 1! Open to the middle, see if your word comes before or after, then search only that half. Binary search uses divide & conquer!

🏭

Manufacturing Assembly Lines

Building cars? Break the process into stations - engine assembly, body work, painting. Each team works in parallel, then everything comes together!

🎬

Movie Rendering (Pixar/Disney)

Rendering a movie frame? Split the frame into sections, render each on different computers, then combine. This is how Pixar creates those stunning visuals!

🌐

Internet Search Engines

Google doesn't search the entire internet from one computer! They split queries across thousands of servers, search in parallel, then merge results!

Level 1: The Basics (Your First Divide & Conquer!)

Level 1

The Magic Formula

The 3-Step Recipe

DIVIDE: Split the problem into smaller subproblems
CONQUER: Solve each subproblem (usually recursively)
COMBINE: Merge the solutions to solve the original problem

Interactive: Watch Merge Sort in Action!

Enter numbers separated by commas to see how merge sort splits and merges them!

Click "Start Merge Sort" to see the divide & conquer magic!

Your First Divide & Conquer - Merge Sort! 🎉

def merge_sort(arr):
    """
    The classic divide & conquer algorithm!
    Time: O(n log n) - much better than O(n²) bubble sort
    """
    
    # BASE CASE: Array of 0 or 1 element is already sorted
    if len(arr) <= 1:
        return arr
    
    # STEP 1: DIVIDE - Split array in half
    mid = len(arr) // 2
    left_half = arr[:mid]    # First half
    right_half = arr[mid:]   # Second half
    
    # STEP 2: CONQUER - Recursively sort each half
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)
    
    # STEP 3: COMBINE - Merge the sorted halves
    return merge(left_sorted, right_sorted)

def merge(left, right):
    """
    Merge two sorted arrays into one sorted array
    This is where the magic happens!
    """
    result = []
    i = j = 0
    
    # Compare elements from both arrays and pick smaller one
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Add remaining elements (if any)
    result.extend(left[i:])   # Add rest of left
    result.extend(right[j:])  # Add rest of right
    
    return result

# Test it out!
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = merge_sort(numbers)
print(f"Original: {numbers}")
print(f"Sorted:   {sorted_numbers}")
                                

Understanding the Process

How merge_sort([64, 34, 25, 12]) Works

1

DIVIDE: Split [64, 34, 25, 12] into [64, 34] and [25, 12]

2

DIVIDE MORE: Split [64, 34] into [64] and [34]. Split [25, 12] into [25] and [12]

3

CONQUER: Single elements are already sorted!

4

COMBINE: Merge [64] and [34] to get [34, 64]. Merge [25] and [12] to get [12, 25]

5

FINAL COMBINE: Merge [34, 64] and [12, 25] to get [12, 25, 34, 64]

Common Mistake #1: Wrong Base Case

# ❌ WRONG - What if array is empty?
def bad_merge_sort(arr):
    if len(arr) == 1:  # Missing len(arr) == 0 case!
        return arr

# ✅ CORRECT - Handle both empty and single element
def good_merge_sort(arr):
    if len(arr) <= 1:  # Handles both cases!
        return arr
                            

Why Divide & Conquer is Amazing

Efficient: O(n log n) instead of O(n²) for sorting
Parallelizable: Subproblems can be solved on different cores/computers
Elegant: Clean, recursive solutions to complex problems
Versatile: Works for many different types of problems

Level 2: Common Divide & Conquer Patterns

Level 2

Pattern 1: Binary Search (Eliminate Half)

Binary Search - The Search Master

def binary_search(arr, target):
    """
    Find target in sorted array by eliminating half each time
    Time: O(log n) - super fast even for huge arrays!
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        # DIVIDE: Find middle point
        mid = (left + right) // 2
        
        # Found it!
        if arr[mid] == target:
            return mid
        
        # CONQUER: Search appropriate half
        elif arr[mid] < target:
            left = mid + 1    # Search right half
        else:
            right = mid - 1   # Search left half
    
    return -1  # Not found

# Example: Finding 7 in a sorted array
numbers = [1, 3, 5, 7, 9, 11, 13, 15]
result = binary_search(numbers, 7)
print(f"Found 7 at index: {result}")  # Output: 3
                                

Pattern 2: Quick Sort (Pick Pivot, Partition)

Quick Sort - The Speed Demon

def quick_sort(arr):
    """
    Average case: O(n log n), but can be O(n²) worst case
    Often faster than merge sort in practice!
    """
    if len(arr) <= 1:
        return arr
    
    # DIVIDE: Pick pivot and partition
    pivot = arr[len(arr) // 2]  # Middle element as pivot
    
    left = [x for x in arr if x < pivot]      # Smaller than pivot
    middle = [x for x in arr if x == pivot]    # Equal to pivot
    right = [x for x in arr if x > pivot]      # Greater than pivot
    
    # CONQUER: Recursively sort left and right parts
    # COMBINE: Concatenate results
    return quick_sort(left) + middle + quick_sort(right)

# Test it!
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_nums = quick_sort(numbers)
print(f"Quick sorted: {sorted_nums}")
                                

Pattern 3: Maximum Subarray (Kadane's Problem)

Finding Maximum Subarray Sum

def max_subarray_divide_conquer(arr, left=0, right=None):
    """
    Find maximum sum of contiguous subarray using divide & conquer
    Classic example from algorithms textbooks!
    """
    if right is None:
        right = len(arr) - 1
    
    # Base case: single element
    if left == right:
        return arr[left]
    
    # DIVIDE: Find middle
    mid = (left + right) // 2
    
    # CONQUER: Find max in left and right halves
    left_max = max_subarray_divide_conquer(arr, left, mid)
    right_max = max_subarray_divide_conquer(arr, mid + 1, right)
    
    # COMBINE: Find max crossing the middle
    cross_max = max_crossing_sum(arr, left, mid, right)
    
    # Return maximum of all three
    return max(left_max, right_max, cross_max)

def max_crossing_sum(arr, left, mid, right):
    """Find max sum that crosses the middle point"""
    # Max sum ending at mid (going left)
    left_sum = float('-inf')
    current_sum = 0
    for i in range(mid, left - 1, -1):
        current_sum += arr[i]
        left_sum = max(left_sum, current_sum)
    
    # Max sum starting at mid+1 (going right)
    right_sum = float('-inf')
    current_sum = 0
    for i in range(mid + 1, right + 1):
        current_sum += arr[i]
        right_sum = max(right_sum, current_sum)
    
    return left_sum + right_sum

# Example: Stock prices (find best buy-sell period)
prices = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_profit = max_subarray_divide_conquer(prices)
print(f"Maximum subarray sum: {max_profit}")  # Output: 6 ([4,-1,2,1])
                                

Pattern 4: Closest Pair of Points

Computational Geometry - Closest Points

import math

def closest_pair(points):
    """
    Find closest pair of points in 2D plane
    Brute force: O(n²), Divide & Conquer: O(n log n)
    """
    # Sort points by x-coordinate
    points.sort(key=lambda p: p[0])
    return closest_pair_rec(points)

def closest_pair_rec(points):
    n = len(points)
    
    # Base case: brute force for small arrays
    if n <= 3:
        return brute_force_closest(points)
    
    # DIVIDE: Split into left and right halves
    mid = n // 2
    left_points = points[:mid]
    right_points = points[mid:]
    
    # CONQUER: Find closest in each half
    left_min = closest_pair_rec(left_points)
    right_min = closest_pair_rec(right_points)
    
    # Current minimum distance
    min_dist = min(left_min, right_min)
    
    # COMBINE: Check points near the dividing line
    mid_x = points[mid][0]
    strip = [p for p in points if abs(p[0] - mid_x) < min_dist]
    
    # Find minimum in strip
    strip_min = strip_closest(strip, min_dist)
    
    return min(min_dist, strip_min)

# Helper functions...
def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
                                

Level 3: Practice Problems

Practice Time!

Easy

Problem 1: Count Inversions

Count how many pairs (i, j) exist where i < j but arr[i] > arr[j]. Use divide & conquer approach.

def count_inversions(arr):
    """
    Count inversions using modified merge sort
    Hint: Count inversions while merging!
    """
    # Your code here!
    pass
                            

💡 Show Solution

def count_inversions(arr):
    def merge_and_count(arr, temp, left, mid, right):
        i, j, k = left, mid + 1, left
        inv_count = 0
        
        while i <= mid and j <= right:
            if arr[i] <= arr[j]:
                temp[k] = arr[i]
                i += 1
            else:
                temp[k] = arr[j]
                inv_count += (mid - i + 1)  # Key insight!
                j += 1
            k += 1
        
        # Copy remaining elements
        while i <= mid:
            temp[k] = arr[i]
            i, k = i + 1, k + 1
        while j <= right:
            temp[k] = arr[j]
            j, k = j + 1, k + 1
        
        # Copy back
        for i in range(left, right + 1):
            arr[i] = temp[i]
        
        return inv_count
    
    def merge_sort_and_count(arr, temp, left, right):
        inv_count = 0
        if left < right:
            mid = (left + right) // 2
            inv_count += merge_sort_and_count(arr, temp, left, mid)
            inv_count += merge_sort_and_count(arr, temp, mid + 1, right)
            inv_count += merge_and_count(arr, temp, left, mid, right)
        return inv_count
    
    temp = [0] * len(arr)
    return merge_sort_and_count(arr[:], temp, 0, len(arr) - 1)
                                

Medium

Problem 2: Majority Element

Find the element that appears more than n/2 times in array. Use divide & conquer approach.

def majority_element(arr):
    """
    Find majority element using divide & conquer
    Hint: Split array, find majority in each half,
    then check which one is actually majority in whole array
    """
    # Your code here!
    pass
                            

💡 Show Solution

def majority_element(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    
    # Base case
    if left == right:
        return arr[left]
    
    # Divide
    mid = (left + right) // 2
    left_majority = majority_element(arr, left, mid)
    right_majority = majority_element(arr, mid + 1, right)
    
    # If both halves agree
    if left_majority == right_majority:
        return left_majority
    
    # Count occurrences
    left_count = sum(1 for i in range(left, right + 1) if arr[i] == left_majority)
    right_count = sum(1 for i in range(left, right + 1) if arr[i] == right_majority)
    
    return left_majority if left_count > right_count else right_majority
                                

Hard

Problem 3: Strassen's Matrix Multiplication

Implement Strassen's O(n^2.807) matrix multiplication algorithm using divide & conquer.

def strassen_multiply(A, B):
    """
    Strassen's algorithm for matrix multiplication
    Reduces 8 multiplications to 7 using clever additions
    """
    # Your code here!
    pass
                            

💡 Show Solution

def strassen_multiply(A, B):
    n = len(A)
    
    # Base case
    if n == 1:
        return [[A[0][0] * B[0][0]]]
    
    # Divide matrices into quadrants
    mid = n // 2
    A11 = [[A[i][j] for j in range(mid)] for i in range(mid)]
    A12 = [[A[i][j] for j in range(mid, n)] for i in range(mid)]
    A21 = [[A[i][j] for j in range(mid)] for i in range(mid, n)]
    A22 = [[A[i][j] for j in range(mid, n)] for i in range(mid, n)]
    
    # Similar for B matrix...
    B11 = [[B[i][j] for j in range(mid)] for i in range(mid)]
    B12 = [[B[i][j] for j in range(mid, n)] for i in range(mid)]
    B21 = [[B[i][j] for j in range(mid)] for i in range(mid, n)]
    B22 = [[B[i][j] for j in range(mid, n)] for i in range(mid, n)]
    
    # Strassen's 7 multiplications
    M1 = strassen_multiply(add_matrices(A11, A22), add_matrices(B11, B22))
    M2 = strassen_multiply(add_matrices(A21, A22), B11)
    M3 = strassen_multiply(A11, subtract_matrices(B12, B22))
    M4 = strassen_multiply(A22, subtract_matrices(B21, B11))
    M5 = strassen_multiply(add_matrices(A11, A12), B22)
    M6 = strassen_multiply(subtract_matrices(A21, A11), add_matrices(B11, B12))
    M7 = strassen_multiply(subtract_matrices(A12, A22), add_matrices(B21, B22))
    
    # Combine results
    C11 = add_matrices(subtract_matrices(add_matrices(M1, M4), M5), M7)
    C12 = add_matrices(M3, M5)
    C21 = add_matrices(M2, M4)
    C22 = add_matrices(subtract_matrices(add_matrices(M1, M3), M2), M6)
    
    # Combine quadrants
    C = [[0] * n for _ in range(n)]
    for i in range(mid):
        for j in range(mid):
            C[i][j] = C11[i][j]
            C[i][j + mid] = C12[i][j]
            C[i + mid][j] = C21[i][j]
            C[i + mid][j + mid] = C22[i][j]
    
    return C
                                

Level 4: Advanced Concepts

Level 4

Master Theorem - Analyzing Divide & Conquer

Master Theorem Formula

For recurrence: T(n) = aT(n/b) + f(n)

a: Number of subproblems
b: Factor by which problem size reduces
f(n): Cost of dividing and combining

Common Algorithm Complexities

Algorithm	Recurrence	Time Complexity	Why?
Binary Search	T(n) = T(n/2) + O(1)	O(log n)	1 subproblem, constant work
Merge Sort	T(n) = 2T(n/2) + O(n)	O(n log n)	2 subproblems, linear merge
Strassen's	T(n) = 7T(n/2) + O(n²)	O(n^2.807)	7 subproblems, quadratic work

Parallel Divide & Conquer

Parallel Merge Sort with Threading

import threading
from concurrent.futures import ThreadPoolExecutor

def parallel_merge_sort(arr, max_threads=4):
    """
    Parallel merge sort using threading
    Perfect for multi-core systems!
    """
    if len(arr) <= 1:
        return arr
    
    if max_threads <= 1 or len(arr) < 1000:
        # Fall back to sequential for small arrays or no threads
        return merge_sort(arr)
    
    # Divide
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    # Conquer in parallel
    with ThreadPoolExecutor(max_workers=2) as executor:
        left_future = executor.submit(
            parallel_merge_sort, left_half, max_threads // 2
        )
        right_future = executor.submit(
            parallel_merge_sort, right_half, max_threads // 2
        )
        
        left_sorted = left_future.result()
        right_sorted = right_future.result()
    
    # Combine
    return merge(left_sorted, right_sorted)

# Example usage
large_array = list(range(10000, 0, -1))  # Reverse sorted

import time
start = time.time()
sorted_seq = merge_sort(large_array.copy())
seq_time = time.time() - start

start = time.time()
sorted_par = parallel_merge_sort(large_array.copy())
par_time = time.time() - start

print(f"Sequential: {seq_time:.3f}s")
print(f"Parallel:   {par_time:.3f}s")
print(f"Speedup:    {seq_time/par_time:.2f}x")
                                

Cache-Efficient Divide & Conquer

Cache Performance Matters!

For large datasets, memory access patterns can make or break performance. Divide & conquer naturally has good cache locality because it works on smaller subproblems that fit in cache.

Cache-oblivious algorithms: Perform well regardless of cache size
Blocking techniques: Divide data to fit in cache levels
Memory hierarchy awareness: Consider L1, L2, L3 cache sizes

Advanced Applications

Fast Fourier Transform (FFT): Signal processing, O(n log n)
Karatsuba Multiplication: Large integer multiplication
Closest Pair Problems: Computational geometry
Convex Hull: Finding outer boundary of point sets
Median of Medians: Finding kth smallest in linear time

Quick Reference Guide

Divide & Conquer Patterns Cheat Sheet

Pattern	When to Use	Example	Time Complexity
Binary Elimination	Search in sorted data	Binary search	O(log n)
Split & Sort	Sorting algorithms	Merge sort, Quick sort	O(n log n)
Geometric Division	2D/3D problems	Closest pair, Convex hull	O(n log n)
Numeric Computation	Mathematical algorithms	FFT, Matrix multiplication	O(n^k) where k < 2
Tree-based Division	Hierarchical data	Tree traversals	O(n)

Design Checklist

Identify base case: When to stop dividing?
Division strategy: How to split the problem?
Subproblem independence: Can parts be solved separately?
Combination method: How to merge results?
Complexity analysis: Use Master Theorem

Common Mistakes

❌ Wrong base case handling
❌ Inefficient combination step
❌ Not balancing subproblems
❌ Forgetting to handle edge cases
❌ Inefficient data copying

Optimization Tips

✅ Use iterative for small inputs
✅ Consider parallel execution
✅ Minimize memory allocation
✅ Cache-friendly data access
✅ Profile and benchmark

Key Takeaways

Think divide, conquer, combine - The three-step recipe
Master the classics first - Binary search, merge sort, quicksort
Analyze with Master Theorem - Predict time complexity
Consider parallel opportunities - Subproblems are independent
Watch for base cases - When is the problem small enough?
Balance is key - Even splits usually work best
Practice geometric problems - Great for interviews
Don't overuse - Sometimes simple iteration is better