NeetCode #786LC-2439MediumGreedy
← Back to All Problems#786 · #2439 · Minimize Maximum of Array(最小化数组中的最大值)
📌 Problem Statement & Constraints
Given an array
nums of n non-negative integers, an operation chooses an index i in [1, n-1], decreases nums[i] by 1 and increases nums[i-1] by 1. Return the minimum possible value of the maximum element. Constraints: 2 <= n <= 10^5, 0 <= nums[i] <= 10^9.💡 Core Algorithmic Approaches
- Mass can only move left, so the value at any position is bounded by the average of the prefix ending there.
- Specifically, the maximum element cannot be smaller than
ceil(prefix_sum[i] / (i + 1))for every prefixi. - This lower bound is achievable: push excess rightward mass left until every prefix average is respected.
- So the answer is the maximum prefix-average ceiling.
💻 Benchmark Python3 Implementation
class Solution:
def minimizeArrayValue(self, nums: List[int]) -> int:
res = 0
prefix = 0
for i, x in enumerate(nums):
prefix += x
# ceiling of the prefix average
res = max(res, -(-prefix // (i + 1)))
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass over the prefixes.
💾 Space Complexity
O(1): two scalars.
⚠️ Interview Pitfalls & Follow-ups
- Using floor division: the bound is the ceiling, since values are integers; floor would understate the answer.
- Thinking mass can move right: the operation only shifts mass one step left.
- Returning
max(nums): the maximum can always be reduced unless the array is already flat enough. - Forgetting the first prefix:
ceil(nums[0] / 1) = nums[0]is a valid lower bound.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.