Maximum Product After K Increments
MedPrompt
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] <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
The brute-force approach is slow because it repeatedly scans the entire array to find the minimum element. We can optimize this process by using a data structure that provides fast access to the minimum element. A min-heap (implemented as a PriorityQueue in Java) is perfect for this task.
Algorithm
- Create a
PriorityQueue(min-heap) and add all elements fromnumsinto it. - Loop
ktimes. - In each iteration, extract the smallest element using
poll(). - Increment the extracted element by 1.
- Add the new value back to the
PriorityQueue. - After the loop, initialize a
longvariableproductto 1. - While the
PriorityQueueis not empty,poll()an element, multiply it withproduct, and take the modulo10^9 + 7. - Return the final product.
Walkthrough
The strategy remains the same: greedily increment the smallest element.
- First, we build a min-heap from all the elements in the
numsarray. This allows us to retrieve the minimum element in O(log N) time. - We then loop
ktimes. In each iteration, we: a. Extract the minimum element from the heap usingpoll(). b. Increment it by 1. c. Insert the incremented element back into the heap usingadd(). - After
kincrements, the heap contains the final set of numbers. We then calculate their product. We can do this by repeatedly polling from the heap until it's empty, multiplying the elements, and taking the modulo at each step.
import java.util.PriorityQueue; class Solution { public int maximumProduct(int[] nums, int k) { int MOD = 1_000_000_007; PriorityQueue<Long> pq = new PriorityQueue<>(); for (int num : nums) { pq.add((long)num); } for (int i = 0; i < k; i++) { long smallest = pq.poll(); pq.add(smallest + 1); } long product = 1; while (!pq.isEmpty()) { product = (product * pq.poll()) % MOD; } return (int) product; }}Complexity
Time
O((N+k) log N). Building the heap from N elements takes O(N log N) time. Then, we perform `k` operations, each involving a `poll` and an `add`, both of which take O(log N) time. This part is O(k log N). The final product calculation involves polling N elements, taking O(N log N). The total complexity is dominated by these operations.
Space
O(N), as the `PriorityQueue` needs to store all N elements from the input array.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Guaranteed to pass within the time limits for the given constraints.
Relatively easy to implement correctly.
Cons
Uses extra space to store the heap.
Can be further optimized if
kis very large, as it processes increments one by one.
The most straightforward approach is to simulate the process directly. The core idea is that to maximize the product, we should always increment the smallest element in the array. This is because for any two numbers a and b where a < b, incrementing a yields a product of (a+1)*b = ab + b, while incrementing b yields a*(b+1) = ab + a. Since b > a, incrementing the smaller number a results in a larger overall product. This greedy strategy is optimal.
Algorithm
- Loop
ktimes. - Inside the loop, find the index of the minimum element in the
numsarray. - If there are multiple minimum elements, any one can be chosen.
- Increment the element at the found index by 1.
- After the loop finishes, calculate the product of all elements in
nums. - Initialize a
longvariableproductto 1. - Iterate through the
numsarray, multiplying each element withproductand taking the modulo10^9 + 7at each step. - Return the final product.
Walkthrough
We repeat the increment operation k times. In each iteration, we find the minimum element in the array and increment it by one. After k iterations, we compute the product of all elements in the modified array. Since the product can be very large, we take the modulo 10^9 + 7 at each multiplication step to prevent overflow.
class Solution { public int maximumProduct(int[] nums, int k) { int MOD = 1_000_000_007; for (int i = 0; i < k; i++) { int minIndex = -1; int minVal = Integer.MAX_VALUE; for (int j = 0; j < nums.length; j++) { if (nums[j] < minVal) { minVal = nums[j]; minIndex = j; } } nums[minIndex]++; } long product = 1; for (int num : nums) { product = (product * num) % MOD; } return (int) product; }}Complexity
Time
O(k * N), where N is the number of elements in `nums`. In each of the `k` operations, we iterate through the entire array of size N to find the minimum element. This leads to a total time complexity of O(k * N). Given the constraints (k, N up to 10^5), this will be too slow and result in a Time Limit Exceeded error.
Space
O(1), as we are modifying the input array in-place and using only a few extra variables.
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient and will not pass for the given constraints due to its high time complexity.
This approach builds upon the same greedy principle of incrementing the smallest numbers but optimizes the process by performing increments in batches. Instead of incrementing one by one using a heap, we sort the array and calculate how many operations it would take to make a group of the smallest elements equal to the next smallest value. This allows us to use multiple k operations in a single step, which is much faster, especially when k is large.
Algorithm
- Sort the
numsarray. - Iterate through the sorted array from left to right, keeping track of the prefix of smallest, equal-valued numbers.
- In each step, calculate the
cost(number of operations) to increment the current prefix ofismallest numbers to match the value of the(i+1)-th number. - If
k >= cost, 'pay' the cost by decrementingkand continue. The prefix of smallest numbers now grows. - If
k < cost, we don't have enough operations to level up. Distribute the remainingkas evenly as possible among the current prefix of smallest numbers. Each getsk / iincrements, and the firstk % ielements get one extra. After this,kis 0, and the process is done. - If
kis still positive after the loop (meaning all numbers became equal), distribute the remainingkevenly among allNnumbers. - Finally, calculate the product of the numbers in the modified
numsarray modulo10^9 + 7.
Walkthrough
- Sort the
numsarray. This brings all the smallest elements to the front. - We iterate through the sorted array, leveling up groups of smallest elements. For a prefix of
iidentical smallest numbers, we calculate the cost to raise them all to the value of the(i+1)-th element. - If we have enough
koperations, we perform this batch update, decrementk, and effectively make the array sorted again with a larger group of smallest numbers. We continue this until we run out ofkor all numbers become equal. - If we don't have enough
kto level up to the next distinct value, we distribute the remainingkoperations as evenly as possible among the current group of smallest elements. - After all
koperations are accounted for, we compute the product modulo10^9 + 7.
import java.util.Arrays; class Solution { public int maximumProduct(int[] nums, int k) { int n = nums.length; int MOD = 1_000_000_007; if (n == 1) { return (nums[0] + k); } Arrays.sort(nums); long currentK = k; int i = 0; while (currentK > 0 && i < n - 1) { if (nums[i] < nums[i+1]) { long diff = nums[i+1] - nums[i]; long ops_needed = diff * (i + 1); if (currentK >= ops_needed) { currentK -= ops_needed; for (int j = 0; j <= i; j++) { nums[j] = nums[i+1]; } } else { long base_add = currentK / (i + 1); long extra = currentK % (i + 1); for (int j = 0; j <= i; j++) { nums[j] += base_add; } for (int j = 0; j < extra; j++) { nums[j]++; } currentK = 0; } } i++; } if (currentK > 0) { long base_add = currentK / n; long extra = currentK % n; for (int j = 0; j < n; j++) { nums[j] += base_add; } for (int j = 0; j < extra; j++) { nums[j]++; } } long product = 1; for (int num : nums) { product = (product * num) % MOD; } return (int) product; }}Complexity
Time
O(N log N). Sorting the array takes O(N log N). The subsequent loop to distribute `k` runs at most N times, making it O(N). Thus, the dominant factor is sorting.
Space
O(log N) or O(N), depending on the space complexity of the sorting algorithm used. If sorting is done in-place, it's O(log N) for recursion stack space.
Trade-offs
Pros
The most time-efficient solution, especially for large
k.Uses constant extra space (if sorting is done in-place).
Cons
The implementation is more complex and requires careful handling of indices and updates compared to the min-heap approach.
Solutions
Solution
class Solution {private static final int MOD = (int)1 e9 + 7;public int maximumProduct(int[] nums, int k) { PriorityQueue<Integer> q = new PriorityQueue<>(); for (int v : nums) { q.offer(v); } while (k-- > 0) { q.offer(q.poll() + 1); } long ans = 1; while (!q.isEmpty()) { ans = (ans * q.poll()) % MOD; } return (int)ans; }}/** * @param {number[]} nums * @param {number} k * @return {number} */ var maximumProduct = function (nums, k) { const n = nums.length; let pq = new MinPriorityQueue(); for (let i = 0; i < n; i++) { pq.enqueue(nums[i]); } for (let i = 0; i < k; i++) { pq.enqueue(pq.dequeue().element + 1); } let ans = 1; const limit = 10 ** 9 + 7; for (let i = 0; i < n; i++) { ans = (ans * pq.dequeue().element) % limit; } return ans; };class Solution {public: int maximumProduct(vector<int> &nums, int k) { int mod = 1e9 + 7; make_heap(nums.begin(), nums.end(), greater<int>()); while (k--) { pop_heap(nums.begin(), nums.end(), greater<int>()); ++nums.back(); push_heap(nums.begin(), nums.end(), greater<int>()); } long long ans = 1; for (int v : nums) ans = (ans * v) % mod; return ans; }};class Solution: def maximumProduct(self, nums: List[int], k: int) -> int: heapify(nums) for _ in range(k): heappush(nums, heappop(nums) + 1) ans = 1 mod = 10 ** 9 + 7 for v in nums: ans = (ans * v) % mod return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.