You are given a 0-indexed array nums and a non-negative integer k.
In one operation, you can do the following:
i that hasn't been chosen before from the range [0, nums.length - 1].nums[i] with any integer from the range [nums[i] - k, nums[i] + k].The beauty of the array is the length of the longest subsequence consisting of equal elements.
Return the maximum possible beauty of the array nums after applying the operation any number of times.
Note that you can apply the operation to each index only once.
A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the order of the remaining elements.
Example 1:
Input: nums = [4,6,1,2], k = 2 Output: 3 Explanation: In this example, we apply the following operations: - Choose index 1, replace it with 4 (from range [4,8]), nums = [4,4,1,2]. - Choose index 3, replace it with 4 (from range [0,4]), nums = [4,4,1,4]. After the applied operations, the beauty of the array nums is 3 (subsequence consisting of indices 0, 1, and 3). It can be proven that 3 is the maximum possible length we can achieve.
Example 2:
Input: nums = [1,1,1,1], k = 10 Output: 4 Explanation: In this example we don't have to apply any operations. The beauty of the array nums is 4 (whole array).
Constraints:
1 <= nums.length <= 1050 <= nums[i], k <= 105Problem Overview: You are given an integer array nums and a value k. Each element can be increased or decreased by at most k. After performing the operation on every element, the goal is to maximize the beauty of the array, defined as the largest number of equal elements. The task reduces to finding the largest group of values that can be adjusted to the same number.
Approach 1: Sorting and Two Pointer Technique (O(n log n) time, O(1) space)
Sort the array first using sorting. If two numbers differ by at most 2 * k, they can be adjusted to the same value because each can move within the range [num - k, num + k]. After sorting, use a sliding window with two pointers. Expand the right pointer while the condition nums[right] - nums[left] <= 2 * k holds. If the difference exceeds this limit, move the left pointer forward to shrink the window. The window size represents how many elements can be transformed into the same value. Track the maximum window length during the scan. Sorting costs O(n log n) time and the two-pointer pass is linear.
Approach 2: HashMap Frequency Counting with Range Sweep (O(n log n) time, O(n) space)
Instead of sorting values directly, treat each number as an adjustable interval [num - k, num + k]. Use a HashMap or ordered map to perform a line sweep. Add +1 at num - k and -1 at num + k + 1. After inserting all updates, iterate through the sorted keys and maintain a running prefix sum to compute how many intervals overlap at each point. The highest overlap corresponds to the maximum beauty. This method resembles prefix-difference techniques often used with arrays and interval problems. Sorting the keys leads to O(n log n) time complexity with O(n) extra space.
Recommended for interviews: The sorting + two pointer solution is the most expected answer. It shows strong understanding of sliding window patterns and how value ranges translate into window constraints. The interval sweep idea is also valid, but interviewers typically prefer the two-pointer approach because it is simpler, memory efficient, and easier to implement under time pressure.
In this approach, we first sort the array. The idea is to use a two-pointer technique to choose a number range such that the numbers in this range can be adjusted by k to be the same. We sort the array and then for each element, expand the range using a two-pointer to see how many elements can be adjusted to fall in the range [nums[i]-k, nums[i]+k].
The function first sorts the array using quicksort. It then initializes two pointers, 'i' and 'j', both starting from the beginning of the array. 'i' represents the start of the window, and 'j' is the current element being considered for inclusion in the window. The while loop contracts the window by increasing 'i' if the difference between nums[j] and nums[i] is more than 2*k. The main goal is to find the maximum size of the window [i, j] where nums[j] can be adjusted to be equal to nums[i] with the allowed operations, represented by the length of this valid subsequence.
Time Complexity: O(n log n) due to sorting, followed by O(n) for the two-pointer scan, resulting in O(n log n) overall.
Space Complexity: O(1), since no additional space apart from input is used.
In this approach, we use a HashMap to count the occurrences of each element.. Then, for every element in the array, determine how many other elements can be adjusted to equal it given the range constraints. This involves counting up possible element choices within the range [x-k, x+k] for each x after adjusting with known positions.
We define a fixed size frequency array that takes possible adjustments into account. The frequency of alterations for any number range is recorded, storing increases with maximum numbers found (adjusted by k). Utilizing this frequency setup culminates in determining greatest repetitions possible.
Time Complexity: O(n + m) where n is the number of elements and m pertains to range demand (constant 200001).
Space Complexity: O(m) for frequency storage.
We notice that for each operation, all elements within the interval [nums[i]-k, nums[i]+k] will increase by 1. Therefore, we can use a difference array to record the contributions of these operations to the beauty value.
In the problem, nums[i]-k might be negative. We add k to all elements to ensure the results are non-negative. Thus, we can create a difference array d with a length of max(nums) + k times 2 + 2.
Next, we iterate through the array nums. For the current element x being iterated, we increase d[x] by 1 and decrease d[x+ktimes2+1] by 1. In this way, we can calculate the prefix sum for each position using the d array, which represents the beauty value for each position. The maximum beauty value can then be found.
The time complexity is O(M + 2 times k + n), and the space complexity is O(M + 2 times k). Here, n is the length of the array nums, and M is the maximum value in the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Two Pointer Technique | Time Complexity: O(n log n) due to sorting, followed by O(n) for the two-pointer scan, resulting in O(n log n) overall. |
| Approach 2: Using a HashMap for Frequency Counting | Time Complexity: O(n + m) where n is the number of elements and m pertains to range demand (constant 200001). |
| Difference Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Two Pointer Sliding Window | O(n log n) | O(1) | Best general solution; simple implementation and optimal for interviews |
| HashMap Interval Sweep (Prefix Sum) | O(n log n) | O(n) | Useful when modeling the problem as overlapping ranges or interval counting |
Maximum Beauty of an Array After Applying Operation - Leetcode 2779 - Python • NeetCodeIO • 8,935 views views
Watch 9 more video solutions →Practice Maximum Beauty of an Array After Applying Operation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor