[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":88,"_72":89,"_35":90},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":55,"_64":65,"_66":67,"_68":69,"_70":71},"id",30,"title","Divide and Conquer","slug","algorithms-part-3-divide-and-conquer","excerpt","Apply the Divide & Conquer paradigm to break down problems. Learn the Master Theorem for analyzing recurrences and implement classic D&C algorithms.","# Algorithms Compendium Part 3: Divide and Conquer Strategy\n\nDivide and Conquer is one of the most powerful algorithmic paradigms. It transforms seemingly intractable problems into manageable pieces, enabling algorithms that would otherwise be impossible. From sorting billions of records to finding the closest pair of points, D&C is the foundation of countless efficient algorithms.\n\nThis article teaches you to recognize D&C problems, apply the Master Theorem for complexity analysis, and implement classic D&C algorithms from scratch.\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Core Concept | Divide problem, solve subproblems, combine results |\n| Key Tool | Master Theorem for recurrence analysis |\n| Classic Algorithms | MergeSort, QuickSort, Binary Search, Karatsuba |\n| Time Complexity | Often O(n log n) for comparison-based problems |\n| Key Insight | Reducing problem size logarithmically is extremely powerful |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Apply the D&C paradigm** to break down complex problems\n- **Use the Master Theorem** to analyze recurrence relations\n- **Implement MergeSort** with deep understanding of the merge step\n- **Apply Quick Select** for O(n) average-case selection\n- **Solve classic D&C problems** like closest pair of points\n- **Recognize when D&C applies** vs other approaches\n\n---\n\n## 🔥 Production Story: The 100 Million Record Sort\n\nA data analytics platform needed to sort 100 million user activity records for daily reporting. The initial approach used a simple comparison sort, running for 8 hours.\n\n```java\n// ❌ Initial approach: trying to sort in memory\npublic void generateDailyReport(List records) {\n Collections.sort(records, Comparator.comparing(ActivityRecord::getTimestamp));\n // ... generate report\n}\n```\n\n**Problem:** 100 million records × 1KB each = 100GB. Didn't fit in memory. External sort was needed.\n\n**The solution - Divide and Conquer external sort:**\n\n```java\n// ✅ External merge sort using D&C\npublic class ExternalMergeSort {\n\n private static final int CHUNK_SIZE = 1_000_000; // 1GB chunks\n\n public void sort(Path inputFile, Path outputFile) throws IOException {\n // DIVIDE: Split into sorted chunks\n List sortedChunks = splitAndSortChunks(inputFile);\n\n // CONQUER: Merge chunks using k-way merge\n mergeChunks(sortedChunks, outputFile);\n }\n\n private List splitAndSortChunks(Path inputFile) throws IOException {\n List chunks = new ArrayList<>();\n List buffer = new ArrayList<>(CHUNK_SIZE);\n\n try (BufferedReader reader = Files.newBufferedReader(inputFile)) {\n String line;\n while ((line = reader.readLine()) != null) {\n buffer.add(parse(line));\n\n if (buffer.size() >= CHUNK_SIZE) {\n // Sort chunk in memory\n buffer.sort(Comparator.comparing(ActivityRecord::getTimestamp));\n // Write to temp file\n Path chunk = writeChunk(buffer);\n chunks.add(chunk);\n buffer.clear();\n }\n }\n }\n\n if (!buffer.isEmpty()) {\n buffer.sort(Comparator.comparing(ActivityRecord::getTimestamp));\n chunks.add(writeChunk(buffer));\n }\n\n return chunks;\n }\n\n private void mergeChunks(List chunks, Path output) throws IOException {\n // K-way merge using priority queue\n PriorityQueue pq = new PriorityQueue<>(\n Comparator.comparing(cr -> cr.peek().getTimestamp())\n );\n\n // Initialize readers\n for (Path chunk : chunks) {\n ChunkReader reader = new ChunkReader(chunk);\n if (reader.hasNext()) {\n pq.add(reader);\n }\n }\n\n // Merge\n try (BufferedWriter writer = Files.newBufferedWriter(output)) {\n while (!pq.isEmpty()) {\n ChunkReader reader = pq.poll();\n writer.write(serialize(reader.next()));\n writer.newLine();\n\n if (reader.hasNext()) {\n pq.add(reader); // Re-add with new head\n }\n }\n }\n }\n}\n```\n\n**Result:** Processing time dropped from 8 hours to 45 minutes:\n- 100 chunks of 1M records each\n- Each chunk sorted in ~10 seconds\n- K-way merge in ~25 minutes\n\n**The lesson:** Divide and Conquer transforms impossible problems into manageable ones. When data doesn't fit, divide until it does.\n\n---\n\n## 🧠 Mental Model: The Three-Step Dance\n\nEvery D&C algorithm follows the same three-step pattern:\n\n```text\n┌─────────────────────────────────────────────────────────────────┐\n│ DIVIDE AND CONQUER PARADIGM │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ 1. DIVIDE │\n│ └── Break problem into smaller subproblems │\n│ └── Usually into 2 or more equal parts │\n│ └── Key: subproblems should be similar to original │\n│ │\n│ 2. CONQUER │\n│ └── Solve subproblems recursively │\n│ └── Base case: solve directly when small enough │\n│ └── Recursive case: apply D&C to subproblems │\n│ │\n│ 3. COMBINE │\n│ └── Merge solutions of subproblems │\n│ └── This is often where the real work happens │\n│ └── Key: combining should be efficient │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n**Visual example with MergeSort:**\n\n```text\n [38, 27, 43, 3, 9, 82, 10]\n │\n DIVIDE ───────────────┼───────────────\n │\n [38, 27, 43, 3] [9, 82, 10]\n │ │\n ────┼──── ────┼────\n │ │ │ │\n [38,27] [43,3] [9,82] [10]\n │ │ │ │\n ───┼─── ───┼─── ───┼─── │\n │ │ │ │ │ │ │\n [38] [27] [43] [3] [9] [82] [10] ← Base cases\n │ │ │ │ │ │ │\n └──┬──┘ └──┬──┘ └──┬──┘ │\n │ │ │ │\n CONQUER ──────┼─────────────┼─────────┼──\n │ │ │\n [27,38] [3,43] [9,82] [10]\n │ │ │ │\n └────┬────┘ └────┬────┘\n │ │\n [3,27,38,43] [9,10,82]\n │ │\n └──────────┬──────────┘\n │\n COMBINE ──────────────┼───────────────\n │\n [3, 9, 10, 27, 38, 43, 82]\n```\n\n---\n\n## 🔬 Deep Dive\n\n### 1. The Master Theorem: Your Complexity Calculator\n\nMost D&C algorithms have recurrences of the form:\n\n```text\nT(n) = aT(n/b) + f(n)\n\nWhere:\n- a = number of subproblems\n- n/b = size of each subproblem\n- f(n) = cost of dividing and combining\n```\n\n**The Master Theorem tells us the complexity:**\n\n```text\nCompare f(n) with n^(log_b(a)):\n\nCase 1: f(n) = O(n^(log_b(a) - ε)) for some ε > 0\n → T(n) = Θ(n^(log_b(a)))\n \"Work at leaves dominates\"\n\nCase 2: f(n) = Θ(n^(log_b(a)) × log^k(n))\n → T(n) = Θ(n^(log_b(a)) × log^(k+1)(n))\n \"Work is evenly distributed\"\n\nCase 3: f(n) = Ω(n^(log_b(a) + ε)) for some ε > 0\n AND af(n/b) ≤ cf(n) for some c < 1\n → T(n) = Θ(f(n))\n \"Work at root dominates\"\n```\n\n**Let's apply it:**\n\n**Example 1: MergeSort**\n```text\nT(n) = 2T(n/2) + Θ(n)\na = 2, b = 2, f(n) = n\nn^(log_2(2)) = n^1 = n\nf(n) = Θ(n) = Θ(n^(log_b(a))) → Case 2 (k=0)\nT(n) = Θ(n log n)\n```\n\n**Example 2: Binary Search**\n```text\nT(n) = T(n/2) + Θ(1)\na = 1, b = 2, f(n) = 1\nn^(log_2(1)) = n^0 = 1\nf(n) = Θ(1) = Θ(n^(log_b(a))) → Case 2 (k=0)\nT(n) = Θ(log n)\n```\n\n**Example 3: Karatsuba Multiplication**\n```text\nT(n) = 3T(n/2) + Θ(n)\na = 3, b = 2, f(n) = n\nn^(log_2(3)) = n^1.585\nf(n) = n = O(n^(1.585 - 0.585)) → Case 1\nT(n) = Θ(n^1.585) ≈ Θ(n^1.59)\n```\n\n### 2. MergeSort: The D&C Template\n\nMergeSort is the canonical D&C algorithm. Understanding it deeply helps with all others.\n\n```java\n// ✅ Complete MergeSort implementation\npublic class MergeSort {\n\n public static void sort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n int[] temp = new int[arr.length]; // Auxiliary array\n mergeSort(arr, temp, 0, arr.length - 1);\n }\n\n private static void mergeSort(int[] arr, int[] temp, int left, int right) {\n // Base case: single element is sorted\n if (left >= right) return;\n\n // DIVIDE: find midpoint\n int mid = left + (right - left) / 2;\n\n // CONQUER: sort both halves\n mergeSort(arr, temp, left, mid);\n mergeSort(arr, temp, mid + 1, right);\n\n // COMBINE: merge sorted halves\n merge(arr, temp, left, mid, right);\n }\n\n private static void merge(int[] arr, int[] temp, int left, int mid, int right) {\n // Copy to temp array\n for (int i = left; i <= right; i++) {\n temp[i] = arr[i];\n }\n\n int i = left; // Pointer for left half\n int j = mid + 1; // Pointer for right half\n int k = left; // Pointer for merged array\n\n // Merge while both halves have elements\n while (i <= mid && j <= right) {\n if (temp[i] <= temp[j]) { // <= for stability\n arr[k++] = temp[i++];\n } else {\n arr[k++] = temp[j++];\n }\n }\n\n // Copy remaining elements from left half (right half already in place)\n while (i <= mid) {\n arr[k++] = temp[i++];\n }\n }\n}\n```\n\n**Why MergeSort matters:**\n\n| Property | MergeSort | QuickSort |\n|----------|-----------|-----------|\n| Worst case | O(n log n) | O(n²) |\n| Stable | Yes | No |\n| Space | O(n) | O(log n) |\n| Cache | Poor | Good |\n| External sort | Yes | No |\n\n### 3. Quick Select: O(n) Selection\n\nFinding the k-th smallest element seems to require sorting (O(n log n)). But D&C gives us O(n) average!\n\n```java\n// ✅ QuickSelect - O(n) average case\npublic class QuickSelect {\n\n public static int findKthSmallest(int[] arr, int k) {\n return quickSelect(arr, 0, arr.length - 1, k - 1); // Convert to 0-indexed\n }\n\n private static int quickSelect(int[] arr, int left, int right, int k) {\n // Base case: single element\n if (left == right) return arr[left];\n\n // DIVIDE: partition around pivot\n int pivotIndex = partition(arr, left, right);\n\n // CONQUER: only recurse on the side containing k\n if (k == pivotIndex) {\n return arr[k]; // Found it!\n } else if (k < pivotIndex) {\n return quickSelect(arr, left, pivotIndex - 1, k); // Left side only\n } else {\n return quickSelect(arr, pivotIndex + 1, right, k); // Right side only\n }\n }\n\n private static int partition(int[] arr, int left, int right) {\n // Use random pivot to avoid worst case\n int pivotIdx = left + new Random().nextInt(right - left + 1);\n int pivot = arr[pivotIdx];\n\n // Move pivot to end\n swap(arr, pivotIdx, right);\n\n int storeIdx = left;\n for (int i = left; i < right; i++) {\n if (arr[i] < pivot) {\n swap(arr, i, storeIdx);\n storeIdx++;\n }\n }\n\n // Move pivot to final position\n swap(arr, storeIdx, right);\n return storeIdx;\n }\n\n private static void swap(int[] arr, int i, int j) {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n}\n```\n\n**Why is it O(n)?**\n\nUnlike QuickSort which recurses on both halves, QuickSelect only recurses on one:\n\n```text\nWorst case (bad pivots): n + n-1 + n-2 + ... + 1 = O(n²)\nAverage case: n + n/2 + n/4 + n/8 + ... = 2n = O(n)\n```\n\n### 4. Closest Pair of Points\n\nA classic D&C problem: given n points, find the pair with minimum distance.\n\n**Brute force:** O(n²) - check all pairs\n**D&C:** O(n log n)\n\n```java\n// ✅ Closest Pair using Divide and Conquer\npublic class ClosestPair {\n\n public static double findClosestPair(Point[] points) {\n // Sort by x-coordinate\n Point[] sortedByX = Arrays.copyOf(points, points.length);\n Arrays.sort(sortedByX, Comparator.comparingDouble(p -> p.x));\n\n // Sort by y-coordinate (for strip processing)\n Point[] sortedByY = Arrays.copyOf(points, points.length);\n Arrays.sort(sortedByY, Comparator.comparingDouble(p -> p.y));\n\n return closestPair(sortedByX, sortedByY, 0, points.length - 1);\n }\n\n private static double closestPair(Point[] px, Point[] py, int left, int right) {\n // Base case: brute force for small inputs\n if (right - left <= 3) {\n return bruteForce(px, left, right);\n }\n\n // DIVIDE: find midpoint\n int mid = left + (right - left) / 2;\n Point midPoint = px[mid];\n\n // Split py into left and right halves\n List pyLeft = new ArrayList<>();\n List pyRight = new ArrayList<>();\n for (Point p : py) {\n if (p.x <= midPoint.x) {\n pyLeft.add(p);\n } else {\n pyRight.add(p);\n }\n }\n\n // CONQUER: find closest pairs in each half\n double dLeft = closestPair(px, pyLeft.toArray(new Point[0]), left, mid);\n double dRight = closestPair(px, pyRight.toArray(new Point[0]), mid + 1, right);\n double d = Math.min(dLeft, dRight);\n\n // COMBINE: check strip around the dividing line\n List strip = new ArrayList<>();\n for (Point p : py) {\n if (Math.abs(p.x - midPoint.x) < d) {\n strip.add(p);\n }\n }\n\n // Check strip (only need to check 7 points ahead due to geometry)\n return Math.min(d, stripClosest(strip, d));\n }\n\n private static double stripClosest(List strip, double d) {\n double minDist = d;\n for (int i = 0; i < strip.size(); i++) {\n // Only check next 7 points (geometric property)\n for (int j = i + 1; j < strip.size() && j < i + 8; j++) {\n double dist = distance(strip.get(i), strip.get(j));\n minDist = Math.min(minDist, dist);\n }\n }\n return minDist;\n }\n\n private static double bruteForce(Point[] points, int left, int right) {\n double minDist = Double.MAX_VALUE;\n for (int i = left; i <= right; i++) {\n for (int j = i + 1; j <= right; j++) {\n minDist = Math.min(minDist, distance(points[i], points[j]));\n }\n }\n return minDist;\n }\n\n private static double distance(Point p1, Point p2) {\n return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));\n }\n}\n\nclass Point {\n double x, y;\n Point(double x, double y) { this.x = x; this.y = y; }\n}\n```\n\n**Why O(n log n)?**\n\n- Sorting: O(n log n)\n- T(n) = 2T(n/2) + O(n) for divide/conquer/combine\n- By Master Theorem: O(n log n)\n\n### 5. Parallel D&C with Fork/Join\n\nD&C is naturally parallelizable - subproblems are independent!\n\n```java\n// ✅ Parallel MergeSort using Fork/Join\npublic class ParallelMergeSort extends RecursiveAction {\n private static final int THRESHOLD = 10000;\n private final int[] arr;\n private final int[] temp;\n private final int left, right;\n\n public ParallelMergeSort(int[] arr, int[] temp, int left, int right) {\n this.arr = arr;\n this.temp = temp;\n this.left = left;\n this.right = right;\n }\n\n @Override\n protected void compute() {\n if (right - left < THRESHOLD) {\n // Sequential sort for small arrays\n Arrays.sort(arr, left, right + 1);\n return;\n }\n\n int mid = left + (right - left) / 2;\n\n // Fork: create tasks for both halves\n ParallelMergeSort leftTask = new ParallelMergeSort(arr, temp, left, mid);\n ParallelMergeSort rightTask = new ParallelMergeSort(arr, temp, mid + 1, right);\n\n // Execute in parallel\n invokeAll(leftTask, rightTask);\n\n // Merge results\n merge(arr, temp, left, mid, right);\n }\n\n private void merge(int[] arr, int[] temp, int left, int mid, int right) {\n // Same merge as before...\n System.arraycopy(arr, left, temp, left, right - left + 1);\n\n int i = left, j = mid + 1, k = left;\n while (i <= mid && j <= right) {\n arr[k++] = (temp[i] <= temp[j]) ? temp[i++] : temp[j++];\n }\n while (i <= mid) arr[k++] = temp[i++];\n }\n\n // Usage\n public static void parallelSort(int[] arr) {\n int[] temp = new int[arr.length];\n ForkJoinPool pool = ForkJoinPool.commonPool();\n pool.invoke(new ParallelMergeSort(arr, temp, 0, arr.length - 1));\n }\n}\n```\n\n**Speedup:** On 8 cores, expect ~4-6x speedup (limited by merge step which is sequential).\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Not Handling Base Case Correctly\n\n```java\n// ❌ Missing base case - infinite recursion\nprivate static void mergeSort(int[] arr, int left, int right) {\n int mid = left + (right - left) / 2;\n mergeSort(arr, left, mid); // Never stops!\n mergeSort(arr, mid + 1, right);\n merge(arr, left, mid, right);\n}\n\n// ✅ Correct base case\nprivate static void mergeSort(int[] arr, int left, int right) {\n if (left >= right) return; // Base case: 0 or 1 elements\n\n int mid = left + (right - left) / 2;\n mergeSort(arr, left, mid);\n mergeSort(arr, mid + 1, right);\n merge(arr, left, mid, right);\n}\n```\n\n### Mistake 2: Incorrect Midpoint Calculation\n\n```java\n// ❌ Integer overflow for large arrays\nint mid = (left + right) / 2; // If left + right > Integer.MAX_VALUE\n\n// ✅ Safe calculation\nint mid = left + (right - left) / 2;\n```\n\n### Mistake 3: Wrong Subarray Boundaries\n\n```java\n// ❌ Off-by-one errors\nmergeSort(arr, left, mid - 1); // Misses element at mid\nmergeSort(arr, mid, right); // Includes mid twice\n\n// ✅ Correct boundaries\nmergeSort(arr, left, mid); // [left, mid]\nmergeSort(arr, mid + 1, right); // [mid+1, right]\n```\n\n---\n\n## 🐛 Debug This\n\nThe following MergeSort implementation has a bug. Find it:\n\n```java\npublic class BuggyMergeSort {\n\n public static void sort(int[] arr) {\n int[] temp = new int[arr.length];\n mergeSort(arr, temp, 0, arr.length - 1);\n }\n\n private static void mergeSort(int[] arr, int[] temp, int left, int right) {\n if (left >= right) return;\n\n int mid = left + (right - left) / 2;\n mergeSort(arr, temp, left, mid);\n mergeSort(arr, temp, mid + 1, right);\n merge(arr, temp, left, mid, right);\n }\n\n private static void merge(int[] arr, int[] temp, int left, int mid, int right) {\n // Copy to temp\n for (int i = left; i <= right; i++) {\n temp[i] = arr[i];\n }\n\n int i = left, j = mid + 1, k = left;\n\n while (i <= mid && j <= right) {\n if (temp[i] <= temp[j]) {\n arr[k++] = temp[i++];\n } else {\n arr[k++] = temp[j++];\n }\n }\n\n // Copy remaining from RIGHT half\n while (j <= right) {\n arr[k++] = temp[j++];\n }\n }\n}\n\n// Test: sort([5, 2, 8, 1, 9])\n// Expected: [1, 2, 5, 8, 9]\n// Actual: [1, 2, 8, 8, 9] (wrong!)\n```\n\n

Click to reveal the bug and solution

\n\n**The Bug:**\n\nThe code only copies remaining elements from the RIGHT half, but forgets the LEFT half!\n\nWhen the right half is exhausted first, left elements remain in temp but aren't copied to arr.\n\n**Trace:**\n```text\nMerging [2, 5] and [1]\ntemp = [2, 5, 1]\nAfter while loop: arr = [1, _, _], i=0, j=3 (j > right)\nMissing: while (i <= mid) to copy 2 and 5!\n```\n\n**The Fix:**\n\n```java\nprivate static void merge(int[] arr, int[] temp, int left, int mid, int right) {\n for (int i = left; i <= right; i++) {\n temp[i] = arr[i];\n }\n\n int i = left, j = mid + 1, k = left;\n\n while (i <= mid && j <= right) {\n if (temp[i] <= temp[j]) {\n arr[k++] = temp[i++];\n } else {\n arr[k++] = temp[j++];\n }\n }\n\n // ✅ Copy remaining from LEFT half\n while (i <= mid) {\n arr[k++] = temp[i++];\n }\n\n // Right half elements are already in place in arr\n // (no need to copy them)\n}\n```\n\n**Note:** We don't need to copy remaining right elements because they're already in the correct position in `arr`.\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Count Inversions ⭐⭐\n\nAn inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Count inversions using D&C.\n\n```java\n// Brute force is O(n²). Use D&C to achieve O(n log n)\npublic static long countInversions(int[] arr) {\n // Your code here\n}\n\n// Example: [2, 4, 1, 3, 5]\n// Inversions: (2,1), (4,1), (4,3) → count = 3\n```\n\n

Solution

\n\n```java\npublic static long countInversions(int[] arr) {\n int[] temp = new int[arr.length];\n return mergeSortCount(arr, temp, 0, arr.length - 1);\n}\n\nprivate static long mergeSortCount(int[] arr, int[] temp, int left, int right) {\n if (left >= right) return 0;\n\n int mid = left + (right - left) / 2;\n\n long count = 0;\n count += mergeSortCount(arr, temp, left, mid);\n count += mergeSortCount(arr, temp, mid + 1, right);\n count += mergeCount(arr, temp, left, mid, right);\n\n return count;\n}\n\nprivate static long mergeCount(int[] arr, int[] temp, int left, int mid, int right) {\n for (int i = left; i <= right; i++) temp[i] = arr[i];\n\n int i = left, j = mid + 1, k = left;\n long inversions = 0;\n\n while (i <= mid && j <= right) {\n if (temp[i] <= temp[j]) {\n arr[k++] = temp[i++];\n } else {\n // All remaining elements in left half are > temp[j]\n inversions += (mid - i + 1);\n arr[k++] = temp[j++];\n }\n }\n\n while (i <= mid) arr[k++] = temp[i++];\n\n return inversions;\n}\n```\n\nKey insight: When we take an element from the right half, it's smaller than all remaining elements in the left half. So we add (mid - i + 1) inversions.\n

\n\n---\n\n### Exercise 2: Maximum Subarray Sum ⭐⭐\n\nFind the contiguous subarray with the maximum sum using D&C.\n\n```java\n// Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]\n// Maximum subarray: [4, -1, 2, 1] with sum 6\npublic static int maxSubarraySum(int[] arr) {\n // Your code here\n}\n```\n\n

Solution

\n\n```java\npublic static int maxSubarraySum(int[] arr) {\n return maxSubarray(arr, 0, arr.length - 1);\n}\n\nprivate static int maxSubarray(int[] arr, int left, int right) {\n // Base case\n if (left == right) return arr[left];\n\n int mid = left + (right - left) / 2;\n\n // Max in left half\n int leftMax = maxSubarray(arr, left, mid);\n\n // Max in right half\n int rightMax = maxSubarray(arr, mid + 1, right);\n\n // Max crossing the midpoint\n int crossMax = maxCrossingSum(arr, left, mid, right);\n\n return Math.max(Math.max(leftMax, rightMax), crossMax);\n}\n\nprivate static int maxCrossingSum(int[] arr, int left, int mid, int right) {\n // Find max sum from mid going left\n int leftSum = Integer.MIN_VALUE;\n int sum = 0;\n for (int i = mid; i >= left; i--) {\n sum += arr[i];\n leftSum = Math.max(leftSum, sum);\n }\n\n // Find max sum from mid+1 going right\n int rightSum = Integer.MIN_VALUE;\n sum = 0;\n for (int i = mid + 1; i <= right; i++) {\n sum += arr[i];\n rightSum = Math.max(rightSum, sum);\n }\n\n return leftSum + rightSum;\n}\n```\n\n**Complexity:** T(n) = 2T(n/2) + O(n) = O(n log n)\n\nNote: Kadane's algorithm solves this in O(n), but this D&C approach demonstrates the paradigm.\n

\n\n---\n\n### Exercise 3: Power Function ⭐⭐\n\nImplement power(x, n) in O(log n) using D&C.\n\n```java\n// Calculate x^n efficiently\npublic static double power(double x, int n) {\n // Your code here\n}\n\n// Example: power(2.0, 10) = 1024.0\n// Handle negative exponents too!\n```\n\n

Solution

\n\n```java\npublic static double power(double x, int n) {\n if (n == 0) return 1;\n\n // Handle negative exponent\n long exp = n;\n if (exp < 0) {\n x = 1 / x;\n exp = -exp;\n }\n\n return powerHelper(x, exp);\n}\n\nprivate static double powerHelper(double x, long n) {\n if (n == 0) return 1;\n if (n == 1) return x;\n\n // D&C: x^n = (x^(n/2))^2 * x^(n%2)\n double half = powerHelper(x, n / 2);\n\n if (n % 2 == 0) {\n return half * half;\n } else {\n return half * half * x;\n }\n}\n```\n\n**Complexity:** O(log n) - we halve n each recursive call.\n\nWhy use `long exp`? To handle Integer.MIN_VALUE whose absolute value overflows int.\n

\n\n---\n\n### Exercise 4: Median of Two Sorted Arrays ⭐⭐⭐⭐\n\nFind the median of two sorted arrays in O(log(min(m,n))).\n\n```java\n// Example: nums1 = [1, 3], nums2 = [2]\n// Merged = [1, 2, 3], median = 2.0\npublic static double findMedianSortedArrays(int[] nums1, int[] nums2) {\n // Your code here\n}\n```\n\n

Solution

\n\n```java\npublic static double findMedianSortedArrays(int[] nums1, int[] nums2) {\n // Ensure nums1 is smaller\n if (nums1.length > nums2.length) {\n return findMedianSortedArrays(nums2, nums1);\n }\n\n int m = nums1.length, n = nums2.length;\n int low = 0, high = m;\n\n while (low <= high) {\n int partitionX = (low + high) / 2;\n int partitionY = (m + n + 1) / 2 - partitionX;\n\n int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];\n int minRightX = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX];\n\n int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];\n int minRightY = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY];\n\n if (maxLeftX <= minRightY && maxLeftY <= minRightX) {\n // Found the correct partition\n if ((m + n) % 2 == 0) {\n return (Math.max(maxLeftX, maxLeftY) +\n Math.min(minRightX, minRightY)) / 2.0;\n } else {\n return Math.max(maxLeftX, maxLeftY);\n }\n } else if (maxLeftX > minRightY) {\n high = partitionX - 1;\n } else {\n low = partitionX + 1;\n }\n }\n\n throw new IllegalArgumentException(\"Input arrays are not sorted\");\n}\n```\n\nThis is a binary search on the partition position, not traditional D&C, but uses the same principle of eliminating half the search space.\n

\n\n---\n\n### Exercise 5: Implement Karatsuba Multiplication ⭐⭐⭐⭐\n\nMultiply two n-digit numbers in O(n^1.59) instead of O(n²).\n\n```java\n// Standard multiplication: O(n²)\n// Karatsuba: O(n^log₂(3)) ≈ O(n^1.585)\npublic static BigInteger karatsuba(BigInteger x, BigInteger y) {\n // Your code here\n}\n```\n\n

Solution

\n\n```java\npublic static BigInteger karatsuba(BigInteger x, BigInteger y) {\n // Base case: use standard multiplication for small numbers\n int n = Math.max(x.bitLength(), y.bitLength());\n if (n <= 2000) {\n return x.multiply(y); // Standard multiplication\n }\n\n // Split numbers in half\n int half = (n + 1) / 2;\n BigInteger mask = BigInteger.ONE.shiftLeft(half).subtract(BigInteger.ONE);\n\n BigInteger xLow = x.and(mask); // Lower half of x\n BigInteger xHigh = x.shiftRight(half); // Upper half of x\n BigInteger yLow = y.and(mask); // Lower half of y\n BigInteger yHigh = y.shiftRight(half); // Upper half of y\n\n // Karatsuba's trick: 3 multiplications instead of 4\n BigInteger z0 = karatsuba(xLow, yLow); // xLow * yLow\n BigInteger z2 = karatsuba(xHigh, yHigh); // xHigh * yHigh\n BigInteger z1 = karatsuba(xLow.add(xHigh), yLow.add(yHigh))\n .subtract(z0).subtract(z2); // (xLow + xHigh)(yLow + yHigh) - z0 - z2\n\n // Combine: z2 * 2^(2*half) + z1 * 2^half + z0\n return z2.shiftLeft(2 * half)\n .add(z1.shiftLeft(half))\n .add(z0);\n}\n```\n\n**Why 3 multiplications?**\n\nNormal: (xH×2^n + xL)(yH×2^n + yL) = xH×yH×2^2n + (xH×yL + xL×yH)×2^n + xL×yL\n\nKaratsuba:\n- z0 = xL × yL\n- z2 = xH × yH\n- z1 = (xL + xH)(yL + yH) - z0 - z2 = xH×yL + xL×yH\n\nResult = z2×2^2n + z1×2^n + z0\n\n3 multiplications instead of 4!\n

\n\n---\n\n## 🎤 Interview Questions\n\n### Question #1: Explain the Divide and Conquer paradigm.\n\n**What interviewers want to hear**: Clear explanation of the three steps with examples.\n\n**Strong answer**:\nDivide and Conquer breaks a problem into smaller subproblems, solves them recursively, and combines the results.\n\n**Three steps:**\n1. **Divide**: Split the problem into smaller instances of the same problem\n2. **Conquer**: Solve subproblems recursively (base case handles small inputs directly)\n3. **Combine**: Merge subproblem solutions into the final answer\n\n**Example - MergeSort:**\n- Divide: Split array in half\n- Conquer: Recursively sort both halves\n- Combine: Merge two sorted halves in O(n)\n\n**When to use D&C:**\n- Problem can be broken into similar subproblems\n- Subproblems are independent\n- Combining solutions is efficient\n\n---\n\n### Question #2: Apply the Master Theorem to T(n) = 4T(n/2) + n².\n\n**What interviewers want to hear**: Correct application with reasoning.\n\n**Strong answer**:\nGiven: T(n) = 4T(n/2) + n²\n\nParameters: a = 4, b = 2, f(n) = n²\n\nCalculate: n^(log_b(a)) = n^(log₂(4)) = n²\n\nCompare f(n) with n^(log_b(a)):\n- f(n) = n²\n- n^(log_b(a)) = n²\n\nSince f(n) = Θ(n²) = Θ(n^(log_b(a))), we're in **Case 2** of Master Theorem.\n\n**Result:** T(n) = Θ(n² log n)\n\nThe work is evenly distributed across all levels of recursion.\n\n---\n\n### Question #3: Why is MergeSort preferred over QuickSort for linked lists?\n\n**What interviewers want to hear**: Understanding of memory access patterns.\n\n**Strong answer**:\nMergeSort is better for linked lists for several reasons:\n\n**QuickSort's disadvantages with linked lists:**\n1. No O(1) random access - partition requires O(n) traversal\n2. Choosing good pivot requires random access\n3. Cache unfriendly - nodes scattered in memory\n\n**MergeSort's advantages:**\n1. Only needs sequential access - perfect for linked lists\n2. Finding middle with slow/fast pointers is O(n) but simple\n3. Merge operation is natural for linked lists\n4. Can be done in-place (no extra array needed)\n\n```java\n// MergeSort for LinkedList - O(1) extra space!\nListNode sortList(ListNode head) {\n if (head == null || head.next == null) return head;\n\n // Find middle\n ListNode slow = head, fast = head.next;\n while (fast != null && fast.next != null) {\n slow = slow.next;\n fast = fast.next.next;\n }\n\n ListNode mid = slow.next;\n slow.next = null; // Split\n\n return merge(sortList(head), sortList(mid));\n}\n```\n\n---\n\n### Question #4: How would you parallelize MergeSort?\n\n**What interviewers want to hear**: Understanding of parallelism opportunities and limitations.\n\n**Strong answer**:\nD&C is naturally parallelizable because subproblems are independent.\n\n**Parallelization strategy:**\n1. **Fork:** Create parallel tasks for left and right halves\n2. **Join:** Wait for both to complete\n3. **Merge:** Sequential (must see both sorted halves)\n\n**Considerations:**\n- Use threshold for sequential execution (small arrays not worth forking)\n- Merge is the bottleneck (always sequential)\n- Maximum speedup limited by merge: ~O(n) work can't be parallelized\n- In practice: 4-6x speedup on 8 cores\n\n**Java implementation:**\n```java\nif (size > THRESHOLD) {\n invokeAll(leftTask, rightTask); // Parallel\n} else {\n Arrays.sort(arr, left, right); // Sequential\n}\n```\n\n---\n\n### Question #5: When would D&C NOT be the best approach?\n\n**What interviewers want to hear**: Understanding of trade-offs and alternatives.\n\n**Strong answer**:\nD&C has limitations:\n\n**1. Overlapping subproblems:**\n- If subproblems share sub-subproblems (like Fibonacci), D&C recomputes them\n- Better: Dynamic Programming with memoization\n\n**2. Subproblems aren't independent:**\n- If solving one subproblem requires info from another\n- Example: Finding shortest path (need global info)\n\n**3. High combine cost:**\n- If merging results takes O(n²), you lose the logarithmic benefit\n- D&C gives O(n log n) only when combine is O(n) or less\n\n**4. Deep recursion:**\n- Very deep recursion can cause stack overflow\n- May need to convert to iterative\n\n**5. Better algorithms exist:**\n- Linear time algorithms (Kadane's for max subarray)\n- Hash-based approaches\n- Greedy algorithms\n\n**Rule of thumb:** Use D&C when dividing gives logarithmic depth AND combining is efficient.\n\n---\n\n## 📋 Quick Reference\n\n### D&C Template\n\n```java\nResult solve(Problem p) {\n // Base case\n if (isSmall(p)) {\n return directSolve(p);\n }\n\n // Divide\n Problem[] subproblems = divide(p);\n\n // Conquer\n Result[] subresults = new Result[subproblems.length];\n for (int i = 0; i < subproblems.length; i++) {\n subresults[i] = solve(subproblems[i]);\n }\n\n // Combine\n return combine(subresults);\n}\n```\n\n### Master Theorem Cheat Sheet\n\n| Recurrence | a | b | f(n) | Case | Result |\n|------------|---|---|------|------|--------|\n| T(n) = T(n/2) + O(1) | 1 | 2 | 1 | 2 | O(log n) |\n| T(n) = 2T(n/2) + O(n) | 2 | 2 | n | 2 | O(n log n) |\n| T(n) = 2T(n/2) + O(1) | 2 | 2 | 1 | 1 | O(n) |\n| T(n) = 4T(n/2) + O(n) | 4 | 2 | n | 1 | O(n²) |\n| T(n) = 3T(n/2) + O(n) | 3 | 2 | n | 1 | O(n^1.59) |\n\n### Classic D&C Algorithms\n\n| Algorithm | Divide | Conquer | Combine | Complexity |\n|-----------|--------|---------|---------|------------|\n| Binary Search | Half array | One side | None | O(log n) |\n| MergeSort | Two halves | Both sides | Merge | O(n log n) |\n| QuickSort | Partition | Both sides | None | O(n log n) avg |\n| QuickSelect | Partition | One side | None | O(n) avg |\n| Closest Pair | Half by x | Both sides | Check strip | O(n log n) |\n| Karatsuba | Half digits | Three muls | Add/shift | O(n^1.59) |\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### Core Principles\n\n1. **D&C = Divide + Conquer + Combine** - the three-step dance\n2. **Master Theorem** is your complexity calculator for recurrences\n3. **Logarithmic reduction** is powerful - halving n log n times\n4. **Combine step is key** - must be efficient for overall efficiency\n5. **D&C parallelizes well** - subproblems are independent\n\n### What You Can Do Now\n\n- Apply the D&C paradigm to break down complex problems\n- Use Master Theorem to analyze recurrence relations\n- Implement MergeSort, QuickSelect, and other D&C algorithms\n- Recognize when D&C applies vs other approaches\n- Parallelize D&C algorithms using Fork/Join\n\n---\n\n## 📅 Review Schedule\n\n| Day | Task | Time |\n|-----|------|------|\n| Day 1 | Review Master Theorem cases | 5 min |\n| Day 3 | Implement MergeSort from memory | 15 min |\n| Day 7 | Solve Count Inversions exercise | 15 min |\n| Day 14 | Redo Debug This exercise | 10 min |\n| Day 30 | Implement QuickSelect from memory | 15 min |\n\n---\n\n*Next in series: [Part 4: Comparison-Based Sorting Deep Dive - QuickSort, MergeSort, HeapSort & TimSort]*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.038275Z","createdAt","2026-06-10T07:19:25.039137Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",22,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder","author",{"_31":55,"_98":57,"_99":100,"_101":102,"_103":-5,"_104":-5,"_105":-5,"_106":-5,"_107":-5},"category",{"_31":94,"_72":59,"_35":95,"_75":96,"_97":-5},"tags",[78,79,80,81],"series",{"_31":62,"_72":73,"_35":74,"_75":76,"_77":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":91,"_72":92,"_35":93},{"_31":88,"_72":89,"_35":90},{"_31":85,"_72":86,"_35":87},{"_31":82,"_72":83,"_35":84},131,"Quicksort","quicksort",132,"Mergesort","mergesort",130,"Master Theorem","master-theorem",129,"Divide And Conquer","divide-and-conquer",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]