Apply operations to maximize frequency score

Array Binary Search Sliding Window Sorting Prefix Sum

38.6% acceptance

Feb 25, 2026

294

You are given a 0-indexed integer array nums and an integer k. You can perform the following operation on the array at most k times: Choose any index i from the array and increase or decrease nums[i] by 1. The score of the final array is the frequency of the most frequent element in the array. Return the maximum score you can achieve.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_frequency_score(nums: Vec<i32>, k: i64) -> i32 {
    let mut sorted = nums.clone();
    sorted.sort_unstable();
    let n = sorted.len();
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + sorted[i] as i64;
    }

    let can_achieve = |w: usize| -> bool {
      for r in w - 1..n {
        let l = r + 1 - w;
        let mid = (l + r) / 2;
        let m = sorted[mid] as i64;
        // cost = m*(mid-l) - (prefix[mid]-prefix[l]) + (prefix[r+1]-prefix[mid+1]) - m*(r-mid)
        let left_cost = m * (mid - l) as i64 - (prefix[mid] - prefix[l]);
        let right_cost = (prefix[r + 1] - prefix[mid + 1]) - m * (r - mid) as i64;
        if left_cost + right_cost <= k {
          return true;
        }
      }
      false
    };

    let mut lo = 1usize;
    let mut hi = n;
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      if can_achieve(mid) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    lo as i32
  }
}