Maximum product after k increments
November 19, 2022
heapProblem 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:
heapq.heapify(nums)
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)