How do you solve Minimize Maximum of Array on LeetCode?

Minimize Maximum of Array (LeetCode #2439) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log(max(nums))) time complexity and O(1) space complexity. Key insight: Redistributing values can help minimize the maximum value.

What is the brute force solution for Minimize Maximum of Array?

The brute force approach for Minimize Maximum of Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves simulating all possible operations to redistribute the values in the array. By repeatedly adjusting the values, we can find the maximum value in the array after each operation and track the minimum of these maximums. The optimal Optimal Solution approach improves this to O(n log(max(nums))).

What are the interview tips for Minimize Maximum of Array?

Explain your thought process clearly; it shows your understanding. Don't rush into coding; take time to plan your approach. Practice similar problems to recognize patterns.

What are common mistakes when solving Minimize Maximum of Array?

Not considering edge cases where elements are already at their minimum. Overlooking the need to check if a redistribution is possible within the current bounds.

#2439

Minimize Maximum of Array

Medium

ArrayBinary SearchDynamic ProgrammingGreedyPrefix SumBinary SearchGreedy

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log(max(nums)))
Space	O(1)	O(1)

💡

Intuition

Time O(n log(max(nums)))Space O(1)

The optimal approach uses binary search to efficiently find the minimum possible maximum value. We leverage the fact that if we can achieve a certain maximum value, we can also achieve any value greater than that, allowing us to narrow down our search space.

⚙️

Algorithm

5 steps

1Step 1: Set low to 0 and high to the maximum value in nums.
2Step 2: While low is less than high, calculate mid as the average of low and high.
3Step 3: Check if it is possible to make all elements in nums less than or equal to mid by redistributing values.
4Step 4: If possible, update high to mid; otherwise, update low to mid + 1.
5Step 5: Return low as the minimum possible maximum value.

solution.py21 lines

1# Full working Python code
2
3def canAchieveMax(nums, target):
4    total = 0
5    for num in nums:
6        if num > target:
7            total += num - target
8    return total
9
10
11def minimizeArray(nums):
12    low, high = 0, max(nums)
13    while low < high:
14        mid = (low + high) // 2
15        if canAchieveMax(nums, mid) <= mid:
16            high = mid
17        else:
18            low = mid + 1
19    return low
20
21print(minimizeArray([3,7,1,6]))

ℹ

Complexity note: The time complexity is O(n log(max(nums))) because we perform a binary search over the possible maximum values (log(max(nums))) and for each mid value, we check the array in O(n).

1Redistributing values can help minimize the maximum value.
2Binary search is effective for finding optimal thresholds in sorted or range-based problems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.