MediumBinary SearchGreedy

Maximum Value at a Given Index in a Bounded Array

1 approach, code in every language

You must build an array of exactly n positive integers subject to three rules: every element is at least 1, the absolute difference between any two adjacent elements is at most 1, and the total of all elements does not exceed a given budget maxSum. Among all arrays that satisfy these rules, you want the one whose value at a fixed position index is as large as possible.

Return that largest achievable value at position index.

Example 1

Input: n = 4, index = 2, maxSum = 6

Output: 2

The array [1, 1, 2, 1] uses a total of 5 (within the budget of 6) and places the value 2 at index 2. No valid array can push index 2 higher without breaking a rule.

Example 2

Input: n = 6, index = 1, maxSum = 10

Output: 3

The array [2, 3, 2, 1, 1, 1] sums to 10 and places 3 at index 1, which is the maximum possible peak for that position under the budget.

Constraints

1 <= n <= 10^9
0 <= index < n
1 <= maxSum <= 10^9

Binary Search on the Peak Value

Guess the value at index, and check whether the cheapest array with that peak fits the budget.

Loading animation…

Intuition

If a peak value at index is feasible, then any smaller peak is also feasible, which makes the answer monotonic and perfect for binary search. For a fixed peak value, the cheapest valid array decreases by exactly 1 on each step away from index and then flattens out at 1 once it cannot decrease any further. The minimal cost of a slope is therefore an arithmetic series that gets clamped to 1s, and we can compute it directly with a closed form. We binary search the peak value and keep the largest one whose minimal total stays within maxSum.

Algorithm walkthrough

1Define a helper that, given a peak value and how many elements sit on one side, returns the smallest possible sum of that side (values step down from peak - 1 and never go below 1).
2Define the total minimal cost of a peak as the left side plus the right side plus the peak itself.
3Binary search the peak value between 1 and maxSum, using long or big-integer arithmetic to avoid overflow.
4For a candidate value, if its total minimal cost is within maxSum, record it and search higher; otherwise search lower.
5Return the largest feasible peak value found.

Implementation

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        def side_sum(peak: int, count: int) -> int:
            if count < peak:
                return (peak - 1 + peak - count) * count // 2
            full = peak * (peak - 1) // 2
            ones = count - (peak - 1)
            return full + ones

        def total(peak: int) -> int:
            return side_sum(peak, index) + side_sum(peak, n - index - 1) + peak

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

Time

O(log(maxSum))

Space

O(1)

Each candidate peak is evaluated in constant time using closed-form slope sums.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

The Tallest Post at a Chosen Place is our own problem on the technique behind Maximum Value at a Given Index in a Bounded Array: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free