Maximum Value at Given Index — Binary Search on Peak Guide

Problem Statement#

You are given three integers n, index, and maxSum. Build an array nums of length n such that every element is at least 1, the absolute difference between adjacent elements is at most 1, and the sum is at most maxSum. Return the maximum possible value of nums[index].

Constraints:

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

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

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

Why This Problem Matters#

LeetCode 1802 is a popular medium binary search interview problem at Amazon and Google. It pairs the search-on-answer template with a small piece of arithmetic series math. Many candidates can identify the binary search but fail to derive the closed-form sum quickly under pressure — that is what the interviewer is probing.

The "peak with slope-1 sides" structure appears in capacity planning, monotone hill problems, and some dp-on-sequences. Recognizing the shape and using triangular numbers to compute the minimal sum for a peak is a transferable trick.

The Core Insight#

For a peak of height v at index, the cheapest valid array slopes down by 1 on each side until it hits 1, then flattens. The sum of one side is the sum of the arithmetic sequence v, v-1, ..., 1 if the side is long enough, otherwise v, v-1, ..., v-(L-1). Binary search the largest v whose total sum is at most maxSum.

Use closed-form arithmetic so the predicate is O(1).

Visual Dry Run#

n = 4, index = 2, maxSum = 6. Left side length = index + 1 = 3, right side length = n - index = 2.

Answer: 2.

Solution (Optimal)#

class Solution:
    def maxValue(self, n, index, maxSum):
        def side_sum(length, peak):
            if peak >= length:
                # peak, peak-1, ..., peak-length+1
                return (peak + (peak - length + 1)) * length // 2
            # peak, peak-1, ..., 1, then 1's fill the rest
            triangle = peak * (peak + 1) // 2
            flat = length - peak
            return triangle + flat
 
        def feasible(v):
            left = side_sum(index + 1, v)
            right = side_sum(n - index, v)
            return left + right - v <= maxSum
 
        lo, hi = 1, maxSum
        while lo < hi:
            mid = lo + (hi - lo + 1) // 2
            if feasible(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

var maxValue = function(n, index, maxSum) {
    const sideSum = (length, peak) => {
        if (peak >= length) {
            const last = peak - length + 1;
            return BigInt(peak + last) * BigInt(length) / 2n;
        }
        const triangle = BigInt(peak) * BigInt(peak + 1) / 2n;
        const flat = BigInt(length - peak);
        return triangle + flat;
    };
 
    const feasible = (v) => {
        const left = sideSum(index + 1, v);
        const right = sideSum(n - index, v);
        return left + right - BigInt(v) <= BigInt(maxSum);
    };
 
    let lo = 1, hi = maxSum;
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo + 1) / 2);
        if (feasible(mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
};

Time: O(log maxSum) — predicate is O(1). Space: O(1).

Common Mistakes#

• Forgetting the -v correction when adding both sides (peak counted twice).
• Computing the slope side as v + (v-1) + ... + 0 instead of stopping at 1.
• Using lower-mid in the maximize variant and infinite-looping.
• Overflowing 32-bit integers when maxSum and peak reach 10^9.
• Looping linearly over v and timing out.

Interview Tips#

• Draw the peak shape on the whiteboard — interviewers love this.
• State the closed-form formula before coding.
• Mention overflow and switch to 64-bit / BigInt explicitly.

Follow-up Questions#

• What if adjacent differences could be at most d instead of 1? Side sum scales with d.
• What if minimum value were 0? Triangle goes to 0, change the cutoff.
• Multiple fixed indices each with their own minimum heights? Multi-constraint LP-flavored.
• Replace integer constraint with reals — does the binary search still terminate? Use tolerance.
• 2D version on a grid? Becomes a contour problem; harder to close-form.

Key Takeaways#

• LC 1802 is a classic maximize search-on-answer with arithmetic-series predicate.
• Subtract the peak once when summing both sides — it is shared.
• Use upper-mid lo + (hi - lo + 1) // 2 to avoid infinite loops.
• Time is O(log maxSum) thanks to a closed-form predicate.
• 64-bit arithmetic or BigInt is required for maxSum = 10^9.
• The peak-with-slope shape recurs in scheduling and capacity problems.
• Master this template before tackling LC 410 Split Array Largest Sum.