Maximum Value at a Given Index in a Bounded Array — Medium Problem & Solution

Problem statement

Build an array nums of length n where every element is a positive integer, adjacent elements differ by at most 1 (|nums[i] - nums[i+1]| <= 1), the total is at most maxSum, and nums[index] is as large as possible.

Return that maximum value of nums[index].

Example 1

Input: n = 4, index = 2, maxSum = 6
Output: 2
Explanation: [1,1,2,1] totals 5 and [1,2,2,1] totals 6.

Example 2

Input: n = 6, index = 1, maxSum = 10
Output: 3
Explanation: [2,3,2,1,1,1] totals 10.

Example 3

Input: n = 1, index = 0, maxSum = 24
Output: 24

Constraints

• 1 <= n <= 100000
• 0 <= index < n
• n <= maxSum <= 1000000000

How to solve Maximum Value at a Given Index in a Bounded Array

Binary search the peak. For a fixed peak, the cheapest legal array descends by exactly 1 per step away from index until it reaches 1, then stays at 1 — any slower descent costs more, and a faster one breaks the adjacency rule.

Approach

1. side(peak, len): the sum of len positions descending from peak - 1. If peak - 1 >= len it is the arithmetic series (peak-1) + … + (peak-len); otherwise it is 1 + … + (peak-1) plus len - (peak-1) ones.
2. can(peak): peak + side(peak, index) + side(peak, n-1-index) <= maxSum.
3. Binary search the largest feasible peak with the upper-biased midpoint.

Why it works

Every element must be at least 1 and adjacent elements differ by at most 1, so an element d steps from the peak is at least max(1, peak - d). The stepped-then-flat array attains that lower bound everywhere, so it is the minimum-cost array with that peak — making can exact. Raising the peak raises every term weakly, so feasibility is monotone.

Complexity

• Time — O(log maxSum)
• Space — O(1)

Pitfalls

• The side sums reach about 10^9 · 10^5 = 10^14, so they need 64-bit arithmetic.
• The plateau of 1s is easy to forget, which overcharges short arrays with tall peaks.
• index counts elements strictly to its left, and n - 1 - index those to its right — the peak itself is counted once.

Reference solution

Python

def maxValue(n: int, index: int, maxSum: int) -> int:
    def side(peak: int, length: int) -> int:
        if length <= 0:
            return 0
        if peak - 1 >= length:
            return ((peak - 1) + (peak - length)) * length // 2
        dec = peak - 1
        return dec * (dec + 1) // 2 + (length - dec)

    def can(peak: int) -> bool:
        return peak + side(peak, index) + side(peak, n - 1 - index) <= maxSum

    lo, hi = 1, maxSum
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if can(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

JavaScript

var maxValue = function(n, index, maxSum) {
    var side = function(peak, len) {
        if (len <= 0) return 0;
        if (peak - 1 >= len) return ((peak - 1) + (peak - len)) * len / 2;
        var dec = peak - 1;
        return dec * (dec + 1) / 2 + (len - dec);
    };
    var can = function(peak) {
        return peak + side(peak, index) + side(peak, n - 1 - index) <= maxSum;
    };
    var lo = 1, hi = maxSum;
    while (lo < hi) {
        var mid = Math.ceil((lo + hi) / 2);
        if (can(mid)) lo = mid; else hi = mid - 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Longest Subsequence With Limited Sum Medium
• K-th Smallest Prime Fraction Medium
• Most Beautiful Item for Each Query Medium
• Find the Safest Path in a Grid Medium
• Longest Arithmetic Subsequence Medium
• Maximum Number of Removable Characters Medium