Problem Statement

Given a positive integer array nums, return the minimum possible value of the maximum integer of nums after performing multiple operations.

In one operation, you must:

• Select any index i such that 1 <= i < n and nums[i] > 0.
• Increase nums[i - 1] by 1.
• Decrease nums[i] by 1.

Examples

Example 1:

• Input: nums = [4, 5, 3, 2, 1, 6]
• Expected Output: 5
• Justification: We can perform operations to decrease the last element (6) to 5 and increase the fifth element to 2. Here, the maximum array element is 5.

Example 2:

• Input: nums = [1, 2, 3, 4]
• Expected Output: 3
• Justification: We can decrease the last element (4) to 3 and increase the third element to 4, then decrease the third element (now 4) to 3, increasing the second element to 3. The array becomes [1, 3, 3, 3], with the maximum being 3.

Example 3:

• Input: nums = [8, 2, 2, 3]
• Expected Output: 8
• Justification: We can't perform any operation to minimize the maximum value of the array. So, 8 is the minimum possible value of the maximum integer.

Solution

To solve this problem, we adopt a strategy that leverages the cumulative sum of the array elements to find the minimum possible maximum value after performing the allowed operations. The core idea is to iteratively calculate the cumulative sum up to each index and use this sum to determine the maximum average value that can be achieved by redistributing the numbers.

This approach is grounded in the insight that the minimum possible maximum value, after any number of operations, is essentially the ceiling of the maximum average of the cumulative sums up to each point in the array. By calculating these averages and keeping track of the highest one, we can deduce the minimum maximum value achievable. This method is effective because it directly addresses the problem's goal without needing to explicitly perform the redistributions, thereby offering a more efficient solution.

Step-by-Step Algorithm

1. Initialize a variable sum to 0 to keep track of the cumulative sum of the array elements.
2. Initialize another variable ans to 0 to store the maximum average found during the iteration.
3. Iterate through the array using a loop:
   • For each element at index i, add it to sum to update the cumulative sum.
   • Calculate the average up to the current index as (sum + i) / (i + 1). This formula accounts for the zero-based indexing and ensures that the division is done considering the total number of elements counted so far.
   • Update ans with the maximum value between the current ans and the calculated average. This step ensures that ans always holds the highest average value found.
4. After completing the iteration, ans will hold the minimum possible maximum value of the array after the operations. Convert ans to an integer (if necessary) and return it as the solution.

Algorithm Walkthrough

Input: nums = [4, 5, 3, 2, 1, 6].

• Initial State:

  • nums = [4, 5, 3, 2, 1, 6]
  • sum = 0
  • ans = 0

• Iteration 1:

  • i = 0, nums[i] = 4
  • sum = 4
  • average = (4 + 0) / (0 + 1) = 4
  • ans = max(0, 4) = 4

• Iteration 2:

  • i = 1, nums[i] = 5
  • sum = 4 + 5 = 9
  • average = (9 + 1) / (1 + 1) = 5
  • ans = max(4, 5) = 5

• Iteration 3:

  • i = 2, nums[i] = 3
  • sum = 9 + 3 = 12
  • average = (12 + 2) / (2 + 1) = 4.666...
  • ans = max(5, 4.666...) = 5

• Iteration 4:

  • i = 3, nums[i] = 2
  • sum = 12 + 2 = 14
  • average = (14 + 3) / (3 + 1) = 4.25
  • ans = max(5, 4.25) = 5

• Iteration 5:

  • i = 4, nums[i] = 1
  • sum = 14 + 1 = 15
  • average = (15 + 4) / (4 + 1) = 3.8
  • ans = max(5, 3.8) = 5

• Iteration 6:

  • i = 5, nums[i] = 6
  • sum = 15 + 6 = 21
  • average = (21 + 5) / (5 + 1) = 4.333...
  • ans = max(5, 4.333...) = 5

• Final State:

  • ans = 5

Code