Skip to main content
Talentd

Maximum Product After K Increments - Solution & Explanation

MediumArrayGreedyHeap (Priority Queue)8 min readAsked at: Infosys, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

Maximum Product After K Increments (LeetCode 2233) | Full solution with mathematical proof | Greedy • Nikhil Lohia • 2,412 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Product After K Increments easy or hard?
Maximum Product After K Increments is typically rated Medium difficulty. The greedy idea—increment the smallest value—is straightforward, but recognizing the need for a min-heap to avoid O(n * k) scanning is the key step that elevates the problem.
Maximum Product After K Increments Python/Java solution
Most implementations push all numbers into a min-heap, repeat k times: pop the smallest value, increment it, and push it back. After all operations, multiply all numbers modulo 1e9+7. The same logic works across Python (heapq), Java (PriorityQueue), C++ (priority_queue with greater), Go, TypeScript, and JavaScript.
How to solve Maximum Product After K Increments in O(n)?
An exact O(n) solution is generally not feasible because you must repeatedly update and retrieve the smallest element during k operations. Maintaining that order efficiently requires a data structure such as a min-heap, which introduces a log n factor. The practical optimal solution is O((n + k) log n).
What is the best approach for Maximum Product After K Increments?
The best approach is Greedy with a Min-Heap (Priority Queue). Always increment the smallest element because increasing smaller values produces a larger multiplicative gain in the final product. Using a heap allows retrieving and updating the smallest element in O(log n), leading to overall time complexity of O((n + k) log n).
Is Maximum Product After K Increments asked at Google/Amazon/Meta?
Greedy optimization problems combined with heaps appear frequently in interviews at companies like Google, Amazon, and Meta. This specific pattern—repeatedly modifying the smallest element using a priority queue—is a common interview theme.
What data structure is used in Maximum Product After K Increments?
A min-heap (priority queue) is the key data structure. It allows efficient access to the smallest element in O(1) time and supports insertion and removal in O(log n), which is essential when performing k incremental updates.
What is the time complexity of Maximum Product After K Increments?
The optimal heap-based solution runs in O((n + k) log n) time. Building the min-heap takes O(n), and each of the k operations performs one pop and one push, each costing O(log n). Space complexity is O(n) for storing the heap.

Ready to solve this problem?

Practice Maximum Product After K Increments with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Increment to Make Array Unique

Next

Minimum Operations to Make the Array Increasing