1802. Maximum Value at a Given Index in a Bounded Array

intuition: convert the original problem to determining if you could generate a valid array with nums[index] == target
- the max sum we can get from forming an array where nums[index] == target is n * target
- the min sum we can get from forming an array where nums[index] == target is
  - nums[index-1] == target - 1 and nums[index+1] == target - 1
  - nums[index-2] == target - 2 and nums[index+2] == target - 2
  - ...

Then we need to compare index and target to determine the sum of subarray[0 ... index] and [index .. n-1]. In other words, to determine if the subarray is arithmetic sequence.

One smart idea is first do maxSum -= n. This way, we can form the algorithm in getMin(k) without having extensive comparison between k and index. But note that when returning result, we need to return low+1 or high+1 rather than low or high

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        def getMin(k):
            leftBound = max(k-index, 0)
            leftSum = (k+leftBound) * (k-leftBound+1) // 2
            rightBound = max(k-(n-1-index), 0)
            rightSum = (k+rightBound) * (k-rightBound+1) // 2
            return leftSum + rightSum - k
        
        maxSum -= n
        low, high = 0, maxSum
        while low + 1 < high:
            mid = low + (high - low) // 2
            if getMin(mid) <= maxSum:
                low = mid
            else:
                high = mid
        
        if getMin(high) <= maxSum:
            return high + 1
        return low + 1

1802. Maximum Value at a Given Index in a Bounded Array - cocoder39/coco39_LC GitHub Wiki