2779. Maximum Beauty of an Array After Applying Operation

2779. Maximum Beauty of an Array After Applying Operation

Difficulty: Medium

Topics: Array, Binary Search, Sliding Window, Sorting

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

Hint:

1. Sort the array.
2. The problem becomes the following: find maximum subarray A[i … j] such that A[j] - A[i] ≤ 2 * k.

Solution:

We can utilize sorting and a sliding window approach.

Approach:

1. Sort the array: Sorting simplifies identifying subsequences where the difference between the largest and smallest element does not exceed 2k.
2. Sliding window technique: Maintain a window of indices [i, j] where the difference nums[j] - nums[i] <= 2k. Adjust i or j to maximize the window size.

Let's implement this solution in PHP: 2779. Maximum Beauty of an Array After Applying Operation

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function maximumBeauty($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage:
$nums1 = [4, 6, 1, 2];
$k1 = 2;
echo maximumBeauty($nums1, $k1) . "\n"; // Output: 3

$nums2 = [1, 1, 1, 1];
$k2 = 10;
echo maximumBeauty($nums2, $k2) . "\n"; // Output: 4
?>

Explanation:

1. Sorting the Array:
   • Sorting ensures that the window defined by indices [i, j] has all elements in increasing order, which makes it easier to check the difference between the smallest and largest values in the window.
2. Sliding Window:
   • Start with both i and j at the beginning.
   • Expand the window by incrementing j and keep the window valid by incrementing i whenever the condition nums[j] - nums[i] > 2k is violated.
   • At each step, calculate the size of the current valid window j - i + 1 and update the maxBeauty.

---

Complexity Analysis:

1. Time Complexity:
   • Sorting the array: O(n log n).
   • Sliding window traversal: O(n).
   • Overall: O(n log n).
2. Space Complexity:
   • O(1), as the solution uses only a few additional variables.

---

Examples:

Input 1:

$nums = [4, 6, 1, 2];
$k = 2;
echo maximumBeauty($nums, $k); // Output: 3

Input 2:

$nums = [1, 1, 1, 1];
$k = 10;
echo maximumBeauty($nums, $k); // Output: 4

This solution adheres to the constraints and efficiently computes the result for large inputs.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub