2779.Maximum Beauty of an Array After Applying Operation.md

Difficulty	Medium
Source	Daily-Question (POTD 11-Dec)
Tags	Array Binary Search Sliding Window Sorting

🚀 2779 - Maximum Beauty of an Array After Applying Operation 🧠

Problem Link:

LeetCode - Maximum Beauty of an Array After Applying Operation

💡 Problem Breakdown:

You are given a 0-indexed array nums and a non-negative integer k. In one operation, you can:

• Choose an index i that hasn't been chosen before.
• 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. You can apply the operation multiple times, but each index can only be modified once.

Your task is to find and return the maximum possible beauty of the array after applying the operation any number of times.

🔍 Example Walkthrough:

Example 1:

Input:
nums = [4, 6, 1, 2], k = 2
Output:
3

Explanation:
In this example, the following operations can be applied:

• 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].

The longest subsequence of equal elements is [4, 4, 4], with a beauty of 3.

Example 2:

Input:
nums = [1, 1, 1, 1], k = 10
Output:
4

Explanation:
In this case, no change is needed, and the entire array is already a subsequence of equal elements with length 4.

Constraints:

• 1 ≤ nums.length ≤ 10^5
• 0 ≤ nums[i] ≤ 10^5
• 0 ≤ k ≤ 10^5

🎯 My Approach:

1. Group Values by Range:
   The key observation is that for any value nums[i], you can change it to any value between [nums[i] - k, nums[i] + k]. Hence, the task is to determine which values can overlap to form the longest subsequence of equal values after applying the operation.

2. Count Frequencies:
   The goal is to determine the maximum number of elements that can be converted to the same value after applying the operation. This can be done by:

   • For each value in the array, calculate the range [value - k, value + k].
   • Use a frequency map to track how many numbers can be converted into any given target value in this range.

3. Efficient Calculation with Sliding Window or Sorting: To avoid checking all possible combinations for every element, we can sort the array and use a sliding window approach or a frequency map with the help of a prefix sum to compute the result efficiently.

🕒 Time Complexity:

• O(n log n):
  Sorting the array takes O(n log n) time. Once sorted, you can use a sliding window technique or frequency counting to determine the maximum possible subsequence length, which can be done in linear time O(n).

• Space Complexity:
  O(n): The space complexity is driven by the frequency map or sliding window data structure used to track the valid subsequences.

📝 Solution Code

Code (C):

int maximumBeauty(int* nums, int numsSize, int k) {
    int max_flower = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > max_flower) {
            max_flower = nums[i];
        }
    }

    int max_range = max_flower + k * 2 + 1;
    int* prefix_sum = (int*)calloc(max_range + 1, sizeof(int));

    for (int i = 0; i < numsSize; i++) {
        prefix_sum[nums[i]]++;
        if (nums[i] + k * 2 + 1 <= max_range) {
            prefix_sum[nums[i] + k * 2 + 1]--;
        }
    }

    int max_beauty = 0, running_sum = 0;
    for (int i = 0; i <= max_range; i++) {
        running_sum += prefix_sum[i];
        if (running_sum > max_beauty) {
            max_beauty = running_sum;
        }
    }

    free(prefix_sum);
    return max_beauty;
}

Code (C++)

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        int max_flower = *max_element(nums.begin(), nums.end());
        int max_range = max_flower + k * 2 + 1;
        vector<int> prefix_sum(max_range + 1, 0);

        for (int flower : nums) {
            prefix_sum[flower]++;
            if (flower + k * 2 + 1 <= max_range) {
                prefix_sum[flower + k * 2 + 1]--;
            }
        }

        int max_beauty = 0, running_sum = 0;
        for (int value : prefix_sum) {
            running_sum += value;
            max_beauty = max(max_beauty, running_sum);
        }

        return max_beauty;
    }
};

Code (Java)

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        int max_flower = Arrays.stream(nums).max().getAsInt();
        int max_range = max_flower + k * 2 + 1;
        int[] prefix_sum = new int[max_range + 1];

        for (int flower : nums) {
            prefix_sum[flower]++;
            if (flower + k * 2 + 1 <= max_range) {
                prefix_sum[flower + k * 2 + 1]--;
            }
        }

        int max_beauty = 0, running_sum = 0;
        for (int value : prefix_sum) {
            running_sum += value;
            max_beauty = Math.max(max_beauty, running_sum);
        }

        return max_beauty;
    }
}

Code (Python)

from typing import List

class Solution:
    def maximumBeauty(self, flowers: List[int], steps: int) -> int:
        max_flower = max(flowers)
        max_range = max_flower + steps * 2 + 2
        prefix_sum = [0] * max_range

        for flower in flowers:
            prefix_sum[flower] += 1
            if flower + steps * 2 + 1 < max_range:
                prefix_sum[flower + steps * 2 + 1] -= 1

        max_beauty = running_sum = 0

        for value in prefix_sum:
            running_sum += value
            if running_sum > max_beauty:
                max_beauty = running_sum

        return max_beauty

Code (Rust)

impl Solution {
    pub fn maximum_beauty(nums: Vec<i32>, k: i32) -> i32 {
        let max_flower = *nums.iter().max().unwrap();
        let max_range = (max_flower + k * 2 + 1) as usize;
        let mut prefix_sum = vec![0; max_range + 1];

        for &flower in &nums {
            prefix_sum[flower as usize] += 1;
            if (flower + k * 2 + 1) as usize <= max_range {
                prefix_sum[(flower + k * 2 + 1) as usize] -= 1;
            }
        }

        let mut max_beauty = 0;
        let mut running_sum = 0;
        for value in prefix_sum {
            running_sum += value;
            max_beauty = max_beauty.max(running_sum);
        }

        max_beauty
    }
}

🎯 Contribute or Ask Questions:

For more discussions, questions, or help with the solution, feel free to reach out on LinkedIn: Connect with Me!.

Enjoying the Solution?

If this helped you, please star this repo to support the efforts and keep it growing!