Problem statement

https://binarysearch.com/problems/Maximize-the-Minimum-Value-After-K-Sublist-Increments/

Solution

The idea is to use binary search, where we ask question: check(x) is how many steps we need to make to make all numbers >= k. To answer this question, we need to first choose numbers we need to increase, then we need to use greedy strategy: start from the first element and subtract 1 as many times as we need. However if we do this, this will be too slow, so we will use difference trick here.

Complexity

It is O(n * log M), where M can be estimated as k * (len(nums)//size + 1) + min(nums) + 1

Code

class Solution:
    def solve(self, nums, size, k):
        def check(x):
            ans = 0
            arr = [max(x - i, 0) for i in nums]
            diff = [arr[0]] + [x - y for x, y in zip(arr[1:], arr)] + [0] * size
            for i in range(len(diff) - size): 
                if diff[i] < 0:
                    diff[i + 1] += diff[i]
                else:
                    diff[i + size] += diff[i]
                    ans += diff[i]
            return ans

        beg, end = -1, k * (len(nums)//size + 1) + min(nums) + 1
        while beg + 1 < end:
            mid = (beg + end)//2
            if check(mid) <= k:
                beg = mid
            else:
                end = mid

        return beg