01
Divide & Conquer Pattern
Divide & Conquer
Divide the problem into smaller subproblems, Conquer by solving subproblems recursively, Combine solutions. Reduces time complexity from O(n) to O(log n) or O(n log n).
// General D&C Template
Result divideAndConquer(Problem problem) {
// Base case
if (problem.isSmall()) {
return solveDirectly(problem);
}
// Divide
Problem left = problem.leftHalf();
Problem right = problem.rightHalf();
// Conquer
Result leftResult = divideAndConquer(left);
Result rightResult = divideAndConquer(right);
// Combine
return combine(leftResult, rightResult);
}
// Master Theorem for T(n) = aT(n/b) + f(n)
// Case 1: f(n) = O(n^(logb(a) - ε)) → T(n) = Θ(n^logb(a))
// Case 2: f(n) = Θ(n^logb(a)) → T(n) = Θ(n^logb(a) * log n)
// Case 3: f(n) = Ω(n^(logb(a) + ε)) → T(n) = Θ(f(n))Step-by-Step Breakdown:
- Base Case: If the problem is small enough, solve it directly (no more division needed)
- Divide: Split the problem into two halves (left and right)
- Conquer: Recursively solve each half - this is where the magic happens!
- Combine: Merge the solutions from both halves into the final answer
Visual: D&C Approach
┌─────────────────────────────┐
│ Original Problem │
│ [1,5,3,8,2,7] │
└─────────────┬───────────────┘
│ DIVIDE
┌─────────────┴───────────────┐
▼ ▼
┌───────────┐ ┌───────────┐
│ [1,5,3] │ │ [8,2,7] │
└─────┬─────┘ └─────┬─────┘
│ DIVIDE │ DIVIDE
┌────┴────┐ ┌────┴────┐
▼ ▼ ▼ ▼
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│[1,5]│ │ [3] │ │[8,2]│ │ [7] │
└──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘
│ │ │ │
▼ ▼ ▼ ▼
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│[1,5]│ │ [3] │ CONQUER │[2,8]│ │ [7] │
└──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘
│ │ │ │
└───┬────┘ └───┬────┘
▼ COMBINE ▼ COMBINE
┌─────────┐ ┌─────────┐
│ [1,3,5] │ │ [2,7,8] │
└────┬────┘ └────┬────┘
│ │
└───────────┬───────────────┘
▼ COMBINE
┌─────────────────┐
│ [1,2,3,5,7,8] │ ✅ Sorted!
└─────────────────┘
Recursion Tree Visualization
dc(0,7) ← Level 0: n work
/ \
dc(0,3) dc(4,7) ← Level 1: n/2 + n/2 = n work
/ \ / \
dc(0,1) dc(2,3) dc(4,5) dc(6,7) ← Level 2: 4 × n/4 = n work
/ \ / \ / \ / \
0 1 2 3 4 5 6 7 ← Level log(n): n × O(1) = n work
Total Levels: log₂(n)
Work per Level: O(n)
Total Time: O(n log n)
02
Binary Search Variants
// Standard Binary Search - O(log n)
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Not found
}
// Lower Bound - First element >= target
int lowerBound(int[] arr, int target) {
int left = 0, right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// Upper Bound - First element > target
int upperBound(int[] arr, int target) {
int left = 0, right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// Find First and Last Position
int[] searchRange(int[] nums, int target) {
int first = lowerBound(nums, target);
if (first == nums.length || nums[first] != target) {
return new int[]{-1, -1};
}
int last = upperBound(nums, target) - 1;
return new int[]{first, last};
}
// Binary Search on Answer - Minimum capacity
int minCapacity(int[] weights, int days) {
int left = Arrays.stream(weights).max().getAsInt();
int right = Arrays.stream(weights).sum();
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
boolean canShip(int[] weights, int days, int capacity) {
int daysNeeded = 1, current = 0;
for (int w : weights) {
if (current + w > capacity) {
daysNeeded++;
current = 0;
}
current += w;
}
return daysNeeded <= days;
}Binary Search Variants Explained:
- Standard Binary Search: Find exact target - return index or -1
- Lower Bound: Find first element ≥ target (insertion point for smaller)
- Upper Bound: Find first element > target (insertion point for larger)
- Search Range: Combine lower/upper bound to find first & last occurrence
- Binary Search on Answer: When the answer is in a range, verify if mid works!
Pro Tip: Use
left + (right - left) / 2 instead of (left + right) / 2 to prevent integer overflow!
03
Quick Select Algorithm
Quick Select: Find kth smallest/largest element in O(n) average time.
Uses partition from Quick Sort but only recurses on one side.
// Quick Select - O(n) average, O(n²) worst
// Find kth smallest element (0-indexed)
int quickSelect(int[] arr, int left, int right, int k) {
if (left == right) return arr[left];
// Random pivot for better average case
int randIdx = left + (int)(Math.random() * (right - left + 1));
swap(arr, randIdx, right);
int pivotIdx = partition(arr, left, right);
if (k == pivotIdx) {
return arr[k];
} else if (k < pivotIdx) {
return quickSelect(arr, left, pivotIdx - 1, k);
} else {
return quickSelect(arr, pivotIdx + 1, right, k);
}
}
int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
swap(arr, ++i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Find Kth Largest = Find (n-k)th smallest
int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
// Median of Two Sorted Arrays - O(log(min(m,n)))
double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length, n = nums2.length;
int left = 0, right = m;
while (left <= right) {
int i = (left + right) / 2;
int j = (m + n + 1) / 2 - i;
int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 == 0) {
return (Math.max(maxLeft1, maxLeft2) +
Math.min(minRight1, minRight2)) / 2.0;
} else {
return Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
right = i - 1;
} else {
left = i + 1;
}
}
return 0;
}Quick Select Step-by-Step:
- Choose Random Pivot: Randomization avoids worst-case O(n²) scenarios
- Partition: Move elements smaller than pivot to left, larger to right
- Compare k with pivot index:
- If k == pivotIdx → Found it! Return the element
- If k < pivotIdx → Recurse on LEFT half only
- If k > pivotIdx → Recurse on RIGHT half only
- Key insight: Unlike Quick Sort, we only recurse on ONE side → O(n) average!
Quick Select Visualization
Find 3rd smallest (k=2, 0-indexed) in [3, 2, 1, 5, 4, 6]
Step 1: Partition with pivot = 4
┌───┬───┬───┬───┬───┬───┐
│ 3 │ 2 │ 1 │ 5 │ 4 │ 6 │
└───┴───┴───┴───┴───┴───┘
After: [3, 2, 1, 4, 5, 6] pivot at index 3
↑
pivot
k=2 < pivotIdx=3 → Search LEFT half only!
Step 2: Partition [3, 2, 1] with pivot = 2
┌───┬───┬───┐
│ 3 │ 2 │ 1 │
└───┴───┴───┘
After: [1, 2, 3] pivot at index 1
↑
pivot
k=2 > pivotIdx=1 → Search RIGHT half only!
Step 3: Only [3] left, k=2, pivotIdx=2
┌───┐
│ 3 │ ← Found! 3rd smallest = 3
└───┘
04
Search in Rotated Array
// Search in Rotated Sorted Array - O(log n)
int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
// Left half is sorted
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Right half is sorted
else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
// Find Minimum in Rotated Sorted Array
int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
// Minimum is in right half
left = mid + 1;
} else {
// Minimum is in left half (including mid)
right = mid;
}
}
return nums[left];
}
// With Duplicates - O(n) worst case
int findMinWithDuplicates(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
right--; // Can't determine, shrink
}
}
return nums[left];
}Rotated Array Strategy:
- Key Insight: One half is ALWAYS sorted in a rotated array
- Check which half is sorted: If
nums[left] <= nums[mid], left half is sorted - Decide where to search:
- If target is in the sorted half's range → search there
- Otherwise → search the other half
Rotated Array Visualization
Original sorted: [1, 2, 3, 4, 5, 6, 7]
Rotated by 3: [4, 5, 6, 7, 1, 2, 3]
↑ ↑ ↑
left mid right
nums[left]=4 <= nums[mid]=7 → LEFT half [4,5,6,7] is sorted!
Looking for target = 2:
- Is 2 in sorted range [4,7]? NO (2 < 4)
- Search RIGHT half: [1, 2, 3]
┌───────────────┬───────────────┐
│ SORTED ✓ │ UNSORTED │
│ [4, 5, 6, 7] │ [1, 2, 3] │
│ target not │ target here! │
│ in range │ ↓ │
└───────────────┴───────────────┘
05
Classic D&C Problems
Peak Element
// Find Peak Element - O(log n)
int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
// Peak is on left side (including mid)
right = mid;
} else {
// Peak is on right side
left = mid + 1;
}
}
return left;
}
// Peak in Mountain Array
int peakIndexInMountainArray(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}Sqrt and Power
// Integer Square Root - O(log n)
int mySqrt(int x) {
if (x < 2) return x;
long left = 1, right = x / 2;
while (left <= right) {
long mid = left + (right - left) / 2;
long sq = mid * mid;
if (sq == x) {
return (int) mid;
} else if (sq < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return (int) right;
}
// Power - O(log n)
double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return power(x, N);
}
double power(double x, long n) {
if (n == 0) return 1.0;
double half = power(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
// Count Inversions - Modified Merge Sort
long countInversions(int[] arr) {
int[] temp = new int[arr.length];
return mergeSort(arr, temp, 0, arr.length - 1);
}
long mergeSort(int[] arr, int[] temp, int left, int right) {
long count = 0;
if (left < right) {
int mid = left + (right - left) / 2;
count += mergeSort(arr, temp, left, mid);
count += mergeSort(arr, temp, mid + 1, right);
count += merge(arr, temp, left, mid, right);
}
return count;
}
long merge(int[] arr, int[] temp, int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
long count = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
count += (mid - i + 1); // Count inversions
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, left, arr, left, right - left + 1);
return count;
}Classic D&C Problems Breakdown:
- Peak Element: Compare mid with mid+1 to determine which side has the peak
- Integer Sqrt: Binary search for the largest x where x² ≤ n
- Power (x^n): Use x^n = (x^(n/2))² to achieve O(log n)
- Count Inversions: Modified merge sort - count during merge phase
Practice Problems
Strengthen your D&C skills with these carefully selected problems, ordered by difficulty:
Easy
Binary Search Basics
Medium
Quick Select & Kth Element
Key Takeaways
Binary Search = O(log n)
Left/right pointers, mid = left + (right-left)/2 to avoid overflow.
Quick Select = O(n) avg
Find kth element without full sorting. Only recurse one side.
Rotated Array
Check which half is sorted, then decide search direction.
Binary Search on Answer
When answer is in range, check if mid satisfies condition.
Knowledge Check
Question 1 of 6
What is Quick Select's average time complexity?
Question 2 of 6
Why use mid = left + (right - left) / 2 instead of (left + right) / 2?
Question 3 of 6
In a rotated sorted array, how do we determine which half is sorted?
Question 4 of 6
Lower bound returns the first element that is:
Question 5 of 6
What is the key insight for binary search on answer problems?
Question 6 of 6
What is Quick Select's worst-case time complexity?