Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4

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.

Solution

Method 1 - Binary Search

To solve this problem, we need to minimize the maximum value in the array nums after performing as many operations as needed. The key insight is that we can use a binary search approach to find the minimum possible value for the maximum element.

Here is the approach:

  1. Binary Search:
    • Use binary search on the possible values of the maximum element, from 0 to the maximum value in nums.
  2. Feasibility Check:
    • For each candidate maximum value in the binary search, check if it is possible to reduce the array such that no element exceeds this value.
    • Utilize a greedy approach to transfer values from right to left, ensuring the elements do not exceed the candidate maximum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Solution {
    public int minimizeArrayValue(int[] nums) {
        int left = 0, right = 0;
        for (int num : nums) {
            right = Math.max(right, num);
        }

        while (left < right) {
            int mid = (left + right) / 2;
            if (canReduceToMax(nums, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean canReduceToMax(int[] nums, int target) {
        long excess = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > target) {
                excess += nums[i] - target;
            } else {
                excess -= Math.min(excess, target - nums[i]);
            }
        }
        return excess == 0;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        def canReduceToMax(nums, target):
            excess = 0
            for i in range(len(nums) - 1, 0, -1):
                if nums[i] > target:
                    excess += nums[i] - target
                else:
                    excess -= min(excess, target - nums[i])
            return excess == 0

        left, right = 0, max(nums)
        while left < right:
            mid = (left + right) // 2
            if canReduceToMax(nums, mid):
                right = mid
            else:
                left = mid + 1

        return left

Complexity

  • ⏰ Time complexity: O(n * log(max(nums))
    • The binary search runs in O(log(max(nums))), where max(nums) is the highest value in nums.
    • The canReduceToMax function performs a single pass through the array, making its complexity O(n).
  • 🧺 Space complexity: O(1)