You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.
Return the maximum product of nums after at most k operations. Since the answer may be very large, return it modulo 109 + 7. Note that you should maximize the product before taking the modulo.
Example 1:
Input: nums = [0,4], k = 5 Output: 20 Explanation: Increment the first number 5 times. Now nums = [5, 4], with a product of 5 * 4 = 20. It can be shown that 20 is maximum product possible, so we return 20. Note that there may be other ways to increment nums to have the maximum product.
Example 2:
Input: nums = [6,3,3,2], k = 2 Output: 216 Explanation: Increment the second number 1 time and increment the fourth number 1 time. Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216. It can be shown that 216 is maximum product possible, so we return 216. Note that there may be other ways to increment nums to have the maximum product.
Constraints:
1 <= nums.length, k <= 1050 <= nums[i] <= 106Problem Overview: You are given an integer array nums and an integer k. In one operation you can pick any element and increase it by 1. After performing exactly k operations, return the maximum possible product of the array elements (usually taken modulo 1e9+7). The challenge is deciding which element to increment at each step to maximize the final product.
Approach 1: Repeated Minimum Scan (Brute Force) (Time: O(n * k), Space: O(1))
The simplest strategy is to repeatedly increment the smallest element in the array. Increasing the smallest value gives the largest marginal improvement to the final product. For each of the k operations, scan the entire array to find the current minimum, increment it, and continue. After all operations, compute the product of the array. This approach demonstrates the greedy intuition but performs poorly because finding the minimum costs O(n) each time.
Approach 2: Greedy + Min-Heap (Priority Queue) (Time: O((n + k) log n), Space: O(n))
The optimal solution uses a min-heap (priority queue) to efficiently track the smallest element. Insert all elements into the heap. For each of the k operations, extract the minimum element, increment it by one, and push it back into the heap. This guarantees the smallest value is always increased first, which maximizes the overall product due to the multiplicative effect. Each heap push and pop takes O(log n), making the update phase O(k log n). Finally, multiply all heap elements together modulo 1e9+7.
This approach relies on a classic greedy observation: distributing increments toward smaller values balances the array and increases the product faster than boosting already large numbers. The heap ensures you always access the smallest element in O(log n) instead of scanning the entire array.
Recommended for interviews: The Greedy + Min-Heap approach is what interviewers expect. Start by explaining the intuition that increasing the smallest value improves the product the most. Mention the brute-force scan to show understanding, then optimize it using a priority queue. That transition demonstrates both problem-solving intuition and knowledge of efficient data structures.
According to the problem description, to maximize the product, we need to increase the smaller numbers as much as possible. Therefore, we can use a min-heap to maintain the array nums. Each time, we take the smallest number from the min-heap, increase it by 1, and then put it back into the min-heap. After repeating this process k times, we multiply all the numbers currently in the min-heap to get the answer.
The time complexity is O(k times log n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeated Minimum Scan (Brute Force) | O(n * k) | O(1) | Good for understanding the greedy idea or when k is very small |
| Greedy + Min-Heap (Priority Queue) | O((n + k) log n) | O(n) | General optimal solution when repeated minimum updates are required |
Maximum Product After K Increments (LeetCode 2233) | Full solution with mathematical proof | Greedy • Nikhil Lohia • 2,266 views views
Watch 9 more video solutions →Practice Maximum Product After K Increments with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor