Minimize Maximum of Array

Leetcode Daily Challenge (5th April, 2023)

5 April, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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.

Link: https://leetcode.com/problems/minimize-maximum-of-array/description/

Problem Explanation with examples:-

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

Intuition:-

Binary search can be used to find the minimum value of the array.
We can use the check if mid can be achieved by the given set of operations.
To check if mid can be achieved, we can use the following algorithm:
For each element in the array, if the element is less than or equal to mid, then we need to add (mid - element) to achieve mid and for that the next element should be greater than mid by (mid - element). If it is not greater than mid by (mid - element), then we cannot achieve mid and we return False.

Solution:-

Initialize left to 0 and right to the maximum element in the array.
While left is less than right, do the following:
Initialize mid to (left + right)//2.
If check(mid) returns True, then we can achieve mid. So, we set right to mid.
Else, we set left to mid + 1.
In check, we initialize a variable have to 0.
Iterate over the array and check if the element is less than or equal to mid. If it is, then we add (mid - element) to have. If it is not, then we check if have is less than (element - mid). If it is, then we cannot achieve mid and we return False. Else, we subtract (element - mid) from have.
If we have not returned False, then we can achieve mid and we return True.
Return left at the end.

Code:-

JAVA Solution

public class Solution {
    public int minimizeArrayValue(int[] nums) {
        int left = 0;
        int right = Arrays.stream(nums).max().getAsInt();
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (check(mid, nums)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    private boolean check(int k, int[] nums) {
        int have = 0;
        for (int i : nums) {
            if (i <= k) {
                have += (k - i);
            } else {
                if (have < (i - k)) {
                    return false;
                } else {
                    have -= (i - k);
                }
            }
        }
        
        return true;
    }
}

Python Solution

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        left = 0
        right = max(nums)

        def check(k):
            have = 0
            for i in nums:
                if i <= k:
                    have += (k - i)
                else:
                    if have < (i - k):
                        return False
                    else:
                        have -= (i - k)

            return True

        while left < right:
            mid = (left + right)//2
            if check(mid):
                right = mid
            else:
                left = mid+1

        return left

Complexity Analysis:-

TIME:-

The time complexity is O(Nlog(Maximum value of nums)), where N is the length of the input nums array. The binary search algorithm takes log(Maximum value of nums) time complexity and each check of the midpoint in the binary search requires a linear scan of the nums array, which takes O(N) time complexity. Therefore, the overall time complexity is O(Nlog(Maximum value of nums)).

SPACE:-

The space complexity is O(1). The algorithm uses a constant amount of extra space to store the left and right pointers and the midpoint in the binary search. The check() function only uses a constant amount of extra space to store the "have" variable. Therefore, the overall space complexity is O(1).

References:-

Binary Search