# Maximum Product After K Increments
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-product-after-k-increments)
Canonical: https://scaleengineer.com/dsa/problems/maximum-product-after-k-increments
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
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 <= 105`
* `0 <= nums[i] <= 106`

# Approaches
## Brute-force Simulation
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.
**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.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient and will not pass for the given constraints due to its high time complexity.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Loop `k` times.
- Inside the loop, find the index of the minimum element in the `nums` array.
- 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 `long` variable `product` to 1.
- Iterate through the `nums` array, multiplying each element with `product` and taking the modulo `10^9 + 7` at each step.
- Return the final product.

## Greedy Approach with Min-Heap
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.
**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.
**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 `k` is very large, as it processes increments one by one.
### Explanation
The strategy remains the same: greedily increment the smallest element.
1. First, we build a min-heap from all the elements in the `nums` array. This allows us to retrieve the minimum element in O(log N) time.
2. We then loop `k` times. In each iteration, we:
   a. Extract the minimum element from the heap using `poll()`.
   b. Increment it by 1.
   c. Insert the incremented element back into the heap using `add()`.
3. After `k` increments, 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.

```java
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;
    }
}
```
### Algorithm
- Create a `PriorityQueue` (min-heap) and add all elements from `nums` into it.
- Loop `k` times.
- 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 `long` variable `product` to 1.
- While the `PriorityQueue` is not empty, `poll()` an element, multiply it with `product`, and take the modulo `10^9 + 7`.
- Return the final product.

## Optimized Greedy with Sorting and Batch Updates
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.
**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.
**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.
### Explanation
1. Sort the `nums` array. This brings all the smallest elements to the front.
2. We iterate through the sorted array, leveling up groups of smallest elements. For a prefix of `i` identical smallest numbers, we calculate the cost to raise them all to the value of the `(i+1)`-th element.
3. If we have enough `k` operations, we perform this batch update, decrement `k`, and effectively make the array sorted again with a larger group of smallest numbers. We continue this until we run out of `k` or all numbers become equal.
4. If we don't have enough `k` to level up to the next distinct value, we distribute the remaining `k` operations as evenly as possible among the current group of smallest elements.
5. After all `k` operations are accounted for, we compute the product modulo `10^9 + 7`.

```java
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;
    }
}
```
### Algorithm
- Sort the `nums` array.
- 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 of `i` smallest numbers to match the value of the `(i+1)`-th number.
- If `k >= cost`, 'pay' the cost by decrementing `k` and continue. The prefix of smallest numbers now grows.
- If `k < cost`, we don't have enough operations to level up. Distribute the remaining `k` as evenly as possible among the current prefix of smallest numbers. Each gets `k / i` increments, and the first `k % i` elements get one extra. After this, `k` is 0, and the process is done.
- If `k` is still positive after the loop (meaning all numbers became equal), distribute the remaining `k` evenly among all `N` numbers.
- Finally, calculate the product of the numbers in the modified `nums` array modulo `10^9 + 7`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @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;
  };

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```