Binary Search To Find An Answer
public int findDuplicate(int[] nums) {
int lo = 1, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (findSmall(nums, mid)) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
private boolean findSmall(int[] nums, int target) {
int count = 0;
for (int num : nums) {
if (num <= target) {
count++;
}
}
return count <= target;
}For problems such as 410, 875, 1011, 1231, it is hard to start. It has pre-conditions:
Choose data from an array
Must choose consecutively
Can be determined by "try out"
Asking for a "min" or "max" of the choice
The problem asks if can be divide the array by a number and having the min/max of this range. Search in a range between the max of all numbers and the sum of all numbers. Use a helper function to try all numbers of the range, and find the min/max.
Instead of trying all numbers, we can use binary search to quickly determine the result.
T: O(N*log(range_size)) S: O(1)
public int shipWithinDays(int[] weights, int D) {
int max = Integer.MIN_VALUE;
int sum = 0;
for (int w : weights) {
max = Math.max(max, w);
sum += w;
}
int left = max, right = sum;
while (left < right) {
int mid = left + (right - left) / 2;
if (canDivide(weights, mid, D)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
/*
*Determine if the array can split into D continuous subarrays,
and each subarray sum can fit (<=) capacity
*/
private boolean canDivide(int[] weights, int capacity, int D) {
int sum = 0, count = 1;
for (int w : weights) {
if (sum + w > capacity) {
sum = 0;
if (count++ > D) return false;
}
sum += w;
}
return count <= D;
}public int splitArray(int[] nums, int m) {
int sum = 0, max = Integer.MIN_VALUE;
for (int n : nums) {
sum += n;
max = Math.max(max, n);
}
int lo = max, hi = sum;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canDivide(nums, mid, m)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
/*
*Determine if the array can split into m continuous subarrays,
and each subarray sum is smaller than sum val
*/
private boolean canDivide(int[] nums, int val, int m) {
int sum = 0, count = 1;
for (int n : nums) {
if (sum + n > val) {
count++;
sum = 0;
if (count > m) {
return false;
}
}
sum += n;
}
return true;
}Divide the array into K continuous subarrays, maximize the min share of this array
public int maximizeSweetness(int[] sweetness, int K) {
int sum = 0, min = sweetness[0];
for (int n : sweetness) {
sum += n;
min = Math.min(min, n);
}
int L = min, R = sum;
while (L < R) {
int mid = L + (R - L + 1) / 2;
if (canDivide(sweetness, mid, K)) {
L = mid;
} else {
R = mid - 1;
}
}
return L;
}
private boolean canDivide(int[] sweet, int t, int K) {
int groupcount = 0, sum = 0;
for (int n : sweet) {
sum += n;
if (sum >= t) {
groupcount++;
sum = 0;
}
}
return groupcount > K;
}public int minEatingSpeed(int[] piles, int H) {
int right = 0;
for (int pile : piles) {
right = Math.max(right, pile);
}
int left = 0;
while (left < right) {
int mid = left + (right - left) / 2;
if (canEatAll(piles, H, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canEatAll(int[] piles, int h, int k) {
int hours = 0;
for (int p : piles) {
hours += Math.ceil(1.0 * p / k);
}
return hours <= h;
}public double minmaxGasDist(int[] stations, int k) {
double left = 0, right = 1e8;
while (right - left > 1e-6) {
double mid = (left + right) / 2.0;
if (isValid(stations, k, mid)) {
right = mid;
} else {
left = mid;
}
}
return left;
}
private boolean isValid(int[] stations, int k, double d) {
int used = 0;
for (int i = 0; i < stations.length - 1; i++) {
used += (int) ((stations[i + 1] - stations[i]) / d);
}
return used <= k;
}Find the Smallest Divisor Given a Threshold
Divide Chocolate
424. Longest Repeating Character Replacement
1802. Maximum Value at a Given Index in a Bounded Array
public int maxValue(int n, int index, int maxSum) {
int left = 1, right = maxSum;
while (left < right) {
int mid = (left + right + 1) / 2;
if (getSum(index, mid, n) <= maxSum) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private long getSum(int index, int value, int n) {
long count = 0;
// On index's left:
// If value > index, there are index + 1 numbers in the arithmetic sequence:
// [value - index, ..., value - 1, value].
// Otherwise, there are value numbers in the arithmetic sequence:
// [1, 2, ..., value - 1, value], plus a sequence of length (index - value + 1) of 1s.
if (value > index) {
count += (long)(value + value - index) * (index + 1) / 2;
} else {
count += (long)(value + 1) * value / 2 + index - value + 1;
};
// On index's right:
// If value >= n - index, there are n - index numbers in the arithmetic sequence:
// [value, value - 1, ..., value - n + 1 + index].
// Otherwise, there are value numbers in the arithmetic sequence:
// [value, value - 1, ..., 1], plus a sequence of length (n - index - value) of 1s.
if (value >= n - index) {
count += (long)(value + value - n + 1 + index) * (n - index) / 2;
} else {
count += (long)(value + 1) * value / 2 + n - index - value;
}
return count - value;
}2616. Minimize the Maximum Difference of Pairs
public int minimizeMax(int[] nums, int p) {
Arrays.sort(nums);
int n = nums.length;
int left = 0, right = nums[n - 1] - nums[0];
while (left < right) {
int mid = left + (right - left) / 2;
if (countValidPairs(nums, mid) >= p) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private int countValidPairs(int[] nums, int threshold) {
int i = 0, count = 0;
while (i < nums.length - 1) {
if (nums[i + 1] - nums[i] <= threshold) {
count++;
i += 2; // skip the next one because it forms a pair with current
} else {
i++;
}
}
return count;
}(NOT on LC) Maximum min absolute difference
Problem: Given an integer array nums and an integer d, you can adjust each element of nums by adding any value up to d (including zero). Your goal is to modify the array such that the minimum absolute difference between any two elements in the adjusted array is maximized. Example: Given nums = [6, 0, 3] and d = 2, one possible adjusted array is [8, 0, 4]. The minimum absolute difference among these elements is 4 (the minimum of |8−4|, |4−0|, and |8−0|). Therefore, the maximum achievable minimum difference is 4. Given nums = [1, 5, 9, 14] and d = 3, you can adjust each element by adding any value from 0 up to 3. One possible adjusted array is [4, 5, 9, 14]. The pairwise absolute differences are: |4 - 5| = 1 |5 - 9| = 4 |9 - 14| = 5 and others like |4 - 9| = 5, |5 - 14| = 9, |4 - 14| = 10 The minimum difference here is 1. But adjusting to [1, 5, 12, 14] gives differences: |1 - 5| = 4 |5 - 12| = 7 |12 - 14| = 2 others: |1 - 12| = 11, |1 - 14| = 13, |5 - 14| = 9
The minimum difference is now 2, which is larger than before. Your goal is to find such adjustments that maximize this minimum absolute difference.
public int maximizeMinDifference(int[] nums, int d) {
Arrays.sort(nums);
int n = nums.length;
int low = 0;
int high = nums[n - 1] + d - nums[0]; // max possible difference
while (low <= high) {
int mid = low + (high - low) / 2;
if (canAdjust(nums, d, mid)) {
low = mid + 1; // try larger minimum difference
} else {
high = mid - 1; // try smaller
}
}
return high;
}
private boolean canAdjust(int[] nums, int d, int minDiff) {
// Adjust first element minimally
long prev = nums[0];
for (int i = 1; i < nums.length; i++) {
// The minimum value to maintain minDiff from prev
long target = prev + minDiff;
// The adjusted value must be in [nums[i], nums[i] + d]
if (target <= nums[i] + d) {
// Assign the max between target and nums[i]
prev = Math.max(target, nums[i]);
} else {
// Cannot maintain minDiff
return false;
}
}
return true;
}
Last updated
Was this helpful?