Skip to main content
Mapagam

Implementing Divide and Conquer

1. Applying Divide and Conquer Technique

Step Description Example
Divide Break the problem into smaller subproblems. 
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
}
Conquer Solve subproblems recursively. 
const sortedLeft = mergeSort(left);
const sortedRight = mergeSort(right);
Combine Combine solutions to form the final result. return merge(sortedLeft, sortedRight);

Example: Merge Sort Implementation

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
Note: Divide and conquer is particularly effective for problems that can be broken down into independent subproblems, such as sorting algorithms like merge sort and quicksort.

2. Implementing Merge Sort

Property Description Example
Time Complexity Best case: O(n log n), Average case: O(n log n), Worst case: O(n log n) O(n log n)
Space Complexity O(n) due to temporary arrays used during merging O(n)
Stability Stable sorting algorithm Yes
Paradigm Divide and Conquer Divide, conquer, combine

Example: Merge Sort Implementation in JavaScript

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Example usage:
const array = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(array)); // [3, 9, 10, 27, 38, 43, 82]
Note: Merge Sort is a stable, comparison-based sorting algorithm that divides the input into halves recursively until individual elements are isolated, then merges them back together in sorted order.

3. Implementing Quick Sort

Property Description Example
pivot selection Element chosen to partition the array last element
partitioning Reorganizes array around pivot smaller elements to left, larger to right
recursion Applies same logic to subarrays sort left and right partitions

Example: Quick Sort Implementation

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

const nums = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort(nums)); // [11, 12, 22, 25, 34, 64, 90]
Note: Time complexity varies: O(n log n) average, O(n²) worst case.

4. Finding Maximum Subarray

Approach Description Time Complexity Space Complexity
Divide and Conquer Recursively divides array into halves, computes max subarray in left, right, and crossing middle O(n log n) O(log n)
Kadane's Algorithm Dynamic programming approach that tracks local and global max at each index O(n) O(1)

Example: Divide and Conquer Implementation

function maxSubarray(arr, low, high) {
  if (low === high) return { sum: arr[low], start: low, end: high };

  const mid = Math.floor((low + high) / 2);
  const left = maxSubarray(arr, low, mid);
  const right = maxSubarray(arr, mid + 1, high);
  const cross = maxCrossingSubarray(arr, low, mid, high);

  if (left.sum >= right.sum && left.sum >= cross.sum) {
    return left;
  } else if (right.sum >= cross.sum) {
    return right;
  } else {
    return cross;
  }
}

function maxCrossingSubarray(arr, low, mid, high) {
  let leftSum = -Infinity;
  let sum = 0;
  let maxLeft = mid;

  for (let i = mid; i >= low; i--) {
    sum += arr[i];
    if (sum > leftSum) {
      leftSum = sum;
      maxLeft = i;
    }
  }

  let rightSum = -Infinity;
  sum = 0;
  let maxRight = mid + 1;

  for (let i = mid + 1; i <= high; i++) {
    sum += arr[i];
    if (sum > rightSum) {
      rightSum = sum;
      maxRight = i;
    }
  }

  return {
    sum: leftSum + rightSum,
    start: maxLeft,
    end: maxRight
  };
}

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const result = maxSubarray(arr, 0, arr.length - 1);
console.log("Max sum: ", result.sum); // 6
console.log("Start index: ", result.start); // 3
console.log("End index: ", result.end); // 6

Example: Kadane's Algorithm Implementation

function maxSubarraySum(arr) {
  let maxSoFar = arr[0];
  let maxEndingHere = arr[0];

  for (let i = 1; i < arr.length; i++) {
    maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }

  return maxSoFar;
}

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubarraySum(arr)); // 6

Comparison of Approaches

  • Divide and Conquer: More intuitive but slower due to recursion overhead
  • Kadane's Algorithm: Optimal for time and space complexity
Property Description Example
Array Sorted array of elements to search [1, 3, 5, 7, 9, 11]
Target Element to find in the array 7
Time Complexity Best case: O(1), Average/Worst: O(log n)
Space Complexity O(1) for iterative, O(log n) for recursive 
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1; // Not found
}

const arr = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(arr, 7)); // Output: 3
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;

  let mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) {
    return mid;
  } else if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

const arr = [1, 3, 5, 7, 9, 11];
console.log(binarySearchRecursive(arr, 7)); // Output: 3
Note: Binary search requires a sorted array to function correctly.

6. Solving Closest Pair of Points

The Closest Pair of Points problem involves finding the two points with the minimum Euclidean distance in a set of points in 2D space. A divide-and-conquer approach can solve this efficiently with O(n log n) time complexity.

Step Description Time Complexity
Divide Split the set of points into two halves by x-coordinate. O(n log n)
Conquer Recursively find the closest pairs in each half. O(n log n)
Combine Find the closest pair across the dividing line. O(n)

Example: Closest Pair of Points Algorithm

function distance(p1, p2) {
  return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
}

function bruteForce(points) {
  let minDist = Infinity;
  let closestPair = null;

  for (let i = 0; i < points.length; i++) {
    for (let j = i + 1; j < points.length; j++) {
      const dist = distance(points[i], points[j]);
      if (dist < minDist) {
        minDist = dist;
        closestPair = [points[i], points[j]];
      }
    }
  }

  return { minDist, closestPair };
}

function closestPairRec(px, py) {
  if (px.length <= 3) return bruteForce(px);

  const mid = Math.floor(px.length / 2);
  const Qx = px.slice(0, mid);
  const Rx = px.slice(mid);

  const xMid = px[mid].x;
  const Qy = py.filter(p => p.x <= xMid);
  const Ry = py.filter(p => p.x > xMid);

  const { minDist: leftMin, closestPair: leftPair } = closestPairRec(Qx, Qy);
  const { minDist: rightMin, closestPair: rightPair } = closestPairRec(Rx, Ry);

  const minDist = Math.min(leftMin, rightMin);
  const closestPair = leftMin < rightMin ? leftPair : rightPair;

  const strip = py.filter(p => Math.abs(p.x - xMid) < minDist);

  const stripClosest = closestInStrip(strip, minDist);
  if (stripClosest.minDist < minDist) {
    return stripClosest;
  }

  return { minDist, closestPair };
}

function closestInStrip(strip, minDist) {
  let closestPair = null;
  let min = minDist;

  for (let i = 0; i < strip.length; i++) {
    for (let j = i + 1; j < strip.length && (strip[j].y - strip[i].y) < min; j++) {
      const dist = distance(strip[i], strip[j]);
      if (dist < min) {
        min = dist;
        closestPair = [strip[i], strip[j]];
      }
    }
  }

  return { minDist: min, closestPair };
}

function closestPair(points) {
  const px = [...points].sort((a, b) => a.x - b.x);
  const py = [...points].sort((a, b) => a.y - b.y);
  return closestPairRec(px, py);
}

// Example usage:
const points = [
  { x: 2, y: 3 },
  { x: 12, y: 30 },
  { x: 40, y: 50 },
  { x: 5, y: 1 },
  { x: 12, y: 10 }
];

const result = closestPair(points);
console.log(result); // Closest pair and distance

7. Implementing Strassen's Matrix Multiplication

Strassen's algorithm is a divide-and-conquer approach to matrix multiplication that reduces the number of multiplications required compared to the standard O(n³) method.

Operation Description Time Complexity Space Complexity
Standard Matrix Multiplication Multiplies two n×n matrices using nested loops. O(n³) O(n²)
Strassen's Algorithm Divides matrices into submatrices and uses 7 recursive multiplications instead of 8. O(n^2.807) O(n²)

Example: Strassen's Matrix Multiplication Implementation

function strassenMultiply(A, B) {
  const n = A.length;
  if (n === 1) return [[A[0][0] * B[0][0]]];

  const mid = Math.floor(n / 2);
  const A11 = A.slice(0, mid).map(row => row.slice(0, mid));
  const A12 = A.slice(0, mid).map(row => row.slice(mid));
  const A21 = A.slice(mid).map(row => row.slice(0, mid));
  const A22 = A.slice(mid).map(row => row.slice(mid));

  const B11 = B.slice(0, mid).map(row => row.slice(0, mid));
  const B12 = B.slice(0, mid).map(row => row.slice(mid));
  const B21 = B.slice(mid).map(row => row.slice(0, mid));
  const B22 = B.slice(mid).map(row => row.slice(mid));

  const M1 = strassenMultiply(add(A11, A22), add(B11, B22));
  const M2 = strassenMultiply(add(A21, A22), B11);
  const M3 = strassenMultiply(A11, subtract(B12, B22));
  const M4 = strassenMultiply(A22, subtract(B21, B11));
  const M5 = strassenMultiply(add(A11, A12), B22);
  const M6 = strassenMultiply(subtract(A21, A11), add(B11, B12));
  const M7 = strassenMultiply(subtract(A12, A22), add(B21, B22));

  const C11 = add(subtract(add(M1, M4), M5), M7);
  const C12 = add(M3, M5);
  const C21 = add(M2, M4);
  const C22 = add(subtract(add(M1, M3), M2), M6);

  return C11.concat(C21).map((row, i) => row.concat(C12[i]).concat(C22[i]));
}

function add(A, B) {
  return A.map((row, i) => row.map((val, j) => val + B[i][j]));
}

function subtract(A, B) {
  return A.map((row, i) => row.map((val, j) => val - B[i][j]));
}
Note: Strassen's algorithm is more efficient for large matrices but has higher constant factors and is less stable numerically than standard multiplication.

8. Finding Majority Element

A majority element in an array is an element that appears more than n/2 times, where n is the size of the array.

Approach Description Time Complexity Space Complexity
Brute Force Count occurrences of each element using nested loops. O(n^2) O(1)
Hash Map Use a hash map to count occurrences of each element. O(n) O(n)
Boyer-Moore Majority Vote Algorithm Efficiently find the majority element in one pass with constant space. O(n) O(1)

Example: Boyer-Moore Majority Vote Algorithm

function majorityElement(nums) {
    let candidate = null;
    let count = 0;

    for (let num of nums) {
        if (count === 0) {
            candidate = num;
        }
        count += (num === candidate) ? 1 : -1;
    }

    return candidate;
}

// Example usage
const nums = [3, 2, 3];
console.log(majorityElement(nums)); // Output: 3
Note: The Boyer-Moore Majority Vote Algorithm assumes that a majority element exists in the array.

9. Solving Count of Smaller Numbers

Given an array of integers, return an array where each element represents the count of smaller numbers to the right of that element.

Input Output Description
nums = [5, 2, 6, 1] [2, 1, 1, 0] For 5 there are 2 smaller numbers to the right (2 and 1). For 2, there is 1 smaller number (1), etc.

Example: Using Merge Sort

function countSmaller(nums) {
    const result = new Array(nums.length).fill(0);
    const indexedNums = nums.map((num, index) => [num, index]);
    
    function merge(left, right) {
        const merged = [];
        let i = 0, j = 0;
        let count = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i][0] <= right[j][0]) {
                merged.push(left[i]);
                result[left[i][1]] += count;
                i++;
            } else {
                merged.push(right[j]);
                count++;
                j++;
            }
        }
        
        while (i < left.length) {
            merged.push(left[i]);
            result[left[i][1]] += count;
            i++;
        }
        
        while (j < right.length) {
            merged.push(right[j]);
            j++;
        }
        
        return merged;
    }
    
    function mergeSort(arr) {
        if (arr.length <= 1) return arr;
        
        const mid = Math.floor(arr.length / 2);
        const left = mergeSort(arr.slice(0, mid));
        const right = mergeSort(arr.slice(mid));
        
        return merge(left, right);
    }
    
    mergeSort(indexedNums);
    return result;
}

// Example usage:
console.log(countSmaller([5, 2, 6, 1])); // [2, 1, 1, 0]
Note: This approach uses a modified merge sort to efficiently count smaller elements in O(n log n) time.

10. Implementing Karatsuba Multiplication

Karatsuba multiplication is a fast algorithm for multiplying large numbers, reducing the complexity from O(n²) to approximately O(n^1.585).

Property Description Notes
Algorithm Type Divide and Conquer Reduces multiplication to three smaller multiplications
Time Complexity O(n^1.585) Improves upon O(n²) classical multiplication
Space Complexity O(n) Due to recursive stack and temporary arrays

Example: Karatsuba Multiplication in JavaScript

function karatsuba(x, y) {
  // Convert to strings for easier manipulation
  const xStr = x.toString();
  const yStr = y.toString();

  // Base case: if numbers are small, use standard multiplication
  if (xStr.length < 10 || yStr.length < 10) {
    return x * y;
  }

  // Make lengths equal by padding with zeros
  const maxLength = Math.max(xStr.length, yStr.length);
  const paddedLength = Math.pow(2, Math.ceil(Math.log(maxLength) / Math.log(2)));
  const paddedX = xStr.padStart(paddedLength, '0');
  const paddedY = yStr.padStart(paddedLength, '0');

  // Split the numbers into halves
  const half = paddedLength / 2;
  const a = parseInt(paddedX.slice(0, half));
  const b = parseInt(paddedX.slice(half));
  const c = parseInt(paddedY.slice(0, half));
  const d = parseInt(paddedY.slice(half));

  // Recursive calls
  const ac = karatsuba(a, c);
  const bd = karatsuba(b, d);
  const adPlusBc = karatsuba(a + b, c + d) - ac - bd;

  // Combine results
  return ac * Math.pow(10, paddedLength) + adPlusBc * Math.pow(10, half) + bd;
}

// Example usage:
const result = karatsuba(1234, 5678);
console.log(result); // Output: 7006652
Note: The Karatsuba algorithm is most effective for very large numbers. For small numbers, the overhead of recursion makes it slower than standard multiplication.

11. Solving Reverse Pairs

Reverse pairs in an array are defined as a pair of indices (i, j) such that:

  • i < j
  • nums[i] > 2 * nums[j]

This problem is commonly solved using a modified merge sort algorithm to efficiently count reverse pairs while maintaining the order of elements.

Example: Counting Reverse Pairs

function reversePairs(nums) {
    if (nums.length <= 1) return 0;
    
    function mergeSort(left, right) {
        if (left >= right) return 0;
        
        const mid = Math.floor((left + right) / 2);
        let count = mergeSort(left, mid) + mergeSort(mid + 1, right);
        
        // Count reverse pairs between left and right subarrays
        let j = mid + 1;
        for (let i = left; i <= mid; i++) {
            while (j <= right && nums[i] <= 2 * nums[j]) j++;
            count += j - (mid + 1);
        }
        
        // Merge the two sorted subarrays
        const temp = [];
        let i = left, k = mid + 1;
        while (i <= mid || k <= right) {
            if (k > right || (i <= mid && nums[i] <= nums[k])) {
                temp.push(nums[i++]);
            } else {
                temp.push(nums[k++]);
            }
        }
        
        for (let i = 0; i < temp.length; i++) {
            nums[left + i] = temp[i];
        }
        
        return count;
    }
    
    return mergeSort(0, nums.length - 1);
}

// Example usage:
const nums = [1, 3, 2, 3, 1];
console.log(reversePairs(nums)); // Output: 2
Property Description Notes
nums[i] > 2 * nums[j] Condition for a reverse pair Valid only when i < j
Time Complexity O(n log n) Due to merge sort approach
Space Complexity O(n) For temporary arrays during merge
Note: The merge sort approach allows efficient counting of reverse pairs by leveraging the sorted nature of subarrays during the merge step.

Was this article helpful?

Related Cheat Sheets