3347. Maximum Frequency of an Element After Performing Operations II

Description

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 of any element in nums after performing the operations.

 

Example 1:

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

Output: 2

Explanation:

We can achieve a maximum frequency of two by:

• Adding 0 to nums[1], after which nums becomes [1, 4, 5].
• Adding -1 to nums[2], after which nums becomes [1, 4, 4].

Example 2:

Input: nums = [5,11,20,20], k = 5, numOperations = 1

Output: 2

Explanation:

We can achieve a maximum frequency of two by:

• Adding 0 to nums[1].

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 0 <= k <= 109
• 0 <= numOperations <= nums.length

 

Solutions

Solution: Sweep Line

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} numOperations
 * @return {number}
 */
const maxFrequency = function (nums, k, numOperations) {
  const countMap = new Map();
  const lineMap = new Map();
  const candidates = new Set();
  let adjustable = 0;
  let result = 1;

  for (const num of nums) {
    const startNum = num - k;
    const endNum = num + k + 1;
    const count = countMap.get(num) ?? 0;
    const startCount = lineMap.get(startNum) ?? 0;
    const endCount = lineMap.get(endNum) ?? 0;

    countMap.set(num, count + 1);
    lineMap.set(startNum, startCount + 1);
    lineMap.set(endNum, endCount - 1);
    candidates.add(num);
    candidates.add(startNum);
    candidates.add(endNum);
  }

  const sortedCandidates = [...candidates].sort((a, b) => a - b);

  for (const num of sortedCandidates) {
    if (lineMap.has(num)) {
      adjustable += lineMap.get(num);
    }

    const count = countMap.get(num) ?? 0;
    const adjusted = adjustable - count;
    const operations = Math.min(adjusted, numOperations);

    result = Math.max(operations + count, result);
  }

  return result;
};