Maximum Beauty of an Array After Applying Operation
Medium
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
ithat 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).
Can you implement a solution that efficiently finds the maximum possible beauty of the array?
Solution
Naive Approach
The most straightforward approach is to iterate through all possible subsequences of the input array nums and, for each subsequence, check if the elements can be made equal by applying the given operation. The maximum length of such a subsequence will be the answer.
- Generate all subsequences of
nums. - For each subsequence, check if its elements can be transformed to be equal within the given
krange. - Keep track of the maximum length among valid subsequences.
This approach has a time complexity of O(2n * n), where n is the length of nums, because there are 2n possible subsequences and checking each subsequence takes O(n) time. The space complexity would be O(n) in the worst case.
This approach is not efficient and will likely result in a time-limit-exceeded error for larger input sizes.
Optimal Approach: Greedy Algorithm
An efficient approach involves sorting the array and then using a sliding window to find the longest subsequence that can be made equal. The main idea is to greedily expand the window as long as all elements within the window can be transformed to a common value within the given k range.
- Sort the array
nums. Sorting allows us to consider elements in increasing order and makes it easier to determine if elements can be made equal within the rangek. - Iterate through the sorted array using a sliding window. Maintain two pointers,
leftandright, representing the start and end of the window. - Check if all elements within the window can be made equal. For a window
nums[left...right], all elements can be made equal ifnums[right] - nums[left] <= 2 * k. - Expand or shrink the window. If the condition in step 3 is met, expand the window by incrementing
right. Otherwise, shrink the window by incrementingleft. - Update the maximum beauty. Keep track of the maximum window size encountered during the iteration. This will be the maximum possible beauty of the array.
Edge Cases
- If the input array is already consisting of all equal elements then just return length of the array
- If k is large enough to cover the whole input array range, all numbers can be converted into same number, hence return length of the array.
def max_beauty(nums, k):
nums.sort()
left = 0
max_len = 0
for right in range(len(nums)):
while nums[right] - nums[left] > 2 * k:
left += 1
max_len = max(max_len, right - left + 1)
return max_len
Time Complexity: O(n log n) due to sorting the array. The sliding window part takes O(n) time.
Space Complexity: O(1). Sorting can be done in-place, and we use a constant amount of extra space.
