2439. Minimize Maximum of Array - Explanation

1. Binary Search

Intuition

The operation allows us to move value from a position to its left neighbor. This means we can redistribute values leftward but never rightward. The key observation is: for any target maximum value m, we can achieve it if and only if the prefix sum up to each index i does not exceed m * (i + 1). This is because we can spread the total sum of the first i+1 elements evenly among those positions.

Since the answer lies between 0 and the maximum element, we can binary search for the smallest valid maximum. For each candidate, we check if the prefix sum constraint holds for all positions.

Algorithm

Binary search on the answer between 0 and max(nums).
For each candidate maximum mid, check validity:
- Iterate through the array maintaining a running prefix_sum.
- If at any index i, the prefix_sum exceeds mid * (i + 1), the candidate is too small.
If valid, try a smaller maximum. If invalid, try a larger one.
Return the smallest valid maximum.

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        def isValid(maxVal):
            prefix_sum = 0
            for i in range(len(nums)):
                prefix_sum += nums[i]
                if prefix_sum > maxVal * (i + 1):
                    return False
            return True

        left, right = 0, max(nums)
        while left < right:
            mid = left + (right - left) // 2
            if isValid(mid):
                right = mid
            else:
                left = mid + 1

        return left

Time & Space Complexity

Time complexity: $O(n \log m)$
Space complexity: $O(1)$ extra space.

Where $n$ is the size of the array $nums$ and $m$ is the maximum value in the array.

2. Prefix Sum + Greedy

Intuition

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.

Algorithm

Initialize res and total with the first element (the first element cannot be reduced).
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.
Return res.

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

Time & Space Complexity

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

Common Pitfalls

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.