Minimize Maximum of Array — Solution in Python, Java & C++
Minimize Maximum of Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimize Maximum of Array is a medium coding problem on arrays, greedy and binary search, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy, Binary Search, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
nums is a 0-indexed array of non-negative integers. In one operation you pick an index i with 1 <= i < n and nums[i] > 0, decrease nums[i] by 1 and increase nums[i - 1] by 1 — one unit moves one step to the left.
You may perform any number of operations. Return the minimum possible value of the largest element of nums.
Example 1
Input: nums = [2,7,1,6]
Output: 5
Explanation: Move 2 units from index 1 to index 0 and 1 unit from index 3 to index 2: `[4,5,2,5]`. The first two elements total 9, so one of them is always at least 5.
Example 2
Input: nums = [9,3]
Output: 9
Explanation: Units only move left, so `nums[0]` can never shrink.
Example 3
Input: nums = [0,0,10]
Output: 4
Explanation: For example `[4,3,3]`.
Constraints
n == nums.length2 <= n <= 10^50 <= nums[i] <= 10^9
Hints for Minimize Maximum of Array
Hint 1
Units can only move left, so the first
i + 1elements can never lose their total.Hint 2
That makes
ceil(prefix_sum(i) / (i + 1))a lower bound on the answer for everyi.Hint 3
The largest of those lower bounds is achievable. Compute it in one pass with 64-bit prefix sums (or binary search the answer with a right-to-left carry check).
How to solve Minimize Maximum of Array
Moving units leftwards never changes the total of a prefix except by adding to it, so each prefix's average (rounded up) is a floor on the maximum. The maximum of those floors is also achievable, which turns the problem into one prefix-sum pass.
Approach
- Sweep
ifrom 0 ton - 1, keeping the running sumprefixin 64 bits. - Compute
ceil(prefix / (i + 1))as(prefix + i) / (i + 1)with integer division. - Return the largest such value.
Why it works
Lower bound: no operation moves units out of the prefix nums[0..i] (they only move left), so its total stays at least prefix_i, and i + 1 numbers with that total have a maximum of at least ceil(prefix_i / (i + 1)). Achievability: let A be the largest bound. Scanning from the right, any element above A can push its excess one step left; the excess carried into position i never makes the prefix ending there exceed A·(i + 1), so the carry finally absorbed by nums[0] leaves it at most A — every element ends at most A.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Prefix sums reach
10^14; keep them in 64-bit integers. - Use integer ceiling division — floating-point division can round across an integer boundary.
- Units cannot move right, so a large
nums[0]is a hard floor on the answer.
Reference solution
Python
from typing import List
def minimizeArrayValue(nums: List[int]) -> int:
prefix = 0
best = 0
for i, x in enumerate(nums):
prefix += x
best = max(best, (prefix + i) // (i + 1))
return bestJava
public static int minimizeArrayValue(int[] nums) {
long prefix = 0, best = 0;
for (int i = 0; i < nums.length; i++) {
prefix += nums[i];
best = Math.max(best, (prefix + i) / (i + 1));
}
return (int) best;
}C++
int minimizeArrayValue(vector<int>& nums) {
long long prefix = 0, best = 0;
for (int i = 0; i < (int)nums.size(); i++) {
prefix += nums[i];
best = max(best, (prefix + i) / (i + 1));
}
return (int)best;
}JavaScript
var minimizeArrayValue = function(nums) {
var prefix = 0, best = 0;
for (var i = 0; i < nums.length; i++) {
prefix += nums[i];
var need = Math.floor((prefix + i) / (i + 1));
if (need > best) best = need;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms