MediumNo. 2233
Maximum Product After K Increments — LeetCode 2233 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Array, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
The 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.
Example
- Input
- nums = [0,4], k = 5
- Output
- 20
- Explanation
- Increment the first number 5 times.
Python solution
class Solution:
def maximumProduct(self, nums: List[int], k: int) -> int:
heapify(nums)
for _ in range(k):
heapreplace(nums, nums[0] + 1)
mod = 10**9 + 7
return reduce(lambda x, y: x * y % mod, nums)Complexity
- Time
- O(k × log n)
- Space · auxiliary
- O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2233. Maximum Product After K Increments is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0502 | IPO | Hard |
| 0630 | Course Schedule III | Hard |
| 0857 | Minimum Cost to Hire K Workers | Hard |
| 1353 | Maximum Number of Events That Can Be Attended | Medium |
| 1383 | Maximum Performance of a Team | Hard |
| 1642 | Furthest Building You Can Reach | Medium |
Frequently asked questions
- How hard is LeetCode 2233. Maximum Product After K Increments?
LeetCode 2233. Maximum Product After K Increments is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2233. Maximum Product After K Increments?
The Python solution on this page runs in O(k × log n).
- What is the space complexity of LeetCode 2233. Maximum Product After K Increments?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2233. Maximum Product After K Increments cover?
LeetCode 2233. Maximum Product After K Increments is tagged Greedy, Array and Heap (Priority Queue) on LeetCode.