Problem statement

https://binarysearch.com/problems/Largest-Kth-Value-of-List/

Solution

Variation of 1802. Maximum Value at a Given Index in a Bounded Array, but here we can have negative elements.

Complexity

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

Code

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

        beg, end = -10**9, 10**9
        while beg + 1 < end:
            mid = (beg + end) // 2
            if test(mid):
                beg = mid
            else:
                end = mid
        return beg