LeetCode 2439 - Minimize Maximum of Array

LeetCode Problem 2439

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Dynamic Programming, Greedy, Prefix Sum

Solution

Problem Understanding

The problem gives a 0-indexed array nums of non-negative integers and allows a specific operation: choose an index i (where 1 <= i < n) such that nums[i] > 0, then decrease nums[i] by 1 and increase nums[i - 1] by 1. The task is to perform this operation any number of times in order to minimize the maximum value in the array.

Effectively, the operation allows moving "value" leftward in the array, which means higher values later in the array can be spread backward to reduce peaks. The input constraints indicate that n can be up to 100,000 and values up to 10^9, which rules out any brute-force approach that simulates every possible operation because it would be too slow.

The key challenge is to determine the smallest possible maximum after arbitrarily many operations without explicitly simulating every operation. Important edge cases include arrays that are already non-increasing, arrays with very large values at the end, or arrays where all elements are equal.

Approaches

Brute Force

A brute-force approach would repeatedly simulate the allowed operation by scanning from right to left, moving 1 from nums[i] to nums[i-1] whenever possible, until no further reduction in the maximum is possible. This approach is correct in principle because it models the problem exactly, but it is far too slow. For arrays of size 10^5 with values up to 10^9, this could require billions of operations.

Optimal Insight

The key observation is that the operation essentially allows us to balance prefix sums. The maximum value after any sequence of operations is constrained by the average of the prefix sums. Specifically, for the first i elements, the maximum value cannot be smaller than the ceiling of the sum of the first i elements divided by i + 1. This is because the sum of the first i+1 elements cannot be redistributed to have all elements smaller than the average.

Thus, the solution is to compute the maximum of these prefix averages across the array. This approach avoids simulating operations entirely and can be computed in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * max(nums))	O(1)	Simulates every valid operation; too slow for large inputs
Optimal	O(n)	O(1)	Uses prefix sum and ceiling division to determine the minimal maximum

Algorithm Walkthrough

1. Initialize prefix_sum to 0 and result to 0. prefix_sum will accumulate the sum of elements from index 0 to the current index. result will track the maximum prefix average seen so far.
2. Iterate through each element nums[i] in the array.
3. Add nums[i] to prefix_sum.
4. Compute the minimum possible maximum for the current prefix as ceil(prefix_sum / (i + 1)). In integer arithmetic, this is (prefix_sum + i) // (i + 1).
5. Update result to be the maximum of the current result and this value.
6. After processing all elements, result will hold the minimum possible maximum value for the entire array.

Why it works: Any number moved leftward contributes to lowering future peaks, but the prefix sum ensures no prefix can be reduced below its average without violating the total sum. By taking the maximum prefix average, we guarantee that all elements can be redistributed to not exceed this value.

Python Solution

from typing import List

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        prefix_sum = 0
        result = 0
        for i, num in enumerate(nums):
            prefix_sum += num
            result = max(result, (prefix_sum + i) // (i + 1))
        return result

In this implementation, we iterate through each number, updating the prefix sum and computing the ceiling of the prefix average using integer division. The final result is the smallest maximum achievable.

Go Solution

func minimizeArrayValue(nums []int) int {
    prefixSum := 0
    result := 0
    for i, num := range nums {
        prefixSum += num
        avg := (prefixSum + i) / (i + 1)
        if avg > result {
            result = avg
        }
    }
    return result
}

In Go, we use similar integer arithmetic. The only difference is explicit variable typing. No special handling for large numbers is needed because Go int can handle sums up to 10^14 safely in this problem context.

Worked Examples

Example 1: nums = [3,7,1,6]

Index	prefix_sum	ceil(prefix_sum/(i+1))	result
0	3	3	3
1	10	5	5
2	11	4	5
3	17	5	5

Output: 5

Example 2: nums = [10,1]

Index	prefix_sum	ceil(prefix_sum/(i+1))	result
0	10	10	10
1	11	6	10

Output: 10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array to compute prefix sums and maximum averages
Space	O(1)	Only a few integer variables are used

The linear time complexity is optimal because each element must be inspected. Constant space makes this efficient for large arrays.

Test Cases

# Provided examples
assert Solution().minimizeArrayValue([3,7,1,6]) == 5  # normal redistribution
assert Solution().minimizeArrayValue([10,1]) == 10    # optimal to leave as is

# Edge cases
assert Solution().minimizeArrayValue([0,0,0]) == 0    # all zeros
assert Solution().minimizeArrayValue([1,2,3,4,5]) == 3  # increasing sequence
assert Solution().minimizeArrayValue([5,4,3,2,1]) == 5  # decreasing sequence
assert Solution().minimizeArrayValue([0,1000000000]) == 1000000000  # large number at end
assert Solution().minimizeArrayValue([1]*100000) == 1  # all same numbers, large array

Test	Why
[3,7,1,6]	Typical case with redistribution
[10,1]	Maximum at start; best to leave as is
[0,0,0]	All zeros edge case
[1,2,3,4,5]	Increasing sequence, requires redistribution
[5,4,3,2,1]	Decreasing sequence, maximum at start
[0,1000000000]	Large number at end tests integer handling
[1]*100000	Large input with uniform values

Edge Cases

1. All zeros: Arrays like [0,0,0] could be mishandled if code assumes positive numbers exist. The solution handles this correctly because prefix sums remain zero and the result is zero.
2. Large values at the end: An array like [0,1000000000] tests integer overflow and proper handling of redistribution. The algorithm computes the ceiling of prefix averages and safely returns the large number without overflow.
3. Increasing sequence: Arrays like [1,2,3,4,5] require moving values leftward to minimize the maximum. A naive approach might incorrectly assume only the last value matters. The prefix sum method ensures the correct minimal maximum is computed by considering averages of all prefixes.