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.
This approach uses binary search to find the minimum possible value of the maximum integer in the array after any number of operations. The idea is to treat the problem as a decision problem: given a target max value, can the array be adjusted to ensure no element exceeds this target?
Initialize the binary search over the range from 0 to the maximum element in the array. For each midpoint, simulate transferring values leftward to see if this is achievable. Adjust the search range based on whether the configuration was possible.
The function minimizeArrayValue uses a helper function canAchieveMax to determine if a given maximum value is achievable. carry keeps track of surplus values that need to be balanced. The binary search adjusts the possible minimum maximum value based on whether the current midpoint is achievable.
Time complexity: O(n log(max(nums))) because we are doing a binary search over a range that can be as large as the maximum element, and for each binary search step, we traverse the list.
Space complexity: O(1) because we only use constant extra space.
This solution uses a greedy approach aided by prefix sums. The goal is to ensure the prefix sum can act as an invariant that will help us decide when rebalancing is possible.
Calculate prefix sums and determine the potential maximum value at each step. Essentially, this max value is influenced by the average value achievable so far.
This Python solution calculates the prefix sum as it iterates through the array. It uses the current index to calculate the potential max value as an adjusted average. This helps keep the balance by checking if previous operations suffice to keep the current potential max.
Time complexity: O(n) as we traverse the array once to compute the prefix sum.
Space complexity: O(1) since only a constant amount of space is used to store the prefix sum and max value.
To minimize the maximum value of the array, it is intuitive to use binary search. We binary search for the maximum value mx of the array, and find the smallest mx that satisfies the problem requirements.
The time complexity is O(n times log M), where n is the length of the array, and M is the maximum value in the array.
| Approach | Complexity |
|---|---|
| Binary Search Solution | Time complexity: Space complexity: |
| Prefix Sum-based Greedy Solution | Time complexity: Space complexity: |
| Binary Search | — |
| 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. |
Minimize Maximum of Array - Leetcode 2439 - Python • NeetCodeIO • 31,427 views views
Watch 9 more video solutions →Practice Minimize Maximum of Array with our built-in code editor and test cases.
Practice on FleetCode