Maximum product after k increments

Array Greedy Heap (Priority Queue)

43.2% acceptance

Feb 25, 2026

790

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;


impl Solution {
  pub fn maximum_product(nums: Vec<i32>, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let mut heap: BinaryHeap<Reverse<i64>> = nums.iter().map(|&x| Reverse(x as i64)).collect();
    for _ in 0..k {
      let Reverse(top) = heap.pop().unwrap();
      heap.push(Reverse(top + 1));
    }
    let mut product = 1i64;
    for Reverse(x) in heap {
      product = product * x % MOD;
    }
    product as i32
  }
}