LeetCode 3347

Solution

Observations

1. Convertible range of each element:
   The original value nums[i] can be converted to any value within the interval [nums[i] - k, nums[i] + k].
   The problem can be transformed into:
   Finding a target value on the number line such that the maximum number of intervals can cover this value.
   The target value will only be one of the values in nums.

2. Overlapping of intervals:
   Each nums[i] corresponds to an interval [nums[i] - k, nums[i] + k].
   If multiple intervals overlap over a certain range, it means those elements can be converted to a common value within the overlapping range.
   This can be reframed as:
   Within the overlapping range, find a value that is covered by the maximum number of intervals.
   For each interval, use its maximum bound and match it with the minimum bound of another interval, maximizing the number of overlapping intervals.

3. Operation limit:
   Elements that are already equal to the target value do not require any operation.

Strategy

Split the problem into two cases:

1. Considering duplicate target values that already exist in nums:
   For each nums[i], determine the leftmost and rightmost intervals using
   nums[l] + k >= nums[i] and nums[i] >= nums[r] - k.
   Use Sort and a Sliding Window. The interval for nums[i] can be shifted from the interval of nums[i-1], resulting in linear complexity.
   The maximum frequency is calculated as:
   min(r - l + 1 - current_count, numOperations) + current_count,
   where current_count is the number of elements equal to the current value (i.e., elements that require no operation).
   A hash map is used to store the count of each value in nums.

2. Without considering duplicate target values:
   For each interval, use nums[i] + k to match another interval's nums[j] - k.
   Apply Sort and a Sliding Window, where for each nums[i], find the rightmost nums[j] such that nums[i] + k >= nums[j] - k.
   The maximum frequency in this case is:
   min(j - i + 1, numOperations).

3. Complexity
   Time: O(n * log(n))
   Space: O(n)

Code

public int maxFrequency(int[] nums, int k, int numOperations) {
  Arrays.sort(nums);

  int res = 1;
  HashMap<Integer, Integer> num_to_count = new HashMap<>();
  // process 2
  for (int i = 0, j = 0; i < nums.length; i++) {
    int cur = nums[i], left1 = cur - k, right1 = cur + k;
    num_to_count.put(cur, num_to_count.getOrDefault(cur, 0) + 1);
    while (j < nums.length) {
      int num_j = nums[j], left2 = num_j - k, right2 = num_j + k;
      if (is_overlapping(left1, right1, left2, right2)) {
        j++;
      } else {
        break;
      }
    }
    res = Math.max(res, Math.min(j - i, numOperations));
  }

  // process 1
  for (int i = 0, start = 0, end = 0; i < nums.length; i++) {
    int cur = nums[i];
    while (start < i) {
      int start_right = nums[start] + k;
      if (start_right < cur)
        start++;
      else
        break;
    }
    while (end + 1 < nums.length) {
      int next_end_left = nums[end + 1] - k;
      if (next_end_left <= cur)
        end++;
      else
        break;
    }
    int cur_cnt = num_to_count.get(cur);
    res = Math.max(res, Math.min(end - start + 1 - cur_cnt, numOperations) + cur_cnt);
  }

  return res;
}

private boolean is_overlapping(int left1, int right1, int left2, int right2) {
  // num1 <= num2, left1 <= left2
  return left1 <= left2 && left2 <= right1;
}