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 the input

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

The above code is WA, because it only restricts the enumeration range of the mode with the highest final frequency (which we call the target mode) to the values in nums. In fact, each number can undergo one operation, and if two numbers become equal after each undergoes one operation, they also meet the requirement.

AC

The main reason for the WA above is 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] through one operation, serving as the target mode.
Then do we need to enumerate all values that nums[i] can become through one operation as candidate target modes? The answer is no.

Core Concepts

• Sort the arraynums
• Each element’s operable interval:[nums[i]-k, nums[i]+k]
• Enumerate the target mode val → calculate the number of elements that can become val

Define the 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 it change → f_i can become larger

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

Critical point analysis

Critical points where the window boundaries change:

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

In other words,Only when val equals some nums[i] ± k or nums[i] itselfthe window boundaries will change.

• val = nums[i] → the corresponding window covers nums[i] itself
• val = nums[i] - k → the window’s left boundary exactly covers nums[i]
• val = nums[i] + k → the window’s right boundary exactly covers nums[i]

These three values are all the 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 even smaller than the minimum of nums, it is meaningless, because if any value can be transformed into this val through operations, then it can certainly also 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 final frequency at which a value can become the most frequent = the original count of this value +
				// the number of times it can be transformed into this value through operations, but it cannot exceed the number convertible 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);
}