Minimize Maximum of Array

Intuitionwhy every prefix limits the final maximum

An operation moves one unit only to the left. Therefore, for any prefix from index 0 through index i, its total can never decrease: units from later positions may enter it, but no unit can leave it. If every final value is at most M, that prefix can contain at most (i + 1) times M units. Its original sum therefore forces M to be at least the ceiling of that prefix sum divided by its length.

This gives a lower bound for every prefix, not just for the whole array. The strongest bound is the largest prefix ceiling. It is also achievable: whenever a prefix has more units than its current limit allows, later positions can send those excess units leftward; when it has no excess, nothing must cross its boundary. Processing prefixes from left to right lets you record the strongest bound as soon as it appears.

The only arithmetic detail is the ceiling. For a prefix sum sum and length len, ceiling(sum / len) is (sum + len - 1) / len with integer division. With i as a zero-based index, len is i + 1, so the expression becomes (sum + i) / (i + 1).

Approachone scan of all prefix lower bounds

1. 1Keep a 64-bit running sum and a running answer, because the prefix total can be as large as 10^14 even though each individual value fits in an int.
2. 2Visit the array from left to right, adding nums[i] to the running sum so the current prefix represents every unit that cannot be moved out of that prefix.
3. 3Compute the ceiling of the current prefix average as (sum + i) / (i + 1), because flooring the division would allow a maximum smaller than the units this prefix must hold.
4. 4Update the answer with the larger of its old value and this ceiling, because every prefix imposes its own lower bound and the final maximum must satisfy them all.
5. 5Return the largest recorded ceiling; no simulation is needed because the prefix bounds are not only necessary but jointly achievable by moving excess units from right to left.

Complexitythe scan uses constant working memory

Annotated solutionC++ · one pass · prefix ceilings are the complete proof

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int minimizeArrayValue(vector<int>& nums) {
        long long sum = 0;
        long long answer = 0;

        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            sum += nums[i];
            long long prefixCeiling = (sum + i) / (i + 1);
            answer = max(answer, prefixCeiling);
        }

        return static_cast<int>(answer);
    }
};

The expression (sum + i) / (i + 1) is the ceiling of the average because i is one less than the prefix length. The answer is updated after adding the current element, so every prefix from length one through n contributes a bound. The 64-bit sum is essential even though the returned answer fits in int.

The binary-search alternativea feasibility check trades simplicity for another logarithmic factor

You can also guess a maximum M and check whether the array can be transformed so every value is at most M. Process from right to left: if nums[i] exceeds M, move exactly that excess to index i - 1. This is the only useful direction, and handling the rightmost positions first ensures every excess has a path toward the left. If the scan finishes, M is feasible.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int minimizeArrayValue(vector<int>& nums) {
        long long low = 0;
        long long high = *max_element(nums.begin(), nums.end());

        while (low < high) {
            long long limit = low + (high - low) / 2;
            long long excess = 0;

            for (int i = static_cast<int>(nums.size()) - 1; i >= 0; --i) {
                long long value = nums[i] + excess;
                if (value > limit) {
                    excess = value - limit;
                } else {
                    excess = 0;
                }
            }

            if (excess == 0) {
                high = limit;
            } else {
                low = limit + 1;
            }
        }

        return static_cast<int>(low);
    }
};

This is a different arrangement, not an optimisation. The check costs O(n), and binary search performs O(log V) checks, where V is the largest initial array value, so the total is O(n log V) instead of O(n). It can feel natural when the question is phrased as a feasibility test, but the prefix-ceiling scan is shorter and faster here.

Common mistakestwo wrong lines that often survive a first test