Problem statement

https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/

Solution

The idea is to use binary search where test(a) is answer for the question if we can build array such that nums[index] = a. How we are going to check if we can construct is to use greedy strategy: go to the left with values a-1, a-2, ... and then go to the right with the same values. We can have two cases for each of the sides: if we reach 0 or we our of indexes. Also by problem definition elements should be >=1, so it is easier to subtract 1 from all element in the beginning.

Complexity

It is O(log n) for time and O(1) for space.

Code

class Solution:
    def maxValue(self, n, index, maxSum):
        def test(a):
            b = max(a - index, 0)
            res = (a + b) * (a - b + 1) // 2
            b = max(a - ((n - 1) - index), 0)
            res += (a + b) * (a - b + 1) // 2
            return res - a <= maxSum

        maxSum -= n
        beg, end = 0, maxSum + 1
        while beg + 1 < end:
            mid = (beg + end) // 2
            if test(mid):
                beg = mid
            else:
                end = mid
        return end