Binary Search To Find An Answer

287. Find the Duplicate Number

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;
}

1011. Capacity To Ship Packages In N Days

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;
}

410. Split Array Largest Sum

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;
}

1231. Divide Chocolate

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;
}

875. Koko Eating Bananas

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;
}

774. Minimize Max Distance to Gas Station

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;
}

274. H-Index

class Solution {
private:
    bool canFit(const vector<int>& citations, int h) {
        int count = 0;
        for (const int& n : citations) {
            if (n >= h) count++;
        }
        return count >= h;
    }

public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canFit(citations, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
};