Minimize Maximum of Array solution and explanation
9 more videos on this problem
Minimize Maximum of Array - Leetcode 2439 - PythonNeetCodeIO · 9:50 · 32K views
Minimize Maximum of Array - (META) | Leetcode-2439 | Explanation ➕ Live Coding 🧑🏻💻👩🏻💻codestorywithMIK · 33:24 · 15K views
Minimize Maximum of Array || Binary Search || Arrays || C++/Java/PythonAryan Mittal · 26:19 · 10K views
Leetcode 2439. Minimize Maximum of Array | Leetcode biweekly contest 89Codewa · 8:39 · 2K views
2439. Minimize Maximum of Array | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 25:43 · 2K views
2439. Minimize Maximum of Array (Leetcode Medium)Programming Live with Larry · 8:32 · 2K views
Daily Leetcode #1100: Apr 05, 2023 - 2439. Minimize Maximum of ArrayProgramming Live with Larry · 26:22 · 510 views
Leetcode 2439: Minimize Maximum of ArrayAlgorithms Casts · 22:53 · 452 views
2439. Minimize Maximum of Array Leetcode Problem | Detailed ExplanationThe Stylish Coder · 12:27 · 211 views
Leetcode 2439 Minimize Maximum of ArrayMaxMing · 4:13 · 136 views
The problem
You are given a 0-indexed array nums comprising of n non-negative integers.
In one operation, you must:
- Choose an integer
isuch that1 <= i < nandnums[i] > 0. - Decrease
nums[i]by 1. - Increase
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] <= 109
Approach overview
Problem 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 1: Binary Search Solution
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.
def minimizeArrayValue(nums):
def canAchieveMax(val):
carry = 0
for num in nums:
carry += num - val
if carry < 0:
carry = 0
return carry <= 0
left, right = 0, max(nums)
while left < right:
mid = (left + right) // 2
if canAchieveMax(mid):
right = mid
else:
left = mid + 1
return leftpublic class Solution {
public int minimizeArrayValue(int[] nums) {
int left = 0, right = 0;
for (int num : nums) right = Math.max(right, num);
while (left < right) {
int mid = (left + right) / 2;
if (canAchieveMax(nums, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canAchieveMax(int[] nums, int val) {
long carry = 0;
for (int num : nums) {
carry += num - val;
if (carry < 0) carry = 0;
}
return carry <= 0;
}
}#include <vector>
#include <algorithm>
#include <climits>
class Solution {
public:
int minimizeArrayValue(const std::vector<int>& nums) {
int left = 0;
int right = *std::max_element(nums.begin(), nums.end());
while (left < right) {
int mid = left + (right - left) / 2;
if (canAchieveMax(nums, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private:
bool canAchieveMax(const std::vector<int>& nums, int val) {
long long carry = 0;
for (int num : nums) {
carry += num - val;
if (carry < 0) carry = 0;
}
return carry <= 0;
}
};function minimizeArrayValue(nums) {
const canAchieveMax = (val) => {
let carry = 0;
for (let num of nums) {
carry += num - val;
if (carry < 0) carry = 0;
}
return carry <= 0;
};
let left = 0, right = Math.max(...nums);
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (canAchieveMax(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}#include <stdbool.h>
#include <stdio.h>
bool canAchieveMax(int* nums, int numsSize, int val) {
long carry = 0;
for (int i = 0; i < numsSize; i++) {
carry += nums[i] - val;
if (carry < 0) carry = 0;
}
return carry <= 0;
}
int minimizeArrayValue(int* nums, int numsSize) {
int left = 0, right = 0;
for (int i = 0; i < numsSize; i++)
if (nums[i] > right) right = nums[i];
while (left < right) {
int mid = left + (right - left) / 2;
if (canAchieveMax(nums, numsSize, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}using System;
public class Solution {
public int MinimizeArrayValue(int[] nums) {
int left = 0, right = nums.Max();
while (left < right) {
int mid = left + (right - left) / 2;
if (CanAchieveMax(nums, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private bool CanAchieveMax(int[] nums, int val) {
long carry = 0;
foreach (var num in nums) {
carry += num - val;
if (carry < 0) carry = 0;
}
return carry <= 0;
}
}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.
Approach 2: Prefix Sum-based Greedy Solution
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.
def minimizeArrayValue(nums):
prefix_sum, max_value = 0, 0
for i in range(len(nums)):
prefix_sum += nums[i]
max_value = max(max_value, (prefix_sum + i) // (i + 1))
return max_valuepublic class Solution {
public int minimizeArrayValue(int[] nums) {
long prefixSum = 0;
int maxValue = 0;
for (int i = 0; i < nums.length; i++) {
prefixSum += nums[i];
maxValue = (int) Math.max(maxValue, (prefixSum + i) / (i + 1));
}
return maxValue;
}
}#include <vector>
#include <algorithm>
class Solution {
public:
int minimizeArrayValue(std::vector<int>& nums) {
long long prefixSum = 0;
int maxValue = 0;
for (int i = 0; i < nums.size(); i++) {
prefixSum += nums[i];
maxValue = std::max(maxValue, static_cast<int>((prefixSum + i) / (i + 1)));
}
return maxValue;
}
};function minimizeArrayValue(nums) {
let prefixSum = 0;
let maxValue = 0;
for (let i = 0; i < nums.length; i++) {
prefixSum += nums[i];
maxValue = Math.max(maxValue, Math.floor((prefixSum + i) / (i + 1)));
}
return maxValue;
}#include <stdio.h>
int minimizeArrayValue(int* nums, int numsSize) {
long prefixSum = 0;
int maxValue = 0;
for (int i = 0; i < numsSize; i++) {
prefixSum += nums[i];
if (maxValue < (prefixSum + i) / (i + 1))
maxValue = (prefixSum + i) / (i + 1);
}
return maxValue;
}public class Solution {
public int MinimizeArrayValue(int[] nums) {
long prefixSum = 0;
int maxValue = 0;
for (int i = 0; i < nums.Length; i++) {
prefixSum += nums[i];
maxValue = Math.Max(maxValue, (int)((prefixSum + i) / (i + 1)));
}
return maxValue;
}
}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.
Approach 3: Binary Search
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.
func minimizeArrayValue(nums []int) int {
check := func(mx int) bool {
d := 0
for i := len(nums) - 1; i > 0; i-- {
d = max(0, nums[i]+d-mx)
}
return nums[0]+d <= mx
}
left, right := 0, slices.Max(nums)
for left < right {
mid := (left + right) >> 1
if check(mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search Solution | Time complexity: Space complexity: |
| Prefix Sum-based Greedy Solution | Time complexity: Space complexity: |
| Binary Search | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimize Maximum of Array easy or hard?
Minimize Maximum of Array is classified as Medium difficulty on LeetCode. The implementation is short, but recognizing that the answer depends on prefix averages requires a key greedy insight.
How to solve Minimize Maximum of Array in O(n)?
Compute a running prefix sum while iterating through the array. For each index i, calculate the ceiling average ceil(prefixSum / (i + 1)). Track the maximum of these values across all prefixes. That value represents the smallest possible maximum after redistributing elements left.
What is the best approach for Minimize Maximum of Array?
The prefix sum greedy approach is the most efficient. Track the running prefix sum and compute ceil(prefixSum / prefixLength) at each index. The maximum of these values is the minimized maximum element. This runs in O(n) time and O(1) space.
Is Minimize Maximum of Array asked at Google/Amazon/Meta?
Problems involving greedy redistribution and prefix constraints appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this question test understanding of prefix sums, greedy reasoning, and binary search on answers.
What data structure is used in Minimize Maximum of Array?
The optimal solution mainly relies on arrays and prefix sums rather than complex data structures. The algorithm maintains a running sum and performs simple arithmetic operations to compute prefix averages.
What is the time complexity of Minimize Maximum of Array?
The optimal greedy solution runs in O(n) time because the array is scanned once while maintaining a prefix sum. Space complexity is O(1). A binary search alternative exists with O(n log m) time where m is the maximum value in the array.
Minimize Maximum of Array Python or Java solution approach?
Most Python and Java implementations follow the same greedy pattern: iterate through the array, maintain a running prefix sum, and compute the ceiling of the average for each prefix. The result is the maximum of those prefix averages, achieved in linear time.