Maximum Frequency of an Element After Performing Operations II

hard binary search sliding window sorting

Problem

You are given an array nums and integers k and numOperations. You perform exactly numOperations operations; each picks a fresh index i (never reused) and adds any integer in [−k, k] to nums[i]. Return the maximum possible frequency of any single value after the operations.

The key insight: for a target value t, any element whose value lies in [t−k, t+k] can be moved onto t with one operation, while elements already equal to t cost nothing. So the best frequency at t is eq + min(numOperations, inRange − eq), where eq counts values equal to t and inRange counts values in the window. Checking targets nums[i]−k, nums[i], nums[i]+k suffices.

Inputnums = [1,4,5], k = 1, numOperations = 2

Output2

Target t = 4: window [3,5] holds 4 and 5. Add 0 to nums[1] (stays 4), add −1 to nums[2] (5→4). Two elements equal 4.

nums (comma-separated)

numOperations

from bisect import bisect_left, bisect_right
def maxFrequency(nums, k, numOperations):
    nums.sort()                              # binary search needs sorted order
    count = {}
    for x in nums:                           # tally each value's frequency
        count[x] = count.get(x, 0) + 1
    candidates = set()
    for x in nums:                           # best targets: x-k, x, x+k
        candidates.add(x - k)
        candidates.add(x)
        candidates.add(x + k)
    ans = 0
    for t in candidates:                     # try each candidate target t
        lo = bisect_left(nums, t - k)        # first value >= t-k
        hi = bisect_right(nums, t + k)       # first value > t+k
        in_range = hi - lo                   # elements reachable to t
        eq = count.get(t, 0)                 # already equal to t (free)
        movable = min(numOperations, in_range - eq)
        ans = max(ans, eq + movable)
    return ans

function maxFrequency(nums, k, numOperations) {
  nums.sort((a, b) => a - b);              // binary search needs sorted order
  const count = new Map();
  for (const x of nums)                     // tally each value's frequency
    count.set(x, (count.get(x) || 0) + 1);
  const candidates = new Set();
  for (const x of nums) {                   // best targets: x-k, x, x+k
    candidates.add(x - k);
    candidates.add(x);
    candidates.add(x + k);
  }
  let ans = 0;
  for (const t of candidates) {             // try each candidate target t
    const lo = lowerBound(nums, t - k);     // first value >= t-k
    const hi = upperBound(nums, t + k);     // first value > t+k
    const inRange = hi - lo;                // elements reachable to t
    const eq = count.get(t) || 0;           // already equal to t (free)
    const movable = Math.min(numOperations, inRange - eq);
    ans = Math.max(ans, eq + movable);
  }
  return ans;
}

int maxFrequency(int[] nums, int k, int numOperations) {
    Arrays.sort(nums);                       // binary search needs sorted order
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums)                       // tally each value's frequency
        count.merge(x, 1, Integer::sum);
    Set<Long> cands = new HashSet<>();
    for (int x : nums) {                     // best targets: x-k, x, x+k
        cands.add((long) x - k);
        cands.add((long) x);
        cands.add((long) x + k);
    }
    int ans = 0;
    for (long t : cands) {                   // try each candidate target t
        int lo = lowerBound(nums, t - k);    // first value >= t-k
        int hi = upperBound(nums, t + k);    // first value > t+k
        int inRange = hi - lo;               // elements reachable to t
        int eq = count.getOrDefault((int) t, 0);
        int movable = Math.min(numOperations, inRange - eq);
        ans = Math.max(ans, eq + movable);
    }
    return ans;
}

int maxFrequency(vector<int>& nums, int k, int numOperations) {
    sort(nums.begin(), nums.end());          // binary search needs sorted order
    unordered_map<long long, int> count;
    for (int x : nums) count[x]++;           // tally each value's frequency
    set<long long> cands;
    for (int x : nums) {                      // best targets: x-k, x, x+k
        cands.insert((long long) x - k);
        cands.insert((long long) x);
        cands.insert((long long) x + k);
    }
    int ans = 0;
    for (long long t : cands) {               // try each candidate target t
        int lo = lower_bound(nums.begin(), nums.end(), t - k) - nums.begin();
        int hi = upper_bound(nums.begin(), nums.end(), t + k) - nums.begin();
        int inRange = hi - lo;                // elements reachable to t
        int eq = count.count(t) ? count[t] : 0;
        int movable = min(numOperations, inRange - eq);
        ans = max(ans, eq + movable);
    }
    return ans;
}

Explanation

Each operation can nudge one element by at most k in either direction. So an element with value v can be turned into any target t as long as |v − t| ≤ k, i.e. v lies in the window [t−k, t+k]. The whole problem reduces to: for each candidate target t, how many elements can end up equal to t?

Elements already equal to t are free — we never have to touch them. Every other element inside the window needs exactly one operation to be pulled onto t, and we only have numOperations of them. So the frequency we can build at t is eq + min(numOperations, inRange − eq), where eq is the count already equal to t and inRange is the count of values in [t−k, t+k].

We sort nums so the window is a contiguous slice. Then bisect_left(nums, t−k) finds the first index with value ≥ t−k and bisect_right(nums, t+k) finds the first index past t+k; their difference is inRange in O(log n).

Which targets are worth checking? The hint says only nums[i]−k, nums[i], and nums[i]+k. Any optimal window can be slid until one boundary touches an element, and the best target lands on one of those 3n values — so we test that small candidate set instead of every integer (the "II" version allows k up to 10⁹, so we cannot bucket-count).

Example: nums = [1,4,5], k = 1, numOperations = 2. Target t = 4: window [3,5] contains 4 and 5, so inRange = 2, eq = 1. We can move min(2, 2−1) = 1 element (the 5→4), giving frequency 1 + 1 = 2.

Time: O(n log n) Space: O(n)