We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Beauty of an Array After Applying Operation

Difficulty: Medium

Problem Description

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 and 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.

Key Insights

  • The operation allows us to replace each element in nums with a value within a specific range.
  • We can group elements that can be transformed into the same value within the range defined by k.
  • To achieve maximum beauty, we should determine the number of elements that can be transformed into the same target value.
  • Using a frequency map can help track how many elements can be adjusted to each potential target value.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting and iterating through the array. Space Complexity: O(n) - for storing frequency counts of the transformed values.

Solution

To solve this problem, we will:

  1. Use a frequency map to count how many elements can be transformed into each value.
  2. For each element in the array, calculate the range of values it can transform into and update the frequency map accordingly.
  3. The maximum beauty will be the maximum value in the frequency map.

Code Solutions

def maxBeauty(nums, k):
    from collections import defaultdict

    freq = defaultdict(int)

    for num in nums:
        # For each number, calculate the range it can transform into
        for target in range(num - k, num + k + 1):
            freq[target] += 1
    
    # The maximum beauty is the maximum value in the frequency map
    return max(freq.values())

# Example usage:
print(maxBeauty([4, 6, 1, 2], 2))  # Output: 3
← Back to All Questions