NeetCode #251LC-2779MediumSliding Window
← Back to All Problems#251 · #2779 · Maximum Beauty of an Array After Applying Operation(数组的最大美丽值)
📌 Problem Statement & Constraints
You are given a 0-indexed integer array
nums and a non-negative integer k. In one operation you may choose an index and replace nums[i] with any integer in [nums[i] - k, nums[i] + k]. Return the maximum beauty of the array: the length of the longest subsequence whose elements can all be made equal. Constraints: 1 <= nums.length <= 10^5, 0 <= nums[i] <= 10^5, 0 <= k <= 10^5.💡 Core Algorithmic Approaches
- A set of values can all be made equal exactly when their maximum minus minimum is at most
2k. - So sort the array and find the longest window with
nums[r] - nums[l] <= 2k. - A sliding window on the sorted array solves this in O(n) after the sort.
- The factor of 2 is the crux: each value may move by up to
kin either direction, so the total spread allowed is2k.
💻 Benchmark Python3 Implementation
class Solution:
def maximumBeauty(self, nums: List[int], k: int) -> int:
nums.sort()
l = 0
best = 0
for r in range(len(nums)):
while nums[r] - nums[l] > 2 * k: # spread too large
l += 1
best = max(best, r - l + 1)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort dominates; the window scan is O(n).
💾 Space Complexity
O(1) beyond the sort.
⚠️ Interview Pitfalls & Follow-ups
- Using
kinstead of2k: the allowed spread is twice the operation range, because both ends can move. - Forgetting to sort: the sliding window relies on the sorted order to make the spread monotone.
- Assuming the subsequence must be contiguous in the original array: it is a subsequence, so any set of elements works and sorting is legitimate.
- Using
>= 2k: the spread may equal2kexactly, so the condition is> 2k.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner