Maximum Value at a Given Index in a Bounded Array LeetCode solution in Python

1
class Solution:
2
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
3
        l = 1
4
        r = int(1e9)
5
        ans = 0
6

7
        while l <= r:
8
            mid = (l + r) // 2
9
            total = 0
10

11
            # add left numbers
12
            if mid >= index + 1:
13
                first = mid - index
14
                size = index + 1
15
                total += first * size + size * (size - 1) / 2
16
            else:
17
                total += mid * (mid + 1) / 2
18
                total += index + 1 - mid
19

20
            # add right numbers
21
            size = n - index
22
            if mid >= size:
23
                last = mid - (n - index - 1)
24
                total += last * size + size * (size - 1) / 2
25
            else:
26
                total += mid * (mid + 1) / 2
27
                total += size - mid
28

29
            # deduct mid because it was added twice
30
            total -= mid
31

32
            if total <= maxSum:
33
                ans = max(ans, mid)
34
                l = mid + 1
35
            else:
36
                r = mid - 1
37

38
        return ans