Maximum Beauty of an Array After Applying Operation
Problem
You are given an array nums and a non-negative integer k. In one operation you may pick an index not chosen before and replace nums[i] with any value in [nums[i] − k, nums[i] + k] (each index at most once). The beauty is the length of the longest subsequence of equal elements. Return the maximum possible beauty.
Two elements a and b can be made equal iff their reachable ranges overlap, i.e. |a − b| ≤ 2k. After sorting, the task reduces to finding the longest window nums[i … j] with nums[j] − nums[i] ≤ 2k.
nums = [4,6,1,2], k = 23def maximumBeauty(nums, k):
nums.sort() # group reachable values together
left = 0 # window start over sorted nums
best = 0 # longest valid window seen
for right in range(len(nums)): # extend the window rightward
while nums[right] - nums[left] > 2 * k:
left += 1 # spread too wide: drop left value
best = max(best, right - left + 1) # window length = matching count
return bestfunction maximumBeauty(nums, k) {
nums.sort((a, b) => a - b); // group reachable values together
let left = 0; // window start over sorted nums
let best = 0; // longest valid window seen
for (let right = 0; right < nums.length; right++) {
while (nums[right] - nums[left] > 2 * k) {
left++; // spread too wide: drop left value
}
best = Math.max(best, right - left + 1); // window length = matching count
}
return best;
}int maximumBeauty(int[] nums, int k) {
Arrays.sort(nums); // group reachable values together
int left = 0; // window start over sorted nums
int best = 0; // longest valid window seen
for (int right = 0; right < nums.length; right++) {
while (nums[right] - nums[left] > 2 * k) {
left++; // spread too wide: drop left value
}
best = Math.max(best, right - left + 1); // window length
}
return best;
}int maximumBeauty(vector<int>& nums, int k) {
sort(nums.begin(), nums.end()); // group reachable values together
int left = 0; // window start over sorted nums
int best = 0; // longest valid window seen
for (int right = 0; right < (int)nums.size(); right++) {
while (nums[right] - nums[left] > 2 * k) {
left++; // spread too wide: drop left value
}
best = max(best, right - left + 1); // window length
}
return best;
}Explanation
The key observation turns a confusing operation into a clean geometry problem. Replacing nums[i] with anything in [nums[i] − k, nums[i] + k] means each value owns an interval of width 2k. Two values can be made equal exactly when their intervals overlap — and that happens iff |a − b| ≤ 2k.
So we want the largest group of values that pairwise satisfy this. If we sort the array, any such group is a contiguous run: it suffices that the smallest and largest in the run differ by at most 2k, because every value in between is automatically within range of both.
That is a textbook sliding window over the sorted array. We move right forward one element at a time. Whenever the window's spread nums[right] − nums[left] exceeds 2k, we advance left to shrink it. Because both pointers only move forward, the total work is linear after the sort.
At each step the current window [left, right] is the longest valid window ending at right, so right − left + 1 is a candidate beauty; we keep the maximum in best.
Example: nums = [4,6,1,2], k = 2 sorts to [1,2,4,6] with 2k = 4. The window [2,4,6] has spread 6 − 2 = 4 ≤ 4, length 3 — that is the answer.