1802. Maximum Value at a Given Index in a Bounded Array (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def maxValue(self, n, index, maxSum):
        """
        :type n: int
        :type index: int
        :type maxSum: int
        :rtype: int
        """
        # binary search
        def getSum(val):
            l = max(0, val - index)
            r = max(0, val - (n - 1 - index))
            return (val + l) * (val - l + 1) // 2 + (val - 1 + r) * (val - r) // 2
        maxSum -= n
        l, r = 0, maxSum
        while l <= r:
            m = (l + r) // 2
            val = getSum(m)
            if val == maxSum:
                return m + 1
            elif val > maxSum:
                r = m - 1
            else:
                l = m + 1
        return l
        
        # my dumb math
        maxSum -= n
        layer = count = 1
        while maxSum > 0:
            if index + layer < n:
                count += 1
            if index - layer >= 0:
                count += 1
            if count == n:
                return layer + maxSum // n + (maxSum % n != 0)
            maxSum -= count
            layer += 1
        return layer