LeetCode 2233 Maximum Product After K Increments (Medium) : NileshBlog.Tech

LeetCode 2233 Maximum Product After K Increments: Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Maximum Product After K Increments” or “LeetCode 2233.” problem.

LeetCode-2233-Maximum-Product-After-K-Increments-animation

Table of Contents

Approach: LeetCode 2233 Maximum Product After K Increments Visualization LeetCode 2233 Priority Queue

In this Leetcode problem, we are tasked with finding the maximum product of an array after performing ‘K’ increments on its elements.

Key Steps:

We begin by implementing a priority queue (min-heap) to efficiently manage the array elements.

We iterate ‘K’ times, taking the smallest element from the heap, incrementing it by 1, and then pushing it back into the heap. This step ensures we increment ‘K’ times as required.
To avoid integer overflow, we use a modulo operation with ‘mod’ (set to 1000000007) after each multiplication in the final result.
After the ‘K’ increments, we compute the product of the elements remaining in the heap, ensuring it remains a maximum product.

We return the final product as the result.

C++ : Leet Code 2233 Priority Queue

class Solution {
public:
    int maximumProduct(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.end());
        int mod = 1000000007;
        while (k--) {
            int x = pq.top();
            pq.pop();
            x++;
            pq.push(x);
        }
        long long int ans = 1;
        while (!pq.empty()) {
            ans *= pq.top();
            ans %= mod;
            pq.pop();
        }
        return ans;
    }
};

Java: Leet Code 2233 Min Heap

import java.util.PriorityQueue;

class Solution {
    public int maximumProduct(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(nums.length);
        for (int num : nums) {
            pq.add(num);
        }
        int mod = 1000000007;
        while (k > 0) {
            int x = pq.poll();
            x++;
            pq.add(x);
            k--;
        }
        long ans = 1;
        while (!pq.isEmpty()) {
            ans = (ans * pq.poll()) % mod;
        }
        return (int) ans;
    }
}

Python: Leet Code 2233 Priority Queue

import heapq

class Solution:
    def maximumProduct(self, nums, k: int) -> int:
        
        # creating a heap
        heap = []
        for i in nums:
            heapq.heappush (heap,i)
            
        while k :
            current = heapq.heappop(heap)
            heapq.heappush(heap, current+1)
            k-=1
            
        result =1
        
        while len(heap)>0:
            x= heapq.heappop(heap)
            result =(result*x )% (10**9+7)
            
        return result

JavaScript: LeetCode 2233 Priority Queue

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumProduct = function(nums, k) {
let MOD = Math.pow(10, 9) + 7;
  
  // build a new minimum priority queue
  
  let queue = new MinPriorityQueue();
  for (let i = 0; i < nums.length; i++) {
    queue.enqueue(nums[i], nums[i]);
  }
  
  
  // To maximize the product, take the smallest element out
  // add 1 to it and add it back to the queue
  let count = 0;
  while (count < k && queue.size() > 0) {
    let {element, priority} = queue.dequeue();
    queue.enqueue(element + 1, priority + 1);
    count += 1;
  }
  
  
  // calculate the product
  let result = 1;
  let elements = queue.toArray().map((a) => a.element);
  for (let i = 0; i < elements.length; i++) {
    result = (result * elements[i]) % MOD;
  }
  
  return result;
};

Result Analysis:

By using a min-heap data structure to efficiently track and update the elements and applying the modulo operation for large numbers, we obtain the maximum product after ‘K’ increments. This code solves the Leetcode problem 2233, “Maximum Product After K Increments,” and provides an optimal solution.

List of Some important Leet code Questions: