Binary Search on Answer: Minimizing the Maximum

When a problem asks to "Minimize the maximum value" or "Maximize the minimum value," consider binary searching for the answer itself and using a check(x) function to verify feasibility.

Split Array Largest Sum (LeetCode 410)

Given an array, split it into $m$ non-empty continuous subarrays such that the largest sum among these subarrays is minimized.

public int splitArray(int[] nums, int m) {
    int low = Arrays.stream(nums).max().getAsInt(); // At least the largest single element
    int high = Arrays.stream(nums).sum();            // At most the sum of all elements
    
    while (low < high) {
        int midLimit = low + (high - low) / 2;
        if (canSplit(nums, m, midLimit)) {
            high = midLimit; // Try to lower the maximum subarray sum
        } else {
            low = midLimit + 1; // Limit too small, must increase it
        }
    }
    return low;
}

// check: Can we split 'nums' into <= m groups where no group sum exceeds 'maxSum'?
private boolean canSplit(int[] nums, int m, int maxSum) {
    int splitCount = 1, currentSum = 0;
    for (int n : nums) {
        if (currentSum + n > maxSum) {
            splitCount++;
            currentSum = 0;
        }
        currentSum += n;
    }
    return splitCount <= m;
}

Universal Template for Result Bisection

low = minimum_possible_valid_answer
high = maximum_possible_valid_answer

while (low < high) {
    mid = (low + high) / 2;
    if (canAccomplish(mid)) {
        high = mid; // Try to find an even smaller optimal result
    } else {
        low = mid + 1; // Current value is too small to be valid
    }
}
return low;

Koko Eating Bananas (LeetCode 875)

public int minEatingSpeed(int[] piles, int h) {
    int low = 1, high = Arrays.stream(piles).max().getAsInt();
    while (low < high) {
        int speed = low + (high - low) / 2;
        long hoursNeeded = 0;
        for (int p : piles) {
            // Ceiling division: (p + speed - 1) / speed
            hoursNeeded += (p + speed - 1) / speed;
        }
        if (hoursNeeded <= h) high = speed;
        else low = speed + 1;
    }
    return low;
}

Capacity to Ship Packages (LeetCode 1011)

public int shipWithinDays(int[] weights, int days) {
    int low = 0, high = 0;
    for (int w : weights) { low = Math.max(low, w); high += w; }
    
    while (low < high) {
        int cap = low + (high - low) / 2;
        int daysUsed = 1, currentLoad = 0;
        for (int w : weights) {
            if (currentLoad + w > cap) {
                daysUsed++;
                currentLoad = 0;
            }
            currentLoad += w;
        }
        if (daysUsed <= days) high = cap;
        else low = cap + 1;
    }
    return low;
}

Minimum Number of Days to Make $m$ Bouquets (LeetCode 1482)

public int minDays(int[] bloomDay, int m, int k) {
    if ((long) m * k > bloomDay.length) return -1;
    int low = 1, high = Arrays.stream(bloomDay).max().getAsInt();
    
    while (low < high) {
        int midDay = low + (high - low) / 2;
        if (canMake(bloomDay, m, k, midDay)) high = midDay;
        else low = midDay + 1;
    }
    return low;
}

private boolean canMake(int[] bloomDay, int m, int k, int day) {
    int bouquets = 0, consecutiveFlowers = 0;
    for (int d : bloomDay) {
        if (d <= day) {
            consecutiveFlowers++;
            if (consecutiveFlowers == k) {
                bouquets++;
                consecutiveFlowers = 0;
            }
        } else {
            consecutiveFlowers = 0;
        }
    }
    return bouquets >= m;
}

Comparison Summary Table