LeetCode 2233: Maximum Product After K Increments

Explanation:

To maximize the product of the array after performing at most k increments, we should focus on incrementing the smallest elements first. If we sort the array in ascending order, we can start by incrementing the smallest element until it reaches the value of the next smallest element, and so on. This way, we ensure that the product is maximized.

We can achieve this by using a priority queue (min-heap) to keep track of the elements in the array. We pop the smallest element from the priority queue, increment it, and then push it back into the priority queue. We repeat this process for k iterations to maximize the product.

The time complexity of this approach is O(klogn) where n is the number of elements in the array and the space complexity is O(n) for the priority queue.

:

import java.util.PriorityQueue;

class Solution {
    public int maxProduct(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) {
            pq.offer(num);
        }
        
        int MOD = 1000000007;
        
        while (k > 0) {
            int curr = pq.poll();
            pq.offer(curr + 1);
            k--;
        }
        
        long result = 1;
        for (int num : pq) {
            result = (result * num) % MOD;
        }
        
        return (int) result;
    }
}