The condition for nums[i] to reach target is: nums[i] - k <= target <= nums[i] + k

Naive Pseudo-code

text
max_beauty = 0
min_val = min(nums) - k
max_val = max(nums) + k

for target from min_val to max_val:
    current_count = 0
    for num in nums:
        if num - k <= target <= num + k:
            current_count += 1
    max_beauty = max(max_beauty, current_count)

return max_beauty

Complexity Analysis

• Time Complexity: $O(R \times N)$, where $R$ is the range of possible values ($max(nums) - min(nums) + 2k$) and $N$ is the number of elements. Given the constraints ($nums[i] \le 10^5$), the range is large, leading to a Time Limit Exceeded (TLE).
• Space Complexity: $O(1)$.

Why it Fails

The brute force approach performs redundant checks. It iterates through a continuous range of target values, recalculating overlaps for every single integer. This is inefficient for large input arrays or wide value ranges.

Core Insight for Maximum Beauty of an Array After Applying Operation

The key to solving LeetCode 2779 efficiently lies in transforming the problem from "finding a target value" to "finding a valid range of original values."

Two elements x and y (assume x <= y) can become equal to the same target value if and only if their reachable ranges [x - k, x + k] and [y - k, y + k] overlap. The intersection of these ranges is valid if the start of the higher range is less than or equal to the end of the lower range: y - k <= x + k y - x <= 2 * k

This inequality y - x <= 2k is the fundamental invariant. It implies that any set of numbers can become equal if the difference between the maximum and minimum number in that set is no greater than 2k.

To maximize the number of elements (the beauty), we need to find the largest subset of nums such that max(subset) - min(subset) <= 2k.

By sorting the array first, any subset we choose becomes a subarray where nums[right] is the maximum and nums[left] is the minimum. This allows us to apply the sliding window technique directly. We expand right to include more elements and advance left only when the condition nums[right] - nums[left] <= 2k is violated.

Visual Description: Imagine the sorted array on a number line. We maintain a window [left, right]. As right moves forward, the value nums[right] increases. We check the "spread" of the window, which is nums[right] - nums[left]. If this spread exceeds 2k, the window is too wide to be "squeezed" into a single point. We then move left forward to reduce the spread until the condition is met again. The maximum width achieved by this window during the scan is our answer.

Execution Flow

Let's trace nums = [4, 6, 1, 2] and k = 2.

1. Sort: nums becomes [1, 2, 4, 6].

2. State: left = 0, max_beauty = 0. Limit is 2 * k = 4.

3. Iteration 1 (right = 0):

   • Window: [1] (indices 0 to 0)
   • Check: nums[0] - nums[0] = 1 - 1 = 0. Since 0 <= 4, valid.
   • Update: max_beauty = max(0, 0 - 0 + 1) = 1.

4. Iteration 2 (right = 1):

   • Window: [1, 2] (indices 0 to 1)
   • Check: nums[1] - nums[0] = 2 - 1 = 1. Since 1 <= 4, valid.
   • Update: max_beauty = max(1, 1 - 0 + 1) = 2.

5. Iteration 3 (right = 2):

   • Window: [1, 2, 4] (indices 0 to 2)
   • Check: nums[2] - nums[0] = 4 - 1 = 3. Since 3 <= 4, valid.
   • Update: max_beauty = max(2, 2 - 0 + 1) = 3.

6. Iteration 4 (right = 3):

   • Window: [1, 2, 4, 6] (indices 0 to 3)
   • Check: nums[3] - nums[0] = 6 - 1 = 5. Since 5 > 4, invalid.
   • Shrink: Increment left to 1.
   • Re-check: nums[3] - nums[1] = 6 - 2 = 4. Since 4 <= 4, valid.
   • Update: max_beauty = max(3, 3 - 1 + 1) = 3.

7. End: Return 3.

Proof of Correctness

The correctness relies on the sorted property of the array. For any subsequence of nums to be transformed into a single value T, every element x in that subsequence must satisfy x - k <= T <= x + k. This implies that for the minimum element min_e and maximum element max_e in that subsequence, we must have max_e - k <= min_e + k, or max_e - min_e <= 2k.

By sorting nums, we ensure that the optimal subsequence corresponds to a contiguous subarray. If we pick a scattered group of indices from the sorted array, say indices i, j, m with i < j < m, the condition depends solely on nums[m] - nums[i]. If this condition holds, we can include all intermediate elements (like nums[j]) without breaking the condition, thereby increasing the subsequence length. Therefore, the problem reduces to finding the longest subarray satisfying the condition, which the sliding window algorithm exhaustively searches.

Reference Implementation

C++ Solution for LeetCode 2779

cpp
#include <vector>
#include <algorithm>

class Solution {
public:
    int maximumBeauty(std::vector<int>& nums, int k) {
        // Step 1: Sort the array to apply sliding window on a contiguous range
        std::sort(nums.begin(), nums.end());
        
        int left = 0;
        int max_beauty = 0;
        int n = nums.size();
        
        // Step 2: Sliding Window Strategy
        for (int right = 0; right < n; ++right) {
            // Step 3: Maintain the condition nums[right] - nums[left] <= 2 * k
            // If invalid, shrink the window from the left
            while (nums[right] - nums[left] > 2 * k) {
                left++;
            }
            
            // Step 4: Update the maximum window size found so far
            max_beauty = std::max(max_beauty, right - left + 1);
        }
        
        return max_beauty;
    }
};

Java Solution for LeetCode 2779

java
import java.util.Arrays;

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        // Step 1: Sort the array
        Arrays.sort(nums);
        
        int left = 0;
        int maxBeauty = 0;
        int n = nums.length;
        
        // Step 2: Sliding Window Strategy
        for (int right = 0; right < n; right++) {
            // Step 3: Check condition: difference between max and min in window <= 2k
            // If condition violated, shrink window
            while (nums[right] - nums[left] > 2 * k) {
                left++;
            }
            
            // Step 4: Update result
            maxBeauty = Math.max(maxBeauty, right - left + 1);
        }
        
        return maxBeauty;
    }
}

Python Solution for LeetCode 2779

python
class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        # Step 1: Sort the array
        nums.sort()
        
        left = 0
        max_beauty = 0
        n = len(nums)
        
        # Step 2: Sliding Window Strategy
        for right in range(n):
            # Step 3: Maintain invariant nums[right] - nums[left] <= 2 * k
            while nums[right] - nums[left] > 2 * k:
                left += 1
            
            # Step 4: Update max length
            max_beauty = max(max_beauty, right - left + 1)
            
        return max_beauty