Problem Description

You have an array nums with n non-negative integers (0-indexed).

You can perform the following operation any number of times:

• Pick an index i where 1 <= i < n and nums[i] > 0
• Decrease nums[i] by 1
• Increase nums[i-1] by 1

This operation essentially moves one unit from position i to position i-1 (shifting value leftward).

Your goal is to minimize the maximum value in the array after performing any number of these operations. Return this minimum possible maximum value.

For example, if you have nums = [3, 7, 1, 6], you can perform operations to redistribute values leftward to minimize the largest element in the resulting array.

The key insight is that you can only move values leftward (from higher indices to lower indices), never rightward. This means each element can potentially receive contributions from elements to its right, but can only give to the element immediately to its left.

The solution uses binary search to find the minimum possible maximum value. For each candidate maximum value mx, it checks whether it's achievable by simulating the process backwards - starting from the rightmost element and calculating how much excess needs to be pushed left if we want to keep all elements at most mx. If the first element (which cannot push anything further left) ends up exceeding mx after receiving all the excess, then mx is not achievable.

Intuition

The first observation is that we're trying to minimize the maximum value, which suggests binary search might be useful. Why? Because if we can achieve a maximum value of mx, then we can also achieve any value greater than mx. This monotonic property makes binary search applicable.

The second key insight is understanding what the operations actually do. Since we can only move values from right to left (from index i to i-1), think of it like water flowing downhill from right to left. Each position can receive "water" from positions to its right and pass it further left.

Now, how do we check if a certain maximum value mx is achievable? We need to verify that we can redistribute the array values such that no element exceeds mx.

Working backwards from right to left makes sense here. For each element nums[i], if it exceeds mx, we need to push the excess (nums[i] - mx) to the left. This excess accumulates as we move left. When we reach nums[0], it has nowhere to push its excess - it must absorb everything. If nums[0] plus all the accumulated excess is still <= mx, then mx is achievable.

Why does this greedy approach work? Because we're forced to handle all excess - we can't leave any element above mx. By processing from right to left and pushing all excess leftward, we're essentially finding the minimum burden on nums[0]. If even this minimum burden makes nums[0] exceed mx, then mx is impossible to achieve.

The binary search range is from 0 to max(nums) because:

• The minimum possible maximum is at least 0 (or could be the average for a tighter bound)
• The maximum possible maximum is the current maximum in the array (we can't increase it)

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

Solution Approach

The solution uses binary search to find the minimum possible maximum value. Here's how the implementation works:

Binary Search Setup:

• Initialize left = 0 and right = max(nums) as the search boundaries
• The answer must lie within this range since we can't make the maximum smaller than 0 or larger than the current maximum

Check Function: The check(mx) function determines if we can achieve a maximum value of mx:

1. Initialize a deficit variable d = 0 to track accumulated excess that needs to be pushed left
2. Iterate through the array from right to left (using nums[:0:-1] which reverses the array except the first element)
3. For each element x:
   • Calculate the total burden: d + x
   • If this exceeds mx, update deficit: d = max(0, d + x - mx)
   • The max(0, ...) ensures we don't have negative deficit
4. Finally, check if nums[0] + d <= mx
   • nums[0] must absorb all the accumulated deficit d
   • If the sum doesn't exceed mx, then mx is achievable

Binary Search Logic:

while left < right:
    mid = (left + right) >> 1  # Equivalent to (left + right) // 2
    if check(mid):
        right = mid  # mid is achievable, try smaller values
    else:
        left = mid + 1  # mid is not achievable, need larger values

The binary search finds the smallest mx where check(mx) returns True.

Why this works:

• When we process from right to left, we greedily push as much excess as possible to the left
• Each position can only reduce its value to at most mx, any excess must go left
• The first element nums[0] becomes the final accumulator - it has no left neighbor to pass excess to
• If even with optimal redistribution nums[0] exceeds mx, then mx is impossible

Time Complexity: O(n * log(max(nums))) where n is the array length

• Binary search runs O(log(max(nums))) iterations
• Each check function takes O(n) time

Space Complexity: O(1) - only using a few variables

Example Walkthrough

Let's walk through the solution with nums = [3, 7, 1, 6].

Step 1: Binary Search Setup

• left = 0, right = max(nums) = 7
• We'll search for the minimum possible maximum value

Step 2: First Binary Search Iteration

• mid = (0 + 7) // 2 = 3

• Check if maximum value of 3 is achievable:

  Check(3) Process (right to left):

  • Start with deficit d = 0
  • Process nums[3] = 6: Total burden = 0 + 6 = 6
    • Exceeds 3, so deficit = 6 - 3 = 3
  • Process nums[2] = 1: Total burden = 3 + 1 = 4
    • Exceeds 3, so deficit = 4 - 3 = 1
  • Process nums[1] = 7: Total burden = 1 + 7 = 8
    • Exceeds 3, so deficit = 8 - 3 = 5
  • Check nums[0]: 3 + 5 = 8 > 3 ❌

  Since check(3) = False, we need a larger value: left = 4

Step 3: Second Binary Search Iteration

• mid = (4 + 7) // 2 = 5

• Check if maximum value of 5 is achievable:

  Check(5) Process:

  • Start with deficit d = 0
  • Process nums[3] = 6: Total burden = 0 + 6 = 6
    • Exceeds 5, so deficit = 6 - 5 = 1
  • Process nums[2] = 1: Total burden = 1 + 1 = 2
    • Doesn't exceed 5, so deficit = 0
  • Process nums[1] = 7: Total burden = 0 + 7 = 7
    • Exceeds 5, so deficit = 7 - 5 = 2
  • Check nums[0]: 3 + 2 = 5 ≤ 5 ✓

  Since check(5) = True, we can try smaller: right = 5

Step 4: Third Binary Search Iteration

• mid = (4 + 5) // 2 = 4

• Check if maximum value of 4 is achievable:

  Check(4) Process:

  • Start with deficit d = 0
  • Process nums[3] = 6: Total burden = 0 + 6 = 6
    • Exceeds 4, so deficit = 6 - 4 = 2
  • Process nums[2] = 1: Total burden = 2 + 1 = 3
    • Doesn't exceed 4, so deficit = 0
  • Process nums[1] = 7: Total burden = 0 + 7 = 7
    • Exceeds 4, so deficit = 7 - 4 = 3
  • Check nums[0]: 3 + 3 = 6 > 4 ❌

  Since check(4) = False: left = 5

Step 5: Termination

• left = right = 5
• Answer: 5

The final redistributed array would be [5, 5, 3, 4] after operations:

• Move 2 from index 3 to 2: [3, 7, 3, 4]
• Move 2 from index 1 to 0: [5, 5, 3, 4]

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log M)

The algorithm uses binary search on the answer space from 0 to max(nums) (which is M). The binary search performs O(log M) iterations. In each iteration, the check function is called, which iterates through the array from the second-to-last element to the first element (excluding index 0), taking O(n) time where n is the length of the array. Therefore, the overall time complexity is O(n × log M).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space. The variables left, right, mid, and d in the check function all use constant space. The iteration through the array in the check function doesn't create any additional data structures proportional to the input size. Therefore, the space complexity is O(1).

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

Common Pitfalls

1. Incorrect Iteration Direction in Check Function

A common mistake is iterating from left to right instead of right to left when checking feasibility. This leads to incorrect logic because:

Wrong Approach:

def check(mx):
    deficit = 0
    for i in range(len(nums)):  # LEFT to RIGHT - WRONG!
        if nums[i] + deficit > mx:
            deficit = nums[i] + deficit - mx
    return True  # No way to validate this

Why it fails: When going left to right, you can't determine what excess will arrive from the right, making it impossible to correctly calculate redistributions.

Correct Approach:

def check(mx):
    deficit = 0
    for x in nums[:0:-1]:  # RIGHT to LEFT - CORRECT!
        deficit = max(0, deficit + x - mx)
    return nums[0] + deficit <= mx

2. Forgetting to Handle the First Element Separately

The first element (index 0) is special - it cannot pass values to the left. A common error is treating it like other elements:

Wrong:

def check(mx):
    deficit = 0
    for x in reversed(nums):  # Includes nums[0] in the loop
        deficit = max(0, deficit + x - mx)
    return deficit == 0  # Wrong validation

Correct:

def check(mx):
    deficit = 0
    for x in nums[:0:-1]:  # Excludes nums[0]
        deficit = max(0, deficit + x - mx)
    return nums[0] + deficit <= mx  # Separate check for nums[0]

3. Integer Overflow with Large Values

When working with large numbers, accumulated deficits can overflow. While Python handles big integers automatically, in other languages this requires attention:

Potential Issue (in languages like Java/C++):

# If nums contains very large values, deficit accumulation might overflow
deficit = deficit + x - mx  # Could overflow in other languages

Solution: Use appropriate data types (long long in C++, long in Java) or add overflow checks.

4. Off-by-One Error in Binary Search

Using the wrong binary search template can cause infinite loops or miss the answer:

Wrong:

while left <= right:  # Using <= can cause issues
    mid = (left + right) // 2
    if check(mid):
        right = mid - 1  # Might skip the answer
    else:
        left = mid + 1

Correct:

while left < right:  # Use < for this template
    mid = (left + right) // 2
    if check(mid):
        right = mid  # Keep mid as potential answer
    else:
        left = mid + 1

5. Misunderstanding the Operation Direction

Some might think values can move in both directions:

Wrong Mental Model: "I can redistribute values freely between adjacent elements"

Correct Understanding: "Values can ONLY move from right to left (from nums[i] to nums[i-1])"

This fundamentally changes the problem - if bidirectional movement were allowed, you could simply average all values, but the constraint makes it more complex.