2439

2439. Minimize Maximum of Array (Medium)

You are given a 0-indexed array nums comprising of n non-negative integers.

In one operation, you must:

• Choose an integer i such that 1 <= i < n and nums[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.length
• 2 <= n <= 105
• 0 <= nums[i] <= 109

Companies: Oracle, Paytm

Related Topics:
Array, Binary Search, Dynamic Programming, Greedy, Prefix Sum

Similar Questions:

• Maximum Candies Allocated to K Children (Medium)
• Minimum Speed to Arrive on Time (Medium)
• Minimum Time to Complete Trips (Medium)

Solution 1. Binary Answer

// OJ: https://leetcode.com/problems/minimize-maximum-of-array
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int minimizeArrayValue(vector<int>& A) {
        int L = 0, R = *max_element(begin(A), end(A));
        auto valid = [&](long long mx) {
            long long d = 0;
            for (long long n : A) {
                n += d;
                if (n > mx) return false;
                d = n - mx;
            }
            return true;
        };
        while (L <= R) {
            int M = (L + R) / 2;
            if (valid(M)) R = M - 1;
            else L = M + 1;
        }
        return L;
    }
};

Solution 2. Prefix Sum + Greedy

Since the value can only flow forward (left), for A[0..i], assume its prefix sum is sum[i], the best we can do is to distribute this sum[i] evenly into these i+1 elements. So, the maximum is ceil(sum[i] / (i+1)).

We compute from left to right, and return the maximum of ceil(sum[i] / (i+1)) as the answer.

// OJ: https://leetcode.com/problems/minimize-maximum-of-array
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minimizeArrayValue(vector<int>& A) {
        long long N = A.size(), ans = 0, sum = 0;
        for (int i = 0; i < N; ++i) {
            sum += A[i];
            ans = max(ans, (sum + i) / (i + 1));
        }
        return ans;
    }
};