LeetCode Daily Problem P3346 Maximum Frequency of Elements After Operations I

---

Timeline

timeline

2025-10-21

init

enumeration

---

Problem:

P3346 Maximum Frequency of Elements After Operations I

https://leetcode.cn/problems/maximum-frequency-of-an-element-after-performing-operations-i/description/?envType=daily-question&envId=2025-10-21

WA

First look at the WA code:

#include <vector>
#include <unordered_map>
#include <algorithm>

using std::vector;
using std::unordered_map;

class Solution {
    public:
	int maxFrequency(vector<int> &nums, int k, int numOperations)
	{
		int n = nums.size();
		int i;
		int left_bound, right_bound;
		int max_val;
		int res = 0;
		unordered_map<int, int> umap;
		for (i = 0; i < n; i++) {
			umap[nums[i]]++;
		}
		std::sort(nums.begin(), nums.end());
		nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
		n = nums.size();
		for (i = 0; i < n; i++) {
			max_val = 0;
			left_bound = i - 1;
			while (left_bound >= 0 &&
			       nums[left_bound] >= nums[i] - k) {
				max_val += umap[left_bound];
				left_bound--;
			}

			right_bound = i + 1;
			while (right_bound < n &&
			       nums[right_bound] <= nums[i] + k) {
				max_val += umap[right_bound];
				right_bound++;
			}
			if (max_val <= numOperations) {
				res = std::max(res, max_val + umap[nums[i]]);
			} else {
				res = std::max(res,
					       numOperations + umap[nums[i]]);
			}
		}
		return res;
	}
};

For input

nums = [5,64]
k = 42
numOperations = 2

The above code is WA because it only enumerates the mode with the highest final frequency, which we call the target mode, only within the values in nums. In fact, each number can undergo one operation, and if two numbers become equal after one operation, that is also valid.

AC

The reason for the WA above is mainly that we did not enumerate completely. For a value nums[i], we need to find values in nums that lie in [nums[i]-k, nums[i]+k]; such values can become the target mode through one operation. However, considering only nums[i] is incorrect because nums[i] can also become any value in [nums[i]-k, nums[i]+k] as the target mode through one operation.
Then do we need to enumerate all values that nums[i] can become as the target mode through one operation? The answer is no.

Core Concept

• Sorted Arraynums
• Operable interval of each element:[nums[i]-k, nums[i]+k]
• Enumerate target mode val → count the number of elements that can become val

Define window[val-k, val+k]：

• Left boundary l: the leftmost element contained in the window
• Right boundary r: the rightmost element contained in the window
• range_size = r - l + 1

Maximum frequency:

$$f_i = \min(\text{range\_size}, \text{numOperations} + \text{count}[val])$$

Key observation

Only when the left or right boundary l or r of the window changes,range_sizewill change → f_i may increase

• Assume val ∈[nums[r]-k, nums[r+1]-k)：
  • r unchanged
  • l unchanged
  • range_size constant → f_i unchanged
• All val inside the intervalWill not increase the maximum frequency→ No need to enumerate

Critical point analysis

Critical points of window boundary changes:

1. Left boundary l change: val - k = nums[i] (left element just enters/leaves the window)
2. Right boundary r change: val + k = nums[i] (right element just enters/leaves the window)

That is,Only when val equals some nums[i] ± k or nums[i] itself, the window boundary will change.

• val = nums[i] → corresponds to the window covering nums[i] itself
• val = nums[i] - k → the left boundary of the window just covers nums[i]
• val = nums[i] + k → the right boundary of the window just covers nums[i]

These three values areall possible critical points that can change the window range

In summary: we only need to enumerate the boundary values, i.e., enumerate {nums[i]-k, nums[i], nums[i]+k}.

#include <vector>
#include <unordered_map>
#include <algorithm>

using std::vector;
using std::unordered_map;

class Solution {
    public:
	int maxFrequency(vector<int> &nums, int k, int numOperations)
	{
		int n = nums.size();
		int i;
		int range_size;
		int res = 0;
		unordered_map<int, int> umap;
		for (i = 0; i < n; i++) {
			umap[nums[i]]++;
		}
		std::sort(nums.begin(), nums.end());

		n = nums.size();
		// 0 <= numOperations <= nums.length
		for (i = 0; i < n; i++) {
			for (int val : { nums[i] - k, nums[i], nums[i] + k }) {
				// The value to enumerate is out of range.
				if (val < nums.front() || val > nums.back()) {
					// If val is smaller than the minimum value in nums, it is meaningless, because if any value can be transformed into this val through operations, then it can certainly be transformed into the minimum of nums. So why not use the minimum as the target mode?
					continue;
				}
				// range {x in nums[i] && x in {val-k..val+k}}
				range_size =
					std::upper_bound(nums.begin(),
							 nums.end(), val + k) -
					std::lower_bound(nums.begin(),
							 nums.end(), val - k);

				// The frequency that can eventually turn a certain value into the most frequent occurrence = the original occurrence count of this value +
				// The number of times it can be turned into this value through operations, but cannot exceed the number that can be converted within the window.
				res = std::max(
					res, std::min(numOperations + umap[val],
						      range_size));
			}
		}
		return res;
	}
};

int main()
{
	vector<int> nums = { 999999997, 999999999, 999999999 };
	Solution S;
	int k = 999999999;
	int numOperations = 2;
	S.maxFrequency(nums, k, numOperations);
}