Maximum Value at a Given Index in a Bounded Array: Binary Search on Answer

Maximum Value at a Given Index in a Bounded Array is LeetCode 1802. You are given three integers n, index, and maxSum. You need to construct an array nums of length n where every element is at least 1, adjacent elements differ by at most 1, and the total sum is at most maxSum. Your goal is to maximize nums[index].

This is a textbook "binary search on the answer" problem. Instead of searching through an array, you search through all possible values for nums[index] and find the largest one that keeps the total sum within budget.

Why this problem matters

Binary search on the answer is one of the most reusable patterns in competitive programming and interviews. You have seen it in problems like Koko Eating Bananas where you search for the minimum valid speed. Here, you flip it: you are searching for the maximum valid peak value. The mechanics are the same, just the direction changes.

The twist in this problem is the feasibility check. You need to compute the minimum possible sum of an array with a given peak value, and you need to do it in O(1) time using arithmetic series formulas. That is where the greedy insight comes in.

The key insight

If you fix the value at index to be v, then to minimize the total sum (giving yourself the best chance of staying within maxSum), you should make every other element as small as possible. The constraints say adjacent elements differ by at most 1 and every element is at least 1.

So the optimal shape is a "mountain" centered at index. The value decreases by 1 on each step away from the peak, down to a floor of 1. Any remaining positions beyond the slope just stay at 1.

For a given peak v, you can compute the sum of the left side and the right side using arithmetic series. If that minimum sum is <= maxSum, then v is achievable. If not, v is too large. This monotonic property is exactly what binary search needs.

The solution

def max_value(n, index, maxSum):
    def min_sum(v):
        left = index
        right = n - index - 1

        def side_sum(length, peak):
            if peak - 1 >= length:
                return length * peak - length * (length + 1) // 2
            else:
                full = peak - 1
                return full * peak - full * (full + 1) // 2 + (length - full)

        return v + side_sum(left, v) + side_sum(right, v)

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

The side_sum helper computes the minimum sum for one side of the mountain. If the peak is tall enough that the slope reaches 1 before running out of array positions, the remaining positions are all 1. Otherwise, the entire side is a decreasing arithmetic sequence from v-1 down to v-length.

Notice the binary search template here uses lo = mid (not lo = mid + 1) and hi = mid - 1. That is because we are maximizing: if the current value is feasible, it could be the answer or something larger could work. We compute mid = lo + (hi - lo + 1) // 2 (ceiling division) to avoid an infinite loop when lo + 1 == hi.

Visual walkthrough

Here is the binary search in action on a small example: n=4, index=2, maxSum=6.

Three iterations. The binary search narrows the range from [1, 6] down to the answer: 2. The array [1, 1, 2, 1] has sum 5, which is within the budget of 6, and no valid array can place a value larger than 2 at index 2.

Complexity analysis

Time: O(log(maxSum)). The binary search runs at most log2(maxSum) iterations. Each iteration computes min_sum in O(1) time using arithmetic formulas.

Space: O(1). Just a handful of variables. No arrays are actually constructed.

The building blocks

1. Binary search on the answer

You are not searching an array. You are searching the range [1, maxSum] for the largest value that satisfies a constraint. The feasibility function (min_sum(v) <= maxSum) is monotonic: if v works, every smaller value works too. If v fails, every larger value fails too. That monotonicity is all binary search needs.

2. Greedy minimum-sum construction

Given a fixed peak, the minimum-sum array is always the mountain shape. You do not need to try different arrangements. The greedy argument is clean: any element that could be smaller (while still respecting the adjacency constraint) should be smaller, because that minimizes the sum and gives you the most room to raise the peak.

The arithmetic series formula sum = n * first + n * (n-1) / 2 (or its rearrangement) lets you compute each side's contribution in O(1), avoiding an O(n) loop inside the binary search.

Edge cases

• index = 0 or index = n-1: The peak is at one end of the array. There is only one side to the mountain. The side_sum helper handles this naturally because one side has length 0.
• maxSum = n: Every element must be exactly 1. The answer is 1.
• n = 1: The entire budget goes to the single element. The answer is maxSum.
• Large maxSum with small n: The peak can be very tall. The arithmetic formula handles this without overflow concerns in Python (though in languages like C++ or Java, you would need long long).

From understanding to recall

The core idea is simple: binary search on the peak value, compute the minimum sum with arithmetic series, check against the budget. You probably follow it clearly right now.

But in an interview, the details matter. Is it lo = mid or lo = mid + 1? Do you use floor or ceiling for mid? How exactly does the arithmetic series formula work when the slope hits the floor of 1? These are the pieces that slip under pressure.

Spaced repetition locks them in. Write the solution from scratch today, again in two days, then in a week. After a few rounds, the side_sum helper and the ceiling-mid trick are automatic. You spend your interview time on communication, not re-derivation.

Related posts

• Koko Eating Bananas - The classic binary search on the answer problem, searching for the minimum valid speed
• Binary Search - The foundational binary search template that all these variants build on
• Find Peak Element - Binary search on a non-sorted array by following the slope

Binary search on the answer is one of those patterns that, once you see it, you see it everywhere. LeetCode 1802 is a great one to drill because the feasibility check adds a layer of arithmetic that makes the problem feel harder than it is. Nail the formula, and the rest is template.