# Minimize Maximum of Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimize-maximum-of-array)
Canonical: https://scaleengineer.com/dsa/problems/minimize-maximum-of-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Paytm](https://scaleengineer.com/companies/paytm)
---
## Problem
You are given a **0-indexed** array `nums` comprising of `n` non-negative integers.

In one operation, you must:

* Choose an integer `i` such that `1 <= i < n` and `nums[i] > 0`.
* Decrease `nums[i]` by 1.
* Increase `nums[i - 1]` by 1.

Return _the **minimum** possible value of the **maximum** integer of_ `nums` _after performing **any** number of operations_.

**Example 1:**

**Input:** nums = [3,7,1,6]
**Output:** 5
**Explanation:**
One set of optimal operations is as follows:
1. Choose i = 1, and nums becomes [4,6,1,6].
2. Choose i = 3, and nums becomes [4,6,2,5].
3. Choose i = 1, and nums becomes [5,5,2,5].
The maximum integer of nums is 5. It can be shown that the maximum number cannot be less than 5.
Therefore, we return 5.

**Example 2:**

**Input:** nums = [10,1]
**Output:** 10
**Explanation:**
It is optimal to leave nums as is, and since 10 is the maximum value, we return 10.

**Constraints:**

* `n == nums.length`
* `2 <= n <= 105`
* `0 <= nums[i] <= 109`

# Approaches
## Binary Search on the Answer
This approach uses binary search to find the minimum possible value for the maximum element in the array. The key observation is the monotonic nature of the problem: if a maximum value of `x` is achievable, any value greater than `x` is also achievable. This allows us to search for the smallest possible `x` in a defined range (e.g., 0 to 10^9). For each candidate value `mid` in our binary search, we have a checker function that determines in linear time if it's possible to make all array elements less than or equal to `mid`. By repeatedly narrowing the search space, we can efficiently converge on the optimal answer.
**Time:** O(N * log(K)), where N is the length of the array and K is the range of possible values for the answer (from 0 to 10^9). The `check` function takes O(N) time, and it is called O(log K) times by the binary search. · **Space:** O(1) extra space.
**Pros:** This is a standard and powerful technique for 'minimize the maximum' or 'maximize the minimum' type problems.; The logic is robust and easier to come up with if the monotonic property is identified.
**Cons:** It is not the most optimal solution in terms of time complexity.; The time complexity has a logarithmic factor, making it slower than a linear-time solution for large input ranges.
### Explanation
```java
class Solution {
    public int minimizeArrayValue(int[] nums) {
        int low = 0;
        int high = 1_000_000_000; // Max constraint for nums[i]
        int ans = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(nums, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    // Helper function to check if it's possible to make all elements <= targetMax
    private boolean check(int[] nums, int targetMax) {
        long prefixSum = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            // The sum of the first i+1 elements cannot exceed what's possible
            // if all of them were at the targetMax value.
            if (prefixSum > (long)(i + 1) * targetMax) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- The problem asks to minimize a maximum value, which suggests that binary search on the answer is a viable strategy. The core idea is that if we can make the array's maximum value equal to `x`, we can certainly make it equal to any value `y > x`. This monotonicity allows for binary search.
- We define a search space for the answer, from `low = 0` to `high = 10^9` (the maximum possible value of an element).
- In each step, we pick a `mid` value and use a helper function, `check(mid)`, to determine if it's possible to transform the array such that all its elements are less than or equal to `mid`.
- The `check(mid)` function works by iterating through the array and verifying a crucial condition for each prefix. For any prefix `nums[0...i]`, the sum of its elements can only be redistributed among those `i+1` positions. Therefore, to make each of these elements at most `mid`, their total sum must not exceed `(i+1) * mid`. If `sum(nums[0...i]) > (i+1) * mid` for any `i`, then `mid` is not a feasible maximum.
- If `check(mid)` returns `true`, it means `mid` is a possible answer, so we try for a smaller one by setting `high = mid - 1`.
- If `check(mid)` returns `false`, `mid` is too small, and we must allow a larger maximum by setting `low = mid + 1`.
- The loop continues until `low` and `high` converge, and the smallest `mid` for which `check(mid)` was true is our answer.

## Greedy Prefix Sum Approach
This is a more efficient, linear-time approach that directly calculates the answer in a single pass. It's based on a crucial observation about the array prefixes. The sum of any prefix `nums[0...i]` can only be redistributed among its `i+1` elements. For the maximum element in this prefix to be minimized, the values should be as evenly distributed as possible. The limiting factor for the entire array's maximum value is the prefix that has the highest average value (`prefix_sum / (i+1)`). By iterating through the array, calculating the running prefix sum, and finding the maximum of these prefix averages (rounded up), we can find the minimum possible maximum for the entire array.
**Time:** O(N), where N is the length of the array. We iterate through the array just once. · **Space:** O(1) extra space, as we only need a few variables to store the running prefix sum and the answer.
**Pros:** Extremely efficient with a linear time complexity.; Requires only a single pass over the input array.; Simple and concise to implement once the logic is understood.
**Cons:** The mathematical insight behind why this greedy prefix-based approach works is less intuitive than the binary search method.
### Explanation
```java
class Solution {
    public int minimizeArrayValue(int[] nums) {
        long prefixSum = 0;
        long ans = 0;

        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            
            // We need to find the ceiling of the average of the current prefix.
            // The average is prefixSum / (i + 1).
            // ceil(a / b) can be calculated with integer division as (a + b - 1) / b.
            // Here, a = prefixSum, b = i + 1.
            long currentCeilAvg = (prefixSum + i) / (i + 1);
            
            // The answer is the maximum of these ceiling averages over all prefixes.
            ans = Math.max(ans, currentCeilAvg);
        }

        return (int)ans;
    }
}
```
### Algorithm
- The core insight is that for any prefix of the array `nums[0...i]`, the sum of its elements `sum(nums[0...i])` is an invariant for that prefix. This is because operations only move values from an index `j` to `j-1`, so no value can enter the prefix from the right (from an index greater than `i`).
- For the final array to have a maximum value of `ans`, every element must be less than or equal to `ans`. This implies that for any prefix `nums[0...i]`, the sum of its `i+1` elements must be at most `(i+1) * ans`.
- Therefore, for our target `ans` to be feasible, the following condition must hold for all `i` from `0` to `n-1`: `sum(nums[0...i]) <= (i+1) * ans`.
- This can be rewritten as `ans >= sum(nums[0...i]) / (i+1)`. Since `ans` must be an integer, we have `ans >= ceil(sum(nums[0...i]) / (i+1))`. 
- To satisfy this for all prefixes, `ans` must be at least the maximum of these required values. The minimum possible `ans` is therefore `max(ceil(sum(nums[0...i]) / (i+1)))` over all `i`.
- The algorithm iterates through the array once, maintaining a running `prefixSum`. In each step, it calculates the average of the current prefix rounded up and updates the overall maximum seen so far.

# Solutions
### Java

```java
class Solution {
private
  int[] nums;
public
  int minimizeArrayValue(int[] nums) {
    this.nums = nums;
    int left = 0, right = max(nums);
    while (left < right) {
      int mid = (left + right) >> 1;
      if (check(mid)) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
private
  boolean check(int mx) {
    long d = 0;
    for (int i = nums.length - 1; i > 0; --i) {
      d = Math.max(0, d + nums[i] - mx);
    }
    return nums[0] + d <= mx;
  }
private
  int max(int[] nums) {
    int v = nums[0];
    for (int x : nums) {
      v = Math.max(v, x);
    }
    return v;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimizeArrayValue(vector<int> &nums) {
    int left = 0, right = *max_element(nums.begin(), nums.end());
    auto check = [&](int mx) {
      long d = 0;
      for (int i = nums.size() - 1; i; --i) {
        d = max(0l, d + nums[i] - mx);
      }
      return nums[0] + d <= mx;
    };
    while (left < right) {
      int mid = (left + right) >> 1;
      if (check(mid))
        right = mid;
      else
        left = mid + 1;
    }
    return left;
  }
};

```

### Python

```python
class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int: def check(mx): d = 0 for x in nums[: 0: - 1]: d = max(0, d + x - mx) return nums[0] + d <= mx left, right = 0, max(nums) while left < right: mid = (left + right) >> 1 if check(mid): right = mid else: left = mid + 1 return left

```