Solution Approach

The solution uses binary search to find the minimum possible maximum value. The key insight is that this problem has a monotonic property: if we can achieve a maximum value of mx, we can also achieve any value greater than mx. This creates a feasibility pattern of [false, false, ..., true, true, ...] as we increase the target maximum.

Binary Search Template: We use the standard binary search template with first_true_index to find the minimum achievable maximum:

left, right = 0, max(nums) first_true_index = -1  while left <= right:  mid = (left + right) // 2  if feasible(mid):  first_true_index = mid  right = mid - 1  else:  left = mid + 1  return first_true_index

Feasible Function: The feasible(target_max) function determines if we can redistribute values such that no element exceeds target_max:

1. Initialize excess = 0 to track accumulated values that must be pushed left
2. Iterate through the array from right to left (excluding the first element)
3. For each element: excess = max(0, excess + current_value - target_max)
4. Return True if nums[0] + excess <= target_max

Why the Template Works Here:

• When feasible(mid) returns True, we record mid as a candidate answer and search for smaller values (right = mid - 1)
• When feasible(mid) returns False, we need larger values (left = mid + 1)
• The first_true_index tracks the minimum achievable maximum

Why the Greedy Check Works:

• Processing right to left pushes excess values leftward (the only direction allowed)
• Each position can reduce its value to at most target_max, with excess going left
• The first element must absorb all accumulated excess since it cannot push further left
• If nums[0] + excess > target_max, the target is impossible

Time Complexity: O(n × log(max(nums))) where n is the array length 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, first_true_index = -1
• We'll search for the minimum possible maximum value using the template

Step 2: First Iteration (left=0, right=7)

• mid = (0 + 7) // 2 = 3
• feasible(3):
  • Start with excess = 0
  • Process nums[3] = 6: excess = max(0, 0 + 6 - 3) = 3
  • Process nums[2] = 1: excess = max(0, 3 + 1 - 3) = 1
  • Process nums[1] = 7: excess = max(0, 1 + 7 - 3) = 5
  • Check: nums[0] + excess = 3 + 5 = 8 > 3 → False
• Since feasible(3) = False: left = mid + 1 = 4

Step 3: Second Iteration (left=4, right=7)

• mid = (4 + 7) // 2 = 5
• feasible(5):
  • Start with excess = 0
  • Process nums[3] = 6: excess = max(0, 0 + 6 - 5) = 1
  • Process nums[2] = 1: excess = max(0, 1 + 1 - 5) = 0
  • Process nums[1] = 7: excess = max(0, 0 + 7 - 5) = 2
  • Check: nums[0] + excess = 3 + 2 = 5 ≤ 5 → True
• Since feasible(5) = True: first_true_index = 5, right = mid - 1 = 4

Step 4: Third Iteration (left=4, right=4)

• mid = (4 + 4) // 2 = 4
• feasible(4):
  • Start with excess = 0
  • Process nums[3] = 6: excess = max(0, 0 + 6 - 4) = 2
  • Process nums[2] = 1: excess = max(0, 2 + 1 - 4) = 0
  • Process nums[1] = 7: excess = max(0, 0 + 7 - 4) = 3
  • Check: nums[0] + excess = 3 + 3 = 6 > 4 → False
• Since feasible(4) = False: left = mid + 1 = 5

Step 5: Termination

• left = 5 > right = 4, loop exits
• Return first_true_index = 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]

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. Using Wrong Binary Search Template Variant

The most important pitfall is using the wrong binary search template. This problem requires the first_true_index template with while left <= right and right = mid - 1:

Wrong Template:

while left < right:  mid = (left + right) // 2  if feasible(mid):  right = mid # WRONG: should be mid - 1  else:  left = mid + 1 return left # WRONG: should return first_true_index

Correct Template:

left, right = 0, max(nums) first_true_index = -1  while left <= right:  mid = (left + right) // 2  if feasible(mid):  first_true_index = mid  right = mid - 1  else:  left = mid + 1  return first_true_index

2. Incorrect Iteration Direction in Feasible Function

A common mistake is iterating from left to right instead of right to left when checking feasibility:

Wrong Approach:

def feasible(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

Correct Approach:

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

3. Forgetting to Handle the First Element Separately

The first element (index 0) is special - it cannot pass values to the left:

Wrong:

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

Correct:

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

4. Integer Overflow with Large Values

When working with large numbers, accumulated excess can overflow. While Python handles big integers automatically, in other languages use appropriate data types (long long in C++, long in Java).

5. Misunderstanding the Operation Direction

Values can ONLY move from right to left (from nums[i] to nums[i-1]). If bidirectional movement were allowed, you could simply average all values.