2779. Maximum Beauty of an Array After Applying Operation

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 01:

class Solution {
 public:
  int maximumBeauty(std::vector<int>& nums, int k) {
    int maxBeauty = 0;

    std::sort(nums.begin(), nums.end());

    for (int left = 0, right = 0; right < nums.size(); ++right) {
      while (nums[right] - nums[left] > 2 * k)
        ++left;
      maxBeauty = std::max(maxBeauty, right - left + 1);
    }

    return maxBeauty;
  }
};

class Solution:
    def maximumBeauty(self, nums: list[int], k: int) -> int:
        maxBeauty = 0
        nums.sort()

        left = 0
        for right in range(len(nums)):
            while nums[right] - nums[left] > 2 * k:
                left += 1
            maxBeauty = max(maxBeauty, right - left + 1)

        return maxBeauty

Time Complexity

• Sorting:
  • The array nums is sorted in ascending order.
  • This takes \(O(n \log n)\), where \(n\) is the size of the nums array.
• Sliding Window:
  • The sliding window technique iterates through the array with two pointers (left and right).
  • Both pointers traverse the array at most once, resulting in \(O(n)\) for this step.
• Overall Time Complexity:

  The total time complexity is \(O(n \log n)\), dominated by the sorting step.

Space Complexity

• In-Place Sorting:
  • The sorting operation is performed in-place, requiring \(O(1)\) additional space (except for the sorting algorithm’s auxiliary space).
• Other Variables:
  • Variables like maxBeauty, left, and right require \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(1)\), assuming the sorting algorithm does not use additional memory.