< Back





2233. Maximum Product After K Increments

We're given a list of integers and asked to find the maximum product of the integers in the list
after incrementing any element in the list k times. Hints that allow us to determine this is a heap
oriented problem are:

  * The requirement to maximize across a list of elements
  * The list is unsorted
  * We have k operations to execute

We create a min heap from the input, and then execute the increment operation k times on the heap,
popping the minimum element, adding 1 to it, and pushing back onto the heap where it is immediately
sorted.

We're asked to return the answer, mod 10^9 + 7. To save time, we mod the running answer scalar
variable after every multiplication operation - thanks to the nature of modulus we'll still end up
with the same result, however, we'll avoid having to handle large integers (which is time
consuming).

The solution is as follows:


  from heapq import heappush, heappop

  class Solution:
      def maximumProduct(self, nums: List[int], k: int) -> int:
          n, mod, ans = len(nums), 10e8 + 7, 1
          heapify(nums)

          for _ in range(k):
              heappush(nums, heappop(nums) + 1)

          for num in nums:
              ans = (ans * num) % mod

          return int(ans)


_ Time Complexity:

  O(n + k) - The heapify() operation takes linear time. Pushing and popping from the heap takes O(1)
  time, which we execute k times. We operate over each number in the input when computing the
  product.

_ Space Complexity:

  O(n) - Our heap will be the same size as the input, n.