Maximum frequency of an element after performing operations i

Array Binary Search Sliding Window Sorting Prefix Sum

40.1% acceptance

Feb 23, 2026

614

105

You are given an integer array nums and two integers k and numOperations. You must perform an operation numOperations times on nums, where in each operation you: Select an index i that was not selected in any previous operations. Add an integer in the range [-k, k] to nums[i]. Return the maximum possible frequency of any element in nums after performing the operations.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeMap;

impl Solution {
  pub fn max_frequency(nums: Vec<i32>, k: i32, num_operations: i32) -> i32 {
    // For a target value t, the maximum frequency achievable is:
    //   freq[t] + min(numOperations, count[t-k..t+k] - freq[t])
    // where count[t-k..t+k] = elements in nums that lie in [t-k, t+k].
    //
    // The optimal target t is NOT necessarily in nums; it can be any integer.
    // Element x contributes to window of t when x-k <= t <= x+k.
    // Count changes at t = x-k (enters) and t = x+k+1 (exits).
    // So candidates: all nums[i], nums[i]-k, and nums[i]+k.
    
    let mut freq: BTreeMap<i32, i32> = BTreeMap::new();
    for &x in &nums { *freq.entry(x).or_insert(0) += 1; }
    
    let mut sorted = nums.clone();
    sorted.sort_unstable();
    
    // Collect candidate targets: nums[i], nums[i]-k, nums[i]+k
    let mut candidates: Vec<i32> = Vec::new();
    for &x in &sorted {
      candidates.push(x);
      candidates.push(x - k);
      candidates.push(x + k);
    }
    candidates.sort_unstable();
    candidates.dedup();
    
    let mut best = 0;
    for &t in &candidates {
      let fv = *freq.get(&t).unwrap_or(&0);
      // Count elements in [t-k, t+k]
      let lo = sorted.partition_point(|&x| x < t - k);
      let hi = sorted.partition_point(|&x| x <= t + k);
      let range_count = (hi - lo) as i32;
      let ops_needed = range_count - fv;
      let contribution = fv + ops_needed.min(num_operations);
      best = best.max(contribution);
    }
    best
  }
}