Minimize Maximum of Array

How it works

Building on the prefix sum insight, we can solve this directly without binary search. At each position i, the minimum possible maximum considering elements 0 to i is the ceiling of prefixSum / (i + 1). This represents the best we can do by spreading the total sum evenly across those positions.

The overall answer is the maximum of these values across all prefixes. We cannot do better than this because each prefix constrains how low the maximum can go, and the tightest constraint determines the answer.

Steps

1. Initialize res and total with the first element (the first element cannot be reduced).
2. For each subsequent index i:
   • Add nums[i] to the running total.
   • Compute the ceiling of total / (i + 1).
   • Update res to be the maximum of itself and this ceiling.
3. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Forgetting That the First Element Cannot Be Reduced

The operation only moves value from position i to position i-1. This means you can never reduce the first element nums[0]} since there is no position to its left. Many solutions incorrectly assume you can redistribute values in both directions. The first element sets a lower bound on the answer since it can only increase, never decrease.

Integer Overflow in Prefix Sum Calculations

When computing prefix sums and comparing against maxVal * (i + 1), the multiplication can overflow if using 32-bit integers. For arrays with large values (up to 10^9) and indices up to 10^5, the product can exceed 2^31. Always use 64-bit integers (long, long long, Int64) for the prefix sum and the multiplication result.

Off-by-One Errors in the Ceiling Division

The greedy solution requires computing the ceiling of prefixSum / (i + 1). A common mistake is using integer division directly, which gives the floor. The ceiling can be computed as (prefixSum + i) / (i + 1) or using explicit ceiling functions. Also ensure the divisor is i + 1 (not i) since indices are 0-based but we need the count of elements.

from typing import List
import math

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        res = total = nums[0]

        for i in range(1, len(nums)):
            total += nums[i]
            res = max(res, math.ceil(total / (i + 1)))

        return res

class Solution {
public:
    int minimizeArrayValue(vector<int>& nums) {
        int res = nums[0];
        long long total = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            total += nums[i];
            res = max(res, (int)ceil((double)total / (i + 1)));
        }

        return res;
    }
};