Skip to main content
Talentd

Maximum Beauty of an Array After Applying Operation - Solution & Explanation

MediumArrayBinary SearchSliding WindowSorting20 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

You are given a 0-indexed array nums and a non-negative integer k.

In one operation, you can do the following:

  • Choose an index i that hasn't been chosen before from the range [0, nums.length - 1].
  • Replace 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 <= 105
  • 0 <= nums[i], k <= 105

Approach Overview

Problem 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.

Approach 1: Approach 1: Sorting and Two Pointer Technique

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Using a HashMap for Frequency Counting

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Difference Array

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), since no additional space apart from input is used.

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).
Space Complexity: O(m) for frequency storage.

Difference Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Two Pointer Sliding WindowO(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

Video Solution

Maximum Beauty of an Array After Applying Operation - Leetcode 2779 - Python • NeetCodeIO • 9,175 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Beauty of an Array After Applying Operation easy or hard?
The problem is rated Medium on LeetCode. The challenge lies in recognizing that each value can shift within [num-k, num+k] and translating that into a constraint on sorted differences. Once this observation is made, a sliding window solution becomes straightforward.
Maximum Beauty of an Array After Applying Operation Python/Java solution
Most implementations sort the array and use two pointers to maintain a window where nums[right] - nums[left] <= 2*k. The window length gives the current beauty, and the maximum across all windows is returned. This approach works efficiently in Python, Java, C++, JavaScript, and other languages.
How to solve Maximum Beauty of an Array After Applying Operation in O(n)?
A pure O(n) solution is difficult because the values need ordering or range processing. The closest approach uses interval counting with prefix sums or a HashMap sweep, but sorting the keys usually leads to O(n log n) time. The practical optimal method remains sorting plus a sliding window.
What is the best approach for Maximum Beauty of an Array After Applying Operation?
The most efficient and interview-preferred approach is sorting the array followed by a sliding window (two pointers). After sorting, maintain a window where the difference between the smallest and largest values is at most 2*k. All numbers in that window can be adjusted to the same value. This solution runs in O(n log n) time due to sorting and uses O(1) extra space.
Is Maximum Beauty of an Array After Applying Operation asked at Google/Amazon/Meta?
This problem follows a common interview pattern combining sorting and sliding window techniques. Similar range-normalization or frequency-maximization problems appear in interviews at companies like Amazon, Google, and Meta when evaluating array manipulation and two-pointer reasoning.
What data structure is used in Maximum Beauty of an Array After Applying Operation?
The main data structures are arrays (for sorting and window scanning) and optionally a HashMap or ordered map for interval sweep counting. The optimal solution primarily relies on sorting and the sliding window two-pointer pattern.
What is the time complexity of Maximum Beauty of an Array After Applying Operation?
The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, a linear sliding window scan computes the maximum valid group in O(n) time. The space complexity is O(1) if sorting is done in place.

Ready to solve this problem?

Practice Maximum Beauty of an Array After Applying Operation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Size Subarray Sum Equals k

Next

Partition Array Such That Maximum Difference Is K