Watch 10 video solutions for Minimize Maximum of Array, a medium level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by NeetCodeIO has 31,427 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed array nums comprising of n non-negative integers.
In one operation, you must:
i such that 1 <= i < n and nums[i] > 0.nums[i] by 1.nums[i - 1] by 1.Return the minimum possible value of the maximum integer of nums after performing any number of operations.
Example 1:
Input: nums = [3,7,1,6] Output: 5 Explanation: One set of optimal operations is as follows: 1. Choose i = 1, and nums becomes [4,6,1,6]. 2. Choose i = 3, and nums becomes [4,6,2,5]. 3. Choose i = 1, and nums becomes [5,5,2,5]. The maximum integer of nums is 5. It can be shown that the maximum number cannot be less than 5. Therefore, we return 5.
Example 2:
Input: nums = [10,1] Output: 10 Explanation: It is optimal to leave nums as is, and since 10 is the maximum value, we return 10.
Constraints:
n == nums.length2 <= n <= 1050 <= nums[i] <= 109Problem Overview: You are given an array nums. In one operation, you can move 1 unit from index i to i-1. After any number of operations, the goal is to minimize the maximum value in the array. Since values can only move left, every prefix effectively shares its total sum across its elements.
Approach 1: Binary Search on the Answer (Time: O(n log m), Space: O(1))
This method searches for the smallest possible maximum value using binary search. The search range is between 0 and the maximum element of the array. For a candidate maximum mid, simulate whether the array can be adjusted so every element is ≤ mid. Traverse from right to left and push excess values leftward (since operations only allow moving to i-1). If the accumulated overflow eventually forces nums[0] to exceed mid, the candidate is invalid. Otherwise it works. This approach is useful when the feasibility condition is monotonic, making binary search a natural fit.
Approach 2: Prefix Sum Greedy (Time: O(n), Space: O(1))
The optimal insight comes from observing that redistribution only moves values left. Consider the prefix [0..i]. After any operations, the total sum of that prefix stays the same, but its values can spread out. The smallest possible maximum value for that prefix is ceil(prefixSum / (i + 1)). Iterate through the array, maintain a running prefix sum, and compute this ceiling average at each index. The final answer is the maximum of these values across all prefixes. This greedy rule works because any prefix that requires a higher average forces the global maximum to be at least that value.
This technique relies heavily on understanding prefix sums and a greedy observation about redistribution. Instead of simulating operations, it directly computes the theoretical lower bound each prefix imposes.
Recommended for interviews: The prefix-sum greedy solution is what most interviewers expect. It runs in O(n) time with constant space and demonstrates strong reasoning about constraints and invariants. The binary search approach still shows solid problem-solving since it frames the problem as a feasibility check, but the greedy prefix average reveals the deeper insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Maximum | O(n log m) | O(1) | Useful when you recognize a monotonic feasibility condition and want a general solution pattern. |
| Prefix Sum Greedy | O(n) | O(1) | Best choice for interviews and production due to linear time and simple logic. |