LeetCode Daily Problem P3347 Maximum Frequency of Elements After Operations II

---

Timeline

timeline

2025-10-22

init

enumeration

---

Problem:

P3347 Maximum Frequency of Elements After Operations I

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

For a value nums[i], we need to find values in nums[i] that lie within [nums[i]-k, nums[i]+k]. Such values can become the target mode through one operation. However, it is incorrect to only consider nums[i], because nums[i] can also become any value within [nums[i]-k, nums[i]+k] as the target mode through one operation.
Then do we need to enumerate all values that the candidate target mode num[i] can become through one operation as target modes? The answer is no.

Core Concept

• Sorted Arraynums
• Operable interval of each element:[nums[i]-k, nums[i]+k]
• Enumerate target mode val → count 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] → corresponding window covers nums[i] itself
• val = nums[i] - k → window left boundary just covers nums[i]
• val = nums[i] + k → window right boundary 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 not within the range
				if (val < nums.front() || val > nums.back()) {
					// If val is smaller than the minimum of nums, it is meaningless, because if any value can be turned into this val through operations, then it can certainly be turned 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 that can turn a certain value into the most frequent occurrence = original occurrence count of this value +
				// The number of times this value can be reached 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);
}