2439. Minimize Maximum of Array

MediumGreedyArrayBinary SearchDynamic ProgrammingPrefix Sum

Problem Description

In this problem, you are given an array nums with n non-negative integers. The focus is on the array's integers' transformation through a series of operations to minimize the value of the maximum integer in the array. Each operation includes three steps:

Select an integer i where i is between 1 and n-1 (inclusive), and nums[i] is greater than 0.
Decrease nums[i] by 1.
Increase nums[i - 1] by 1.

The objective is to find out the smallest possible value of the largest number in the array after performing any number of these operations.

Intuition

The intuition behind the solution is to use binary search to find the minimum possible value of the maximum integer in the array after all the operations. Since we are asked for the minimum possible maximum value, we can guess that there is some maximum value that we cannot go below no matter how many operations we perform.

We perform binary search between the lowest possible maximum value, which is 0, and the current maximum value in the array. For each guess (possible maximum value) in the binary search, we check if we can achieve that maximum value after performing the operations. Here's the step-by-step reasoning:

Start with a binary search between 0 and the maximum value present in the array nums.
Calculate the middle value between the current range as our guess for the possible maximum value.
Define a check function that will determine if it is possible to achieve the guessed maximum value with the array.
In the check function, we work backwards from the end of the array towards the beginning (right to left). For each element, we calculate the surplus or deficit compared to our guessed maximum and carry this difference to the previous element.
The conditions that tell us if we can achieve the guessed maximum are:
- If at any point the required decrease is so great we cannot make up the difference with the carried surplus, the check fails.
- If we can carry the difference through to the first element, we then check if the total sum of increases needed for the first element does not exceed our guessed maximum.
If the check function returns true, it means we can achieve the guessed maximum or even lower, so we continue searching towards the lower half of the binary search range.
If the check function returns false, the guessed maximum is too low, and we have to adjust our range towards the higher values.
Repeat this process until the binary search narrows down to the smallest possible maximum integer value that satisfies the condition (the left and right pointers converge).

The solution uses the fact that after all possible optimizations, the array nums will become non-decreasing from the beginning to the end. This is because the maximum possible number in an optimal solution cannot be less than the average of the numbers in the array. Thus, binary search optimizes the process by eliminating the need to test each value sequentially.

Learn more about Greedy, Binary Search, Dynamic Programming and Prefix Sum patterns.

Solution Approach

The solution utilizes a binary search algorithm to narrow down the possible maximum value that can be achieved in the array after performing the operations. Here's an in-depth walkthrough of the algorithm, elaborating on the reference solution provided:

Binary Search Initialization: Define two pointers, left and right, which represent the range within which the final answer could be. Initialize left to 0, assuming the minimum possible value in the array could be 0 after all operations, and initialize right to the maximum value in nums, which is the upper limit of the answer.
Binary Search Loop: While left is less than right, calculate the middle of the current left and right boundary, mid = (left + right) >> 1. (>> 1 is a bitwise operation equivalent to dividing by 2, shifting the bits to the right once.)
Check Function: The check function is defined to test whether a certain maximum value mx can be attained after performing the allowed operations. It works as follows:
- Initialize a d variable to 0, which represents the cumulative difference needed to reach the guessed maximum mx from the end of the array.
- Iterate in reverse (from the last element to the second, hence nums[:0:-1]) to calculate d. At each step, update d by adding the difference between the current element x and mx only if that difference is positive. In other words, if the element x is larger than mx, we need to 'push' some of its value to its left neighbor.
- Finally, add d to the first element nums[0] and check if it still does not exceed mx. If it does not, return True; otherwise, False.
Binary Search Logic: Use the result of the check function inside the binary search loop. If check(mid) returns True, the current guess can be achieved, and perhaps a lower maximum value is possible, so we update right to mid. Conversely, if check(mid) returns False, we must increase our guess and move the lower boundary up, setting left to mid + 1.
Binary Search Conclusion: The binary search concludes when left equals right, indicating that the search range has been narrowed down to a single element—this element is the minimum possible maximal value that can be achieved in the nums array after performing any number of operations.

This solution effectively combines binary search with a greedy strategy in the check function to ensure that all potential operations are taken into account from right to left, simulating the effect that the operations would have on an array and determining the viability of a selected maximum value. The use of binary search drastically reduces the number of checks needed compared to a linear search and finds the optimal solution efficiently.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Assume we have an array nums = [3, 1, 5, 6, 8, 7] with n = 6 non-negative integers. We need to minimize the value of the maximum integer in the array after performing our operations.

Initialize our binary search range with left = 0 and right = max(nums) = 8.
Conduct a binary search. The first mid value will be (0 + 8) / 2 = 4.
Run the check function with mx = 4:
- Start iterating from the end:
  - nums[5] = 7, d += 7 - 4 = 3 (since 7 is greater than 4)
  - nums[4] = 8, d += 8 - 4 = 7 (total d becomes 10)
  - nums[3] = 6, d += 6 - 4 = 12 (total d becomes 12)
  - nums[2] = 5, d += 5 - 4 = 13 (total d becomes 13)
  - nums[1] does not contribute since 1 is not greater than 4
  Now, adding the total d (13) to nums[0] which is 3, we have 3 + 13 = 16, which is greater than mx = 4, so our check function returns False.
Since the check function returned False, we can't attain a maximum with 4. We adjust our binary search range, setting left to mid + 1, which is 5.
With a new search range left = 5 and right = 8, we calculate a new mid value of (5 + 8) / 2 = 6 and repeat the check function. We keep iterating this process until we find the mid value for which the check function returns True.
When we finally find the smallest mid for which the check function returns True, we have found the smallest possible value of the largest number in the array after performing the operations. For this example, let's assume through the binary search process, we find that the smallest maximum we can achieve is 5.
The solution approach successfully minimizes the maximum value in the array with the optimal use of operations detailed in the given problem.

Solution Implementation

1class Solution:
2    def minimizeArrayValue(self, nums: List[int]) -> int:
3
4        # Function to check if a given maximum value can be achieved
5        # by distributing the values across the nums array.
6        def is_valid(max_value):
7            # 'additional' keeps track of the value that needs to be distributed
8            # to achieve the max_value in the nums array.
9            additional = 0
10            # Iterating backwards to check if it's possible to reduce
11            # all values to at most max_value by distribution.
12            for num in nums[:-1][::-1]:
13                additional = max(0, additional + num - max_value)
14            # Check if the first element plus the distributable amount is less than
15            # or equal to the maximum value after distribution.
16            return nums[0] + additional <= max_value
17
18        # Binary search to find the minimum possible maximum value in the array
19        # after redistribution.
20        left = 0              # Minimum possible value
21        right = max(nums)     # Maximum possible value in the original array
22      
23        # Perform binary search to find the minimum maximum value.
24        while left < right:
25            mid = (left + right) // 2
26            # If the mid value is a valid maximum, we try to see if there's a smaller maximum.
27            if is_valid(mid):
28                right = mid
29            # If the mid value is not valid, we search for a larger value that might be valid.
30            else:
31                left = mid + 1
32        # The binary search loop exits when left == right, which is the minimum maximum value.
33        return left
34

1class Solution {
2    private int[] nums; // Array to store the input numbers
3
4    // Method to find the minimum possible max value of the array after modifications
5    public int minimizeArrayValue(int[] nums) {
6        this.nums = nums; // Initialize the global array with the input array
7        int left = 0; // Start of the search range
8        int right = findMaxValue(nums); // End of the search range, which is the max value in nums
9      
10        // Binary search to find the minimum possible value
11        while (left < right) {
12            int mid = (left + right) / 2; // Middle value of the current search range
13            if (canBeMinimizedTo(mid)) {
14                right = mid; // If can minimize to `mid`, continue search on the left half
15            } else {
16                left = mid + 1; // Otherwise, search on the right half
17            }
18        }
19      
20        return left; // The minimum possible max value after minimization
21    }
22
23    // Method to check if we can minimize the array to a certain max value
24    private boolean canBeMinimizedTo(int maxVal) {
25        long deficit = 0; // Tracks the required decrease to achieve maxVal
26        // Iterate backward through the array
27        for (int i = nums.length - 1; i > 0; --i) {
28            // Accumulate the deficit from the end of the array to the start
29            deficit = Math.max(0, deficit + nums[i] - maxVal);
30        }
31        // Check if we can minimize the first element with the accumulated deficit
32        return nums[0] + deficit <= maxVal;
33    }
34
35    // Helper method to find the maximum value in an array
36    private int findMaxValue(int[] nums) {
37        int maxValue = nums[0]; // Initialize with the first element of the array
38        // Iterate over the array to find the maximal value
39        for (int num : nums) {
40            maxValue = Math.max(maxValue, num);
41        }
42        return maxValue; // Return the found maximum
43    }
44}
45

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int minimizeArrayValue(std::vector<int>& nums) {
7        // Initialize the search range for the minimum possible max value
8        int minPossibleValue = 0;
9        int maxPossibleValue = *max_element(nums.begin(), nums.end());
10      
11        // Define a lambda function to check if a given max value is possible
12        // by distributing values from right to left
13        auto canDistribute = [&](int maxValue) {
14            long excess = 0;
15            // Iterate over the array from the end to start (excluding the first element)
16            for (int i = nums.size() - 1; i > 0; --i) {
17                // Calculate the excess that needs to be distributed to the left
18                excess = std::max(0l, excess + nums[i] - maxValue);
19            }
20            // The first element plus any excess should not exceed the max value
21            return nums[0] + excess <= maxValue;
22        };
23
24        // Perform a binary search to find the minimum max value that satisfies
25        // the distribution criteria
26        while (minPossibleValue < maxPossibleValue) {
27            int mid = (minPossibleValue + maxPossibleValue) / 2;
28
29            // If the current midway value works, try to see if we can lower it
30            if (canDistribute(mid))
31                maxPossibleValue = mid;
32            // If it doesn't work, we need to try a higher value
33            else
34                minPossibleValue = mid + 1;
35        }
36
37        // The left pointer will point to the smallest max value that works, so return it
38        return minPossibleValue;
39    }
40};
41

1// TypeScript code equivalent of the provided C++ code
2
3// Import array related utilities
4import { max } from 'lodash';
5
6// Define a method to minimize the array value
7function minimizeArrayValue(nums: number[]): number {
8    // Initialize the search range for the minimum possible max value
9    let minPossibleValue: number = 0;
10    let maxPossibleValue: number = max(nums) as number;
11
12    // Define a lambda function to check if a given max value is possible
13    // by distributing values from right to left
14    const canDistribute = (maxValue: number): boolean => {
15        let excess: number = 0;
16        // Iterate over the array from the end to start (excluding the first element)
17        for (let i: number = nums.length - 1; i > 0; --i) {
18            // Calculate the excess that needs to be distributed to the left
19            // If positive, add it to the current excess, otherwise keep the current excess
20            excess = Math.max(0, excess + nums[i] - maxValue);
21        }
22        // The first element plus any excess should not exceed the max value
23        return nums[0] + excess <= maxValue;
24    };
25
26    // Perform a binary search to find the minimum max value that satisfies
27    // the distribution criteria
28    while (minPossibleValue < maxPossibleValue) {
29        let mid: number = Math.floor((minPossibleValue + maxPossibleValue) / 2);
30
31        // If the current midway value works, try to see if we can lower it
32        if (canDistribute(mid)) {
33            maxPossibleValue = mid;
34        }
35        // If it doesn't work, we need to try a higher value
36        else {
37            minPossibleValue = mid + 1;
38        }
39    }
40
41    // The minPossibleValue will point to the smallest max value that works, so return it
42    return minPossibleValue;
43}
44
45// Example usage:
46// const nums: number[] = [10, 20, 30];
47// const minimizedValue: number = minimizeArrayValue(nums);
48// console.log(minimizedValue); // Output will vary based on function implementation
49

Time and Space Complexity

The given code implements a binary search algorithm to minimize the maximum value in the array after applying the specified operation. Here's the analysis of its time and space complexity:

Time Complexity:

The while loop in the code is running a binary search over the range 0 to max(nums), which has at most log(max(nums)) iterations since we're halving the search space in every step. The check function is called inside the loop and it iterates through the array in reverse, which takes O(n) time. Therefore, the time complexity of the code is O(n * log(max(nums))).

Space Complexity:

The space complexity of the code is O(1). The algorithm uses a constant number of variables (d, mx, left, right, mid) and the space occupied by these does not depend on the size of the input array nums. The function check also does not use any additional space that scales with the size of the input, as it works in place.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know