2779. Maximum Beauty of an Array After Applying Operation

Method 1

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

Method 1

【O(nlog(n)) time | O(1) space】

package Leetcode.Array;

import java.util.Arrays;

/**
 * @author zhengxingxing
 * @date 2024/12/11
 */
public class MaximumBeautyOfAnArrayAfterApplyingOperation {
    public static int maximumBeauty(int[] nums, int k) {
        // Step 1: Sort the array to bring close numbers together.
        Arrays.sort(nums);

        int maxBeauty = 1; // Tracks the maximum beauty found.
        int left = 0; // Left pointer of the sliding window.

        // Iterate through the array with the right pointer.
        for (int right = 0; right < nums.length; right++) {
            // Check if the difference between nums[right] and nums[left] exceeds 2 * k.
            // If it does, increment the left pointer to reduce the window size.
            if (nums[right] - nums[left] > 2 * k) {
                left++;
            }

            // Update the maximum beauty by comparing it to the current window size.
            maxBeauty = Math.max(maxBeauty, right - left + 1);
        }
        return maxBeauty;
    }

    public static void main(String[] args) {
        // Test case 1
        int[] nums1 = {4, 6, 1, 2};
        int k1 = 2;
        System.out.println("Test case 1: " + maximumBeauty(nums1, k1)); // Expected: 3

        // Test case 2
        int[] nums2 = {1, 1, 1, 1};
        int k2 = 0;
        System.out.println("Test case 2: " + maximumBeauty(nums2, k2)); // Expected: 4

        // Test case 3
        int[] nums3 = {10, 1, 3, 5, 7};
        int k3 = 1;
        System.out.println("Test case 3: " + maximumBeauty(nums3, k3)); // Expected: 2

        // Test case 4
        int[] nums4 = {100, 101, 102, 103, 104};
        int k4 = 2;
        System.out.println("Test case 4: " + maximumBeauty(nums4, k4)); // Expected: 5

        // Test case 5
        int[] nums5 = {8, 2, 4, 6};
        int k5 = 3;
        System.out.println("Test case 5: " + maximumBeauty(nums5, k5)); // Expected: 4
    }
}

Method 1

Enjoy Reading This Article?