Minimize maximum of array

Array Binary Search Dynamic Programming Greedy Prefix Sum

46.5% acceptance

Feb 25, 2026

2580

645

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 perfor ming any number of operations. *

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimize_array_value(nums: Vec<i32>) -> i32 {
    // Answer = max over all i of ceil(prefix_sum[i+1] / (i+1))
    let mut ans = 0i64;
    let mut prefix = 0i64;
    for (i, &v) in nums.iter().enumerate() {
      prefix += v as i64;
      let ceil_avg = (prefix + i as i64) / (i as i64 + 1);
      ans = ans.max(ceil_avg);
    }
    ans as i32
  }
}