2779.maximum-beauty-of-an-array-after-applying-operation.cpp

//  Tag: Array, Binary Search, Sliding Window, Sorting
//  Time: O(NlogN)
//  Space: O(1)
//  Ref: -
//  Note: -

//  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
//  
//  

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int i = 0;
        int res = 0;
        for (int j = 0; j < n; j++) {
            while (nums[j] - nums[i] > 2 * k) {
                i += 1;
            }

            res = max(res, j - i + 1);
        }
        return res;
    }
};

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int i = 0;
        int j = 0;
        for (j = 0; j < n; j++) {
            if (nums[j] - nums[i] > 2 * k) {
                i += 1;
            }
        }
        return j - i;
    }
};