Maximum product after k increments

November 19, 2022


Problem URL: Maximum product after k increments

We will use a heap to keep track of the minimum element in the array. Then we will iterate k times and we will pop the minimum element from the heap and add 1 to it. We will push the new element back to the heap. We will continue this process until we reach the end of the array.

class Solution:
    def maxProductAfterKIncrements(self, nums: List[int], k: int) -> int:
        for _ in range(k):
            heapq.heappush(nums, heapq.heappop(nums)+1)

        res = 1
        for num in heap:
            res *= num
        return res % (10**9+7)

Time complexity: O(klog(n))
Space complexity: O(n)