Maximum Beauty of an Array After Applying Operation

Leetcode Problem:

• Maximum Beauty of an Array After Applying Operation

Summary

• Given a 0-indexed array nums and a non-negative integer k, find the maximum possible beauty of the array after applying the operation any number of times.

Approach

• This problem can be solved by using a two-pointer technique
• The idea is to maintain two pointers, one at the beginning and one at the end of the array
• The pointer at the end is used to track the maximum possible beauty
• The pointer at the beginning is used to track the minimum possible value in the current window
• If the difference between the value at the end pointer and k is less than or equal to the sum of the value at the beginning pointer and k, it means that we can extend the current window to the right
• Otherwise, we move the beginning pointer to the right.

Complexity

• O(n log n) due to the sorting operation, where n is the size of the input array.

Explanation

• The solution starts by sorting the input array in ascending order
• Then it initializes two pointers, l and r, to 0
• It also initializes a variable ans to 1
• The while loop continues until the end pointer r reaches the end of the array
• Inside the loop, it checks if the difference between the value at the end pointer and k is less than or equal to the sum of the value at the beginning pointer and k
• If the condition is true, it means that we can extend the current window to the right, so it increments the end pointer r and updates the ans variable with the maximum of the current ans and the difference between the end pointer r and the beginning pointer l
• Otherwise, it increments the beginning pointer l
• Finally, the solution returns the ans variable, which represents the maximum possible beauty of the array.

Solution Code:

class Solution {
public:
    int maximumBeauty(vector& nums, int k) {
        sort(nums.begin(), nums.end());
        int l = 0;
        int r = 0;
        int ans = 1;
        while(r < nums.size()){
            if(nums[r] - k <= nums[l] + k){
                r++;
                ans = max(ans, r - l);
            } else{
                l++;
            }
        }
        
        
        return ans;
    }
};