Maximum Value at a Given Index in a Bounded Array

medium binary search math

Problem

Build an array of length n, positives, adjacent differ ≤1, total ≤ maxSum. Maximize arr[index].

Inputn = 4, index = 2, maxSum = 6

Output2

[1,1,2,1] sums to 5 ≤ 6; can't reach 3.

index

maxSum

def max_value(n, index, maxSum):
    def cost(side, peak):
        if peak > side:
            return (peak + (peak - side + 1)) * side // 2
        return (peak * (peak + 1)) // 2 + (side - peak)
    lo, hi = 1, maxSum
    while lo < hi:
        mid = (lo + hi + 1) // 2
        total = mid + cost(index, mid - 1) + cost(n - index - 1, mid - 1)
        if total <= maxSum:
            lo = mid
        else:
            hi = mid - 1
    return lo

function maxValue(n, index, maxSum) {
  function cost(side, peak) {
    if (peak > side) return ((peak + (peak - side + 1)) * side) / 2;
    return (peak * (peak + 1)) / 2 + (side - peak);
  }
  let lo = 1, hi = maxSum;
  while (lo < hi) {
    const mid = Math.floor((lo + hi + 1) / 2);
    const total = mid + cost(index, mid - 1) + cost(n - index - 1, mid - 1);
    if (total <= maxSum) lo = mid; else hi = mid - 1;
  }
  return lo;
}

class Solution {
    long cost(long side, long peak) {
        if (peak > side) return (peak + (peak - side + 1)) * side / 2;
        return peak * (peak + 1) / 2 + (side - peak);
    }
    public int maxValue(int n, int index, int maxSum) {
        long lo = 1, hi = maxSum;
        while (lo < hi) {
            long mid = (lo + hi + 1) / 2;
            long total = mid + cost(index, mid - 1) + cost(n - index - 1, mid - 1);
            if (total <= maxSum) lo = mid; else hi = mid - 1;
        }
        return (int) lo;
    }
}

long cost(long side, long peak) {
    if (peak > side) return (peak + (peak - side + 1)) * side / 2;
    return peak * (peak + 1) / 2 + (side - peak);
}
int maxValue(int n, int index, int maxSum) {
    long lo = 1, hi = maxSum;
    while (lo < hi) {
        long mid = (lo + hi + 1) / 2;
        long total = mid + cost(index, mid - 1) + cost(n - index - 1, mid - 1);
        if (total <= maxSum) lo = mid; else hi = mid - 1;
    }
    return (int) lo;
}

Explanation

To make arr[index] as large as possible while keeping the total <= maxSum, the best shape is a triangle peak: the value at index is highest, and it steps down by 1 on each side until it hits the floor of 1. We binary-search the peak value because a smaller peak always fits if a bigger one does.

For a candidate peak v, the helper cost(side, peak) computes the sum of one side. If the side is long enough that the values reach 1 before running out, it is a triangular number plus a flat tail of 1s. If the side is short, it is just a clipped arithmetic series. The total is the peak plus both sides, using peak - 1 as the neighbor value.

If total <= maxSum, the peak is affordable so we go higher (lo = mid); otherwise we lower it (hi = mid - 1). The mid = (lo + hi + 1) // 2 rounding biases upward so the loop ends on the largest feasible value.

Example: n = 4, index = 2, maxSum = 6. Peak 2 gives an array like [1,1,2,1] summing to 5, which fits. Peak 3 would need more than 6, so the answer is 2.

Because each cost is a closed-form formula, every check is O(1), and the whole search runs in O(log maxSum) time.

Time: O(log maxSum) Space: O(1)