Minimize Maximum of Array — Prefix Average and Binary Search

Problem Statement#

Given a 0-indexed integer array nums, you can repeatedly pick i greater than 0 and decrease nums[i] by 1 while increasing nums[i-1] by 1. Return the minimum possible value of the maximum element.

Constraints:

• 2 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

Input:  nums = [3, 7, 1, 6]
Output: 5

Input:  nums = [10, 1]
Output: 10

Why This Problem Matters#

LeetCode 2439 is a medium binary search interview problem that often appears at Google and Amazon as a warm-up. It tests two skills at once: recognizing the search-on-answer pattern and noticing that a closed-form prefix average exists. Strong candidates produce the O(n) solution; everyone else falls back to O(n log V) binary search, which is also acceptable.

The pattern — minimize the max under a left-to-right transfer constraint — recurs in load balancing, energy redistribution, and stream chunking. It belongs to the FAANG O(log n) family because it always invites the question "can you binary search the answer?"

Walking through both the binary search and the closed form on the whiteboard signals that you understand why the closed form is correct, not just that it works.

The Core Insight#

For any candidate maximum v, every prefix sum nums[0..i] must satisfy prefix <= v * (i + 1). Equivalently, v must be at least ceil(prefix_sum / (i + 1)) for every i. The minimum feasible v is therefore the maximum of those prefix averages — that is the closed-form answer.

Binary search on v works the same way: feasible(v) checks each prefix and decides whether the cumulative excess can be pushed left. The binary search collapses to the closed form because the feasibility predicate is monotone.

Visual Dry Run#

Input [3, 7, 1, 6].

Answer: 5.

Solution (Optimal)#

import math
 
class Solution:
    def minimizeArrayValue(self, nums):
        total = 0
        ans = 0
        for i, x in enumerate(nums):
            total += x
            ans = max(ans, math.ceil(total / (i + 1)))
        return ans

var minimizeArrayValue = function(nums) {
    let total = 0n;
    let ans = 0n;
    for (let i = 0; i < nums.length; i++) {
        total += BigInt(nums[i]);
        const cur = (total + BigInt(i)) / BigInt(i + 1);
        if (cur > ans) ans = cur;
    }
    return Number(ans);
};

Time: O(n) — single pass over the array. Space: O(1) — running totals only.

Common Mistakes#

• Forgetting integer overflow when summing up to 10^14 — use BigInt or 64-bit ints.
• Performing floor division and getting an off-by-one on the average.
• Believing values can flow right-to-left and computing suffix averages instead.
• Running the redistribution simulation directly, which is O(n^2).
• Using the binary search version with a wrong upper bound like max(nums) instead of the prefix sum.

Interview Tips#

• Mention both binary search on answer and the closed form. Implement the closed form.
• Use BigInt or long from the start in JavaScript and Java.
• Explicitly note that values can only flow leftward — that constraint defines the prefix bound.

Follow-up Questions#

• What if values could also flow rightward? Now you can equalize completely — answer is ceil(total / n).
• What if we wanted to minimize variance instead of maximum? Different objective, similar prefix logic.
• What changes if nums[i] can be negative? The prefix average still works but watch ceil semantics.
• Solve it with binary search on answer — what is the feasibility predicate? Track running excess.
• 2D version with row transfers? Run per-row prefix average then take the column max.

Key Takeaways#

• LC 2439 has a clean O(n) closed form: max over prefix averages.
• Binary search on the answer also works in O(n log V) with monotone feasibility.
• Values flow only left, which is what enables the prefix bound.
• Use BigInt or 64-bit ints to avoid overflow on 10^9 inputs.
• Apply ceil(total / (i + 1)) not floor division.
• This is a canonical search-on-answer warm-up at FAANG.
• The same prefix-bound idea solves load-balancing chunk problems.