Problem statement

https://binarysearch.com/problems/Most-Occurring-Number-After-K-Increments/

Solution

The idea is to sort array, and then use sliding window approach to extend right end or shrink left. We extend until we can: that is last value in window multiplied by number of elements minus sum of values in window is <= k.

Complexity

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

Code

class Solution:
    def solve(self, A, k):
        A = sorted(A)
        n = len(A)
        beg, end, sm = 0, 0, A[0]
        ans = (0, 0)
        while end < n and beg < n:
            if end + 1 < n and A[end + 1]*(end - beg + 2) - (sm + A[end + 1]) <= k:
                end += 1
                sm += A[end]
                ans = max(ans, (end - beg + 1, -A[end]))
            else:
                sm -= A[beg]
                beg += 1

        return -ans[1]