⚡Flashcard Drill➔
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

  1. Mass can only move left, so the value at any position is bounded by the average of the prefix ending there.
  2. Specifically, the maximum element cannot be smaller than ceil(prefix_sum[i] / (i + 1)) for every prefix i.
  3. This lower bound is achievable: push excess rightward mass left until every prefix average is respected.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems