Maximum Beauty of an Array After Applying Operation
MedPrompt
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
ithat 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 <= 1050 <= nums[i], k <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
The core idea is that a group of numbers can be made equal if the difference between the maximum and minimum number in the group is at most 2k. To simplify finding such groups, we can first sort the array. After sorting, any such group will form a contiguous subarray. The problem then becomes finding the longest subarray nums[i...j] where nums[j] - nums[i] <= 2k. This approach iterates through all possible subarrays of the sorted array, checks the condition, and keeps track of the maximum length found.
Algorithm
- Sort the input array
numsin non-decreasing order. - Initialize a variable
maxBeautyto 0. - Use a nested loop to iterate through all possible subarrays. The outer loop with index
idefines the start of the subarray, and the inner loop with indexjdefines the end. - For each subarray
nums[i...j], the minimum element isnums[i]and the maximum isnums[j]. - Check if the condition
nums[j] - nums[i] <= 2 * kis met. - If it is, the subarray's length
j - i + 1is a potential answer. UpdatemaxBeauty = max(maxBeauty, j - i + 1). - If the condition is not met, we can break the inner loop as any further element
nums[j+1]will also not satisfy the condition due to the sorted nature of the array. - After checking all possible starting points
i,maxBeautywill hold the maximum possible beauty.
Walkthrough
This approach begins by sorting the input array nums. This is a crucial step because it allows us to easily find the minimum and maximum elements of any subarray. For a subarray starting at index i and ending at index j in a sorted array, nums[i] is the minimum and nums[j] is the maximum. We then use two nested loops to examine every possible contiguous subarray. The outer loop selects a starting element nums[i], and the inner loop extends the subarray by including subsequent elements nums[j]. For each subarray, we check if nums[j] - nums[i] <= 2 * k. If this condition holds, it means all elements in this subarray can be transformed into a single common value, and we update our maximum beauty with the current subarray's length. If the condition fails, we can stop extending the current subarray and move to the next starting element, as the array is sorted.
import java.util.Arrays; class Solution { public int maximumBeauty(int[] nums, int k) { Arrays.sort(nums); int n = nums.length; if (n == 0) { return 0; } int maxBeauty = 1; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[j] - nums[i] <= 2 * k) { maxBeauty = Math.max(maxBeauty, j - i + 1); } else { break; // Optimization } } } return maxBeauty; }}Complexity
Time
O(N^2), where N is the number of elements in `nums`. Sorting takes O(N log N), but the nested loops to check all subarrays take O(N^2), which dominates the complexity.
Space
O(log N) or O(N), depending on the implementation of the sorting algorithm used. This space is for the recursion stack or auxiliary array for sorting.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem for small inputs.
Cons
Highly inefficient for large input sizes due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error on competitive programming platforms for the given constraints.
This approach significantly improves upon the brute-force method by using a more efficient technique to find the longest valid subarray. After sorting the array, we can use a sliding window, defined by two pointers left and right. We expand the window by moving the right pointer and shrink it by moving the left pointer whenever the condition nums[right] - nums[left] <= 2k is violated. This way, we find the longest valid subarray in a single pass over the sorted array, making it much faster.
Algorithm
- Sort the input array
nums. - Initialize two pointers,
left = 0andright = 0, representing the start and end of a sliding window. - Initialize
maxBeauty = 0. - Iterate with the
rightpointer from0tonums.length - 1to expand the window. - Inside the loop, check if the window is valid:
nums[right] - nums[left] <= 2 * k. - If the window is invalid (
nums[right] - nums[left] > 2 * k), shrink the window from the left by incrementing theleftpointer until the condition is met again. - Once the window
[left, right]is valid, its length isright - left + 1. UpdatemaxBeauty = max(maxBeauty, right - left + 1). - After the
rightpointer has traversed the entire array, returnmaxBeauty.
Walkthrough
The sliding window technique is a powerful tool for problems involving finding an optimal subarray or substring. After sorting nums, we maintain a 'window' of elements nums[left...right]. The key idea is to efficiently expand and shrink this window. We iterate through the array using a right pointer. For each nums[right], we add it to our window. Then, we check if the window's property (nums[right] - nums[left] <= 2 * k) is maintained. If not, the window is too wide, so we slide the window forward by incrementing the left pointer. We repeat this until the window is valid again. At each step, after ensuring the window is valid, we calculate its size and update our maxBeauty. Since both left and right pointers only move forward, each element is visited at most twice, leading to a linear time complexity for the scan after sorting.
import java.util.Arrays; class Solution { public int maximumBeauty(int[] nums, int k) { Arrays.sort(nums); int n = nums.length; int left = 0; int maxBeauty = 0; for (int right = 0; right < n; right++) { while (nums[right] - nums[left] > 2 * k) { left++; } maxBeauty = Math.max(maxBeauty, right - left + 1); } return maxBeauty; }}Complexity
Time
O(N log N), dominated by the initial sorting of the array. The subsequent sliding window scan takes O(N) time.
Space
O(log N) or O(N), for the space required by the sorting algorithm.
Trade-offs
Pros
Efficient and passes the time limits for the given constraints.
It's a standard, elegant, and easy-to-reason-about solution for this class of problems.
Cons
The overall performance is bottlenecked by the initial sorting step, making it slightly less optimal than non-sorting-based approaches for specific data distributions.
This approach rephrases the problem into a classic interval problem: for each number num, it can be transformed into any integer in the range [num - k, num + k]. We want to find an integer x that is included in the maximum number of these ranges. This can be solved efficiently using a sweep-line algorithm. We use a difference array to mark the start (+1) and end (-1) of each interval. By taking a prefix sum of this array, we can find the point of maximum overlap, which corresponds to the maximum beauty.
Algorithm
- Realize the problem is equivalent to finding a point on the number line covered by the maximum number of intervals
[num - k, num + k]. - Use a difference array (or sweep-line array),
line, to store the changes in overlap count. To handle potentially negative start points (num - k), use an offset to map all coordinates to non-negative indices. - The range of coordinates is from
min(num-k)tomax(num+k). An offset ofkor slightly more is sufficient. The array size should accommodatemax(num) + 2k + 2. - For each
numinnums, calculate its interval[start, end] = [num - k, num + k]. Apply the offset to these coordinates. - Increment the count at the start of the interval:
line[start + offset]++. - Decrement the count just after the end of the interval:
line[end + 1 + offset]--. - After processing all numbers, iterate through the
linearray, calculating a running prefix sum (currentBeauty). - The maximum value of this running sum is the answer,
maxBeauty.
Walkthrough
Instead of sorting the input array, this method focuses on the ranges of possible values. Each nums[i] generates a range [nums[i] - k, nums[i] + k]. We want to find a point with the highest overlap among all these ranges. The sweep-line algorithm is perfect for this. We create a large array, let's call it line, that represents the number line. Since num - k can be negative, we apply an offset to all coordinates to map them to valid array indices. For each number num, we increment line at the index corresponding to num - k and decrement it at the index for num + k + 1. This way, line[i] stores the net change in the number of active intervals at point i. Finally, we iterate through the line array, accumulating the values. The running sum at any point i gives the total number of intervals covering i. The maximum running sum we encounter is the maximum beauty.
class Solution { public int maximumBeauty(int[] nums, int k) { // The values for our sweep line can range from num-k to num+k. // With num, k <= 10^5, min(num-k) = -10^5, max(num+k) = 2*10^5. // We use an offset to map these to non-negative array indices. int offset = 100001; // Size needs to accommodate max(num+k+1) + offset, which is roughly 3*10^5. int[] line = new int[300003]; for (int num : nums) { int start = num - k + offset; int end = num + k + offset; line[start]++; if (end + 1 < line.length) { line[end + 1]--; } } int maxBeauty = 0; int currentBeauty = 0; for (int count : line) { currentBeauty += count; maxBeauty = Math.max(maxBeauty, currentBeauty); } return maxBeauty; }}Complexity
Time
O(N + V), where N is the number of elements and V is the range of values. O(N) to populate the difference array and O(V) to find the maximum overlap. This is faster than O(N log N) for the given constraints.
Space
O(V), where V is the range of values from `min(num-k)` to `max(num+k)`. Given the constraints, this is O(max(nums) + 2k), which is a constant amount of space (approx. 3*10^5).
Trade-offs
Pros
Asymptotically the fastest solution for the given constraints, as it avoids the O(N log N) sorting step.
Operates in time linear to the number of elements and the range of values.
Cons
Requires a large auxiliary array, which might lead to high memory usage if the range of values is very large.
Can be slightly more complex to implement correctly due to the need for coordinate offsetting.
Solutions
Solution
class Solution {public int maximumBeauty(int[] nums, int k) { int m = Arrays.stream(nums).max().getAsInt() + k * 2 + 2; int[] d = new int[m]; for (int x : nums) { d[x]++; d[x + k * 2 + 1]--; } int ans = 0, s = 0; for (int x : d) { s += x; ans = Math.max(ans, s); } return ans; }}class Solution {public: int maximumBeauty(vector<int> &nums, int k) { int m = *max_element(nums.begin(), nums.end()) + k * 2 + 2; vector<int> d(m); for (int x : nums) { d[x]++; d[x + k * 2 + 1]--; } int ans = 0, s = 0; for (int x : d) { s += x; ans = max(ans, s); } return ans; }};class Solution: def maximumBeauty(self, nums: List[int], k: int) -> int: m = max(nums) + k * 2 + 2 d = [0] * m for x in nums: d[x] += 1 d[x + k * 2 + 1] -= 1 ans = s = 0 for x in d: s += x ans = max(ans, s) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.