LeetCode Challenge Day 36 — 3346.Max Frequency After Operations

Hey folks

This is Day 36 of my LeetCode streak 🚀.
Today’s problem is Max Frequency After Operations — a medium difference array + greedy problem where each number can be shifted within a range [num - k, num + k], and we want to maximize how many elements can be made equal after at most numOperations.

📌 Problem Statement

You are given an array nums, an integer k, and another integer numOperations.

• Each element v in nums can be converted into any integer within [v - k, v + k].
• You are allowed to use at most numOperations conversions.
• Return the maximum possible frequency of any number you can achieve.

💡 Intuition

Every number contributes to an interval of possible target values.
If we know, for each integer x, how many numbers can be converted to x, we can compute:

• How many are already equal to x.
• How many can potentially be converted to x.

By using at most numOperations of these conversions, we maximize the frequency at that point.

🔑 Approach

1. Build a frequency map of numbers.

   • If numOperations = 0, the answer is just the maximum frequency.

2. Compute global bounds:

   • lo = min(nums) - k
   • hi = max(nums) + k

3. Use a difference array to record coverage:

   • For each number v, mark that it covers the interval [v - k, v + k].
   • Apply prefix sums to build array C, where C[i] = how many numbers can reach lo + i.

4. For each candidate x = lo + idx:

   • equal = freq.get(x) || 0
   • coverNonEqual = C[idx] - equal
   • Candidate frequency = equal + min(numOperations, coverNonEqual)

5. Track the maximum candidate.

⏱️ Complexity Analysis

• Time complexity:

  • Frequency building: O(n)
  • Difference array construction & prefix sums: O(range)
  • Iteration: O(range)
  • Overall: O(n + range), where range = max(nums) - min(nums) + 2k.

• Space complexity:

  • Difference array + prefix array: O(range).

🧑‍💻 Code (JavaScript)

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} numOperations
 * @return {number}
 */
var maxFrequency = function(nums, k, numOperations) {
  const n = nums.length;
  if (n === 0) return 0;

  const freq = new Map();
  for (const v of nums) freq.set(v, (freq.get(v) || 0) + 1);

  if (numOperations === 0) {
    let best = 0;
    for (const c of freq.values()) best = Math.max(best, c);
    return best;
  }

  let minVal = Infinity, maxVal = -Infinity;
  for (const v of nums) {
    if (v < minVal) minVal = v;
    if (v > maxVal) maxVal = v;
  }
  const lo = minVal - k;
  const hi = maxVal + k;
  const size = (hi - lo + 3) | 0;

  const diff = new Int32Array(size);
  for (const v of nums) {
    const L = v - k - lo;
    const R = v + k - lo;
    diff[L] += 1;
    diff[R + 1] -= 1;
  }

  const lenC = hi - lo + 1;
  const C = new Int32Array(lenC);
  let run = 0;
  for (let i = 0; i < lenC; i++) {
    run += diff[i];
    C[i] = run;
  }

  let ans = 0;
  for (let idx = 0; idx < lenC; idx++) {
    const x = lo + idx;
    const equal = freq.get(x) || 0;
    let coverNonEqual = C[idx] - equal;
    if (coverNonEqual < 0) coverNonEqual = 0;

    const cand = equal + Math.min(numOperations, coverNonEqual);
    if (cand > ans) ans = cand;
    if (ans === n) return n;
  }

  return ans;
};

// Example runs:
console.log(maxFrequency([1,4,5], 1, 2));   // 2
console.log(maxFrequency([5,11,20,20], 5, 1)); // 2

🧪 Example Walkthrough

Input: nums = [1,4,5], k = 1, numOperations = 2

Intervals:

1 → [0,2]

4 → [3,5]

5 → [4,6]

Candidate = 4:

equal = 1 (the 4)

coverNonEqual = 1 (the 5 can move to 4)

With 2 operations available → freq = 2

Output: 2

🎥 Reflections

This problem is a nice combination of interval coverage + greedy adjustment. Using a difference array ensures we handle ranges efficiently, instead of checking every number individually.

That’s it for Day 36 of my LeetCode journey! Onwards to the next challenge 🔥

Happy Coding 👨‍💻