Maximum frequency of an element after performing operations ii

Array Binary Search Sliding Window Sorting Prefix Sum

53.9% acceptance

Feb 23, 2026

300

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

impl Solution {
  pub fn max_frequency(nums: Vec<i32>, k: i32, num_operations: i32) -> i32 {
    // Same logic as version I but values can be up to 1e9.
    // The optimal target t is NOT necessarily in nums.
    // 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).
    // Candidates: all nums[i], nums[i]-k, nums[i]+k.
    
    let mut sorted = nums.clone();
    sorted.sort_unstable();
    
    let mut freq_map = std::collections::HashMap::new();
    for &x in &sorted { *freq_map.entry(x).or_insert(0i32) += 1; }
    
    // Collect candidate targets
    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_map.get(&t).unwrap_or(&0);
      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 contribution = fv + (range_count - fv).min(num_operations);
      best = best.max(contribution);
    }
    best
  }
}