Applications of Bisection
- O(n) optimize to logn, o(n^2) to O(nlog$the_range)
- Know the search Space: range(min, max), index
- calculation error(tolerance) should be less than
- Suppose we know the value, we can easily determine whether the value is true/possible
- With O(n) time
- Use greedy to to check, time complexity: O(n) or less
- Sliding window
- Two Pointers
- isPossible(*, int curValue)
- minimum is maximized
Detail
- error (tolerance) as part of the API
Search space
- range: smallest to largest
- index
validate the answer is right
public int woodCut(int[] L, int k) {
int lo = 1;
int hi = 0;
for (int i = 0; i < L.length; i++) {
hi = Math.max(hi, L[i]);
}
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
int pieces = getPieces(mid, L);
if (pieces < k) {
hi = mid - 1;
} else {
lo = mid;
}
}
if (getPieces(lo, L) >= k) {
return lo;
} else {
return 0;
}
}
private int getPieces(int len, int[] L) {
int ans = 0;
for (int l : L) {
ans += l / len;
}
return ans;
}Find kth in sorted matrix
- LeetCode 378 - Kth Smallest Element in a Sorted Matrix
- LeetCode - 719 Find K-th Smallest Pair Distance
public int smallestDistancePair(int[] nums, int k) { Arrays.sort(nums); int lo = 0; int hi = nums[nums.length - 1] - nums[0]; while (lo < hi) { int mi = (lo + hi) / 2; int count = 0, left = 0; for (int right = 0; right < nums.length; ++right) { while (nums[right] - nums[left] > mi) left++; count += right - left; } //count = number of pairs with distance <= mi if (count >= k) hi = mi; else lo = mi + 1; } return lo; } - LeetCode 786 - K-th Smallest Prime Fraction
- A = [1, 2, 3, 5], K = 3: The fractions to be considered in sorted order are: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3. The third fraction is 2/5.
- store p, q during bisection
- PriorityQueue: O(klogk)
public int[] kthSmallestPrimeFraction(int[] A, int K) { double l = 0, r = 1; int p = 0, q = 1; for (int n = A.length, cnt = 0; true; cnt = 0, p = 0) { double m = (l + r) / 2; for (int i = 0, j = n - 1; i < n; i++) { while (j >= 0 && A[i] > m * A[n - 1 - j]) j--; cnt += (j + 1); if (j >= 0 && p * A[n - 1 - j] < q * A[i]) { p = A[i]; q = A[n - 1 - j]; } } if (cnt < K) { l = m; } else if (cnt > K) { r = m; } else { return new int[] {p, q}; } } } - LeetCode 668 - Kth Smallest Number in Multiplication Table: O(m∗log(m∗n))
- LeetCode 644 - Maximum Average Subarray II
- find the contiguous subarray whose length is greater than or equal to k that has the maximum average value.
private boolean canFind(int[] A, int K, double avg) { int i, k; double rightSum = 0, leftSum = 0, minLeftSum = 0; for (i = 0; i < K; ++i) { rightSum += A[i] - avg; } for (i = K; i <= A.length; ++i) { if (rightSum - minLeftSum >= 0) { return true; } if (i < A.length) { rightSum += A[i] - avg; leftSum += A[i - K] - avg; minLeftSum = Math.min(minLeftSum, leftSum); } } return false; } public double maxAverage(int[] A, int K) { int i; double start, stop, mid; start = stop = A[0]; for (i = 0; i < A.length; ++i) { start = Math.min(A[i], start); stop = Math.max(A[i], stop); } while (start + 1e-5 < stop) { mid = (start + stop) / 2; if (canFind(A, K, mid)) { start = mid; } else { stop = mid; } } return start; } - LeetCode 774 - Minimize Max Distance to Gas Station
- add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized
- bisection
- dp[i][j] represents minimum max distance when adding j new gas stations to first i intervals
- dp[i][j] = min(max(dp[i - 1][j - k], (stations[i] - stations[i - 1]) / (k + 1))), for 0<k<j
- base case: dp[i][0] = max(stations[0], …, stations[i - 1]), dp[0][j] = 0
Examples
- LeetCode 287 - Find the Duplicate Number
- Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive)
- Constant space, don’t modify the array
- Bisection (1, n), count(nums, int mid)
- 32(n)
- O(n) find cycle in LinkedList
public int findDuplicate(int[] nums) {
int n = nums.length-1;
int low = 1, high= n;
int mid = 0;
while(low<high) {
mid = low + (high-low)/2;
int c= count(nums, mid); //count #numbers less than mid.
if(c<=mid) {
low = mid+1;
} else {
high = mid;
}
}
return low;
}
private int count(int[] nums, int mid) {
int c =0;
for(int i=0; i<nums.length; i++) {
if(nums[i]<=mid) c++;
}
return c;
}- POJ 2976 Dropping tests
Convert r = max(∑a[i] / ∑b[i]) -> ∑a[i] - ∑b[i] * r = 0
- LeetCode 410 - Split Array Largest Sum
- split the array into m non-empty continuous subarrays and minimize the largest sum among these m subarrays
- f[i][j] = min(max(f[i - 1][k] + nums[k] + nums[k + 1] + … + nums[j]))
- f[1][i] = prefix sum of nums[i]
- bisection
- LeetCode 718 - Maximum Length of Repeated Subarray
- HARD LeetCode 862 - Shortest Subarray with Sum at Least K
- monotone queue on prefix sum
- store the possible values of the start pointer in the queue
- bisection: O(nlognlogn)
- TreeMap: prune bad candidates
public int shortestSubarray(int[] A, int K) { int N = A.length; // Compute cumulative sum int[] cumSum = new int[N]; for (int i = 0; i < N; ++i) { cumSum[i] = i > 0 ? cumSum[i-1] + A[i] : A[i]; } if (!existsSolution(cumSum, K, N)) return -1; // Binary search over all possible lengths int l = 1, r = N; while (l < r) { int m = l + (r-l) / 2; if (existsSolution(cumSum, K, m)) { r = m; } else { l = m+1; } } return l; } boolean existsSolution(int[] cumSum, int K, int len) { // Priority queue that maintains minimal value within the window of size 'len' PriorityQueue<VI> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val)); pq.add(new VI(0, -1)); for (int i = 0; i < cumSum.length; ++i) { // Clean up minimal elements that are outside of the window while (!pq.isEmpty() && pq.peek().pos < i-len) { pq.poll(); } int windowMin = !pq.isEmpty() ? pq.peek().val : 0; if (cumSum[i] - windowMin >= K) { return true; } pq.add(new VI(cumSum[i], i)); } return false; } public static class VI {public int val, pos;} - monotone queue on prefix sum
Return not mid
private long search(int[] nums, int k, long left, long right) {
if (left >= right) {
return left;
}
long res = left;
long guess = left + (right - left) / 2;
int count = 0;
for (int num : nums) {
if (num <= guess) {
count++;
res = Math.max(res, num);
}
}
if (count == k) {
return res;
} else if (count < k) {
return search(nums, k, Math.max(res + 1, guess), right);
} else {
return search(nums, k, left, res);
}
}
public double findMedian(int[] nums) {
int len = 0;
for (int num : nums) {
len++;
}
if (len % 2 == 1) {
return (double) search(nums, len / 2 + 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
} else {
return (double) (search(nums, len / 2, Integer.MIN_VALUE, Integer.MAX_VALUE) +
search(nums, len / 2 + 1, Integer.MIN_VALUE, Integer.MAX_VALUE)) / 2;
}
}