MediumArrayBinary SearchDynamic ProgrammingGreedyPrefix SumUpdated Sep 2026

2439. Minimize Maximum of Array

Asked at Visa

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given an array nums of non-negative integers. In one operation you pick an index i with 1 <= i < n and nums[i] > 0, then move one unit from nums[i] to its left neighbor: nums[i] goes down by 1 and nums[i-1] goes up by 1.

You may do this any number of times (including zero). Return the smallest possible value of the maximum element in the array after all your operations.

The key restriction is that value only flows left. A unit can never move right, so the first i+1 elements can never give away their total to the elements after them.

Units only move left

37160123iPick i = 1: nums[1] drops by 1 and nums[0] rises by 1total 10, stuck here46160123The first two elements hold 10 units forever — none ofit can escape to the right
Each operation shifts one unit from an element to its left neighbor, so the first k elements can never lose their total.

Constraints

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

Examples

Example 1
Inputnums = [3,7,1,6]
Output5
WhyWe can push units left until the array becomes [5,5,2,5]. Its maximum is 5. No sequence of moves can get the maximum below 5, because the first two elements hold 3 + 7 = 10 units and can never send any of it to the right, so one of them must be at least ceil(10/2) = 5.
Example 2
Inputnums = [10,1]
Output10
WhyThe only legal move takes from index 1 and gives to index 0, which makes the maximum worse. So we do nothing and the answer is 10.

Asked At

1 companies
CompanyDifficulty
VisaMediumView all Visa questions →

How to Think About It

1

Units only move leftward, so the first i + 1 elements can never shed their total — they can only spread it evenly among themselves.

2

For each prefix, the best you can do is make its maximum ceil(prefixSum / (i + 1)). So the answer is at least the largest such value over all prefixes.

3

Key insight: that lower bound is also achievable — you can always balance each prefix down to its ceiling average by pushing excess left.

4

So the answer is max over i of ceil(prefix[i] / (i + 1)).

5

Walkthrough for [3,7,1,6]: prefixes 3, 10, 11, 17 -> ceilings 3, 5, 4, 5 -> answer 5.

Optimal Approach

Step 1: total = 0, best = 0.
Step 2: For each index i: total += nums[i]; best = max(best, ceil(total / (i + 1))).
Step 3: Return best.

Time: O(n). Space: O(1).

Prefix averages give the answer

31011170123Prefix sums of [3,7,1,6] are 3, 10, 11, 1735450123Ceilings of prefixSum / (i+1): ceil(3/1)=3,ceil(10/2)=5, ceil(11/3)=4, ceil(17/4)=5best = max(best, ceil(total / (i+1)))answer = 5
For every prefix, the best possible maximum is its ceiling average, and the largest such value over all prefixes is achievable.
ComplexityTime O(n)Space O(1)One pass over the array keeps a running prefix sum, and only a few variables are stored.

What Trips People Up in Real Interviews

1

Simulating the moves one unit at a time — values reach 10^9.

2

Binary searching the answer without noticing the closed-form prefix-average bound (binary search works, but explain the monotone check).

3

Using floor instead of ceiling division.

4

Overflow of the prefix sum in C++/Java; use 64-bit.

Solution Code

O(n) time
def minimizeArrayValue(nums):
    total = best = 0
    for i, x in enumerate(nums):
        total += x
        best = max(best, (total + i) // (i + 1))
    return best

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimize Maximum of Array problem?

Minimize Maximum of Array lets you repeatedly move one unit from `nums[i]` to `nums[i-1]`. What is the smallest possible maximum value? Value can only flow left, so the answer is governed by prefix averages.

How do you solve Minimize Maximum of Array?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimize Maximum of Array?

Minimize Maximum of Array is asked at Visa. It is a medium difficulty problem.

What are common mistakes on Minimize Maximum of Array?
  • Simulating the moves one unit at a time — values reach `10^9`.
  • Binary searching the answer without noticing the closed-form prefix-average bound (binary search works, but explain the monotone check).
  • Using floor instead of ceiling division.
  • Overflow of the prefix sum in C++/Java; use 64-bit.