Maximum value at a given index in a bounded array

Math Binary Search Greedy

38.9% acceptance

Feb 25, 2026

2715

478

You are given three positive integers: n, index, and maxSum. You want to construct an array nums (0-indexed) that satisfies the following conditions: nums.length == n nums[i] is a positive integer where 0 <= i < n. abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1. The sum of all the elements of nums does not exceed maxSum. nums[index] is maximized. Return nums[index] of the constructed array. Note that abs(x) equals x if x >= 0, and -x otherwise.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_value(n: i32, index: i32, max_sum: i32) -> i32 {
    let n = n as i64;
    let index = index as i64;
    let max_sum = max_sum as i64;

    fn min_sum_side(v: i64, len: i64) -> i64 {
      if v - 1 >= len {
        // descending: v-1, v-2, ..., v-len
        (2 * v - len - 1) * len / 2
      } else {
        // descending until 1, then padding with 1s
        v * (v - 1) / 2 + (len - (v - 1))
      }
    }

    let mut lo = 1i64;
    let mut hi = max_sum;
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      let total = mid + min_sum_side(mid, index) + min_sum_side(mid, n - 1 - index);
      if total <= max_sum {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    lo as i32
  }
}