Minimize the Maximum of Subarrays After Splits — BS on Answer

Problem 334 · Minimize the Maximum of Arrays After Operations

Difficulty: Medium · Pattern: BS on Answer + Greedy check

After at most k operations on adjacent pairs, minimize the maximum element.

Solutions

# Python — Binary search on answer
def minimizeArrayValue(nums):
    # Min possible max = ceil(prefix_sum / (i+1)) for each prefix
    # The answer is max of all these prefix averages
    import math
    total = 0; ans = 0
    for i, x in enumerate(nums):
        total += x
        ans = max(ans, math.ceil(total / (i+1)))
    return ans

// Java
public int minimizeArrayValue(int[] nums) {
    long total=0, ans=0;
    for (int i=0;i<nums.length;i++) {
        total+=nums[i];
        ans=Math.max(ans,(total+i)/(i+1));
    }
    return (int)ans;
}

Complexity

Time: O(n)
Space: O(1)

Key Insight

The optimal answer is the max over all prefix averages (ceiling), because we can equalize from left to right.