Maximum Value at Given Index — Binary Search on Peak Value

Problem 326 · Maximum Value at a Given Index in a Bounded Array

Difficulty: Medium · Pattern: BS on Answer

Maximize nums[index] given that all values >= 1, adjacent values differ by at most 1, and sum <= maxSum.

Intuition

For a peak value v at index, sum = arithmetic triangle on left + triangle on right. Use formula for triangle sum.

Solutions

# Python
def maxValue(n, index, maxSum):
    def triangle_sum(length, peak):
        if peak >= length:
            return (2*peak - length + 1) * length // 2
        else:
            # peak, peak-1, ..., 1, 1, 1, ...
            return peak*(peak+1)//2 + (length-peak)

    def feasible(v):
        left = triangle_sum(index+1, v)
        right = triangle_sum(n-index, v)
        return left + right - v <= maxSum  # -v because center counted twice

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

Complexity

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