Minimize Maximum of Array

Medium
1162.

Minimize Maximum of Array

Minimize Maximum of Array is a medium coding problem on arrays, greedy and binary search, asked in Amazon and Google interviews.

nums is a 0-indexed array of non-negative integers. In one operation you pick an index i with 1 <= i < n and nums[i] > 0, decrease nums[i] by 1 and increase nums[i - 1] by 1 — one unit moves one step to the left.

You may perform any number of operations. Return the minimum possible value of the largest element of nums.

Example 1

Input
nums = [2,7,1,6]
Output
5
Explanation
Move 2 units from index 1 to index 0 and 1 unit from index 3 to index 2: `[4,5,2,5]`. The first two elements total 9, so one of them is always at least 5.

Example 2

Input
nums = [9,3]
Output
9
Explanation
Units only move left, so `nums[0]` can never shrink.

Example 3

Input
nums = [0,0,10]
Output
4
Explanation
For example `[4,3,3]`.

Constraints

  • n == nums.length
  • 2 <= n <= 10^5
  • 0 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimizeArrayValue = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimize Maximum of Array — Solution in Python, Java & C++

Minimize Maximum of Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimize Maximum of Array is a medium coding problem on arrays, greedy and binary search, asked in Amazon and Google interviews.

Problem statement

nums is a 0-indexed array of non-negative integers. In one operation you pick an index i with 1 <= i < n and nums[i] > 0, decrease nums[i] by 1 and increase nums[i - 1] by 1 — one unit moves one step to the left.

You may perform any number of operations. Return the minimum possible value of the largest element of nums.

Example 1

Input: nums = [2,7,1,6]
Output: 5
Explanation: Move 2 units from index 1 to index 0 and 1 unit from index 3 to index 2: `[4,5,2,5]`. The first two elements total 9, so one of them is always at least 5.

Example 2

Input: nums = [9,3]
Output: 9
Explanation: Units only move left, so `nums[0]` can never shrink.

Example 3

Input: nums = [0,0,10]
Output: 4
Explanation: For example `[4,3,3]`.

Constraints

  • n == nums.length
  • 2 <= n <= 10^5
  • 0 <= nums[i] <= 10^9

Hints for Minimize Maximum of Array

  1. Hint 1

    Units can only move left, so the first i + 1 elements can never lose their total.

  2. Hint 2

    That makes ceil(prefix_sum(i) / (i + 1)) a lower bound on the answer for every i.

  3. Hint 3

    The largest of those lower bounds is achievable. Compute it in one pass with 64-bit prefix sums (or binary search the answer with a right-to-left carry check).

How to solve Minimize Maximum of Array

Moving units leftwards never changes the total of a prefix except by adding to it, so each prefix's average (rounded up) is a floor on the maximum. The maximum of those floors is also achievable, which turns the problem into one prefix-sum pass.

Approach

  1. Sweep i from 0 to n - 1, keeping the running sum prefix in 64 bits.
  2. Compute ceil(prefix / (i + 1)) as (prefix + i) / (i + 1) with integer division.
  3. Return the largest such value.

Why it works

Lower bound: no operation moves units out of the prefix nums[0..i] (they only move left), so its total stays at least prefix_i, and i + 1 numbers with that total have a maximum of at least ceil(prefix_i / (i + 1)). Achievability: let A be the largest bound. Scanning from the right, any element above A can push its excess one step left; the excess carried into position i never makes the prefix ending there exceed A·(i + 1), so the carry finally absorbed by nums[0] leaves it at most A — every element ends at most A.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Prefix sums reach 10^14; keep them in 64-bit integers.
  • Use integer ceiling division — floating-point division can round across an integer boundary.
  • Units cannot move right, so a large nums[0] is a hard floor on the answer.

Reference solution

Python

from typing import List

def minimizeArrayValue(nums: List[int]) -> int:
    prefix = 0
    best = 0
    for i, x in enumerate(nums):
        prefix += x
        best = max(best, (prefix + i) // (i + 1))
    return best

Java

public static int minimizeArrayValue(int[] nums) {
    long prefix = 0, best = 0;
    for (int i = 0; i < nums.length; i++) {
        prefix += nums[i];
        best = Math.max(best, (prefix + i) / (i + 1));
    }
    return (int) best;
}

C++

int minimizeArrayValue(vector<int>& nums) {
    long long prefix = 0, best = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        prefix += nums[i];
        best = max(best, (prefix + i) / (i + 1));
    }
    return (int)best;
}

JavaScript

var minimizeArrayValue = function(nums) {
    var prefix = 0, best = 0;
    for (var i = 0; i < nums.length; i++) {
        prefix += nums[i];
        var need = Math.floor((prefix + i) / (i + 1));
        if (need > best) best = need;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms