⚡Flashcard Drill➔
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

  1. A set of values can all be made equal exactly when their maximum minus minimum is at most 2k.
  2. So sort the array and find the longest window with nums[r] - nums[l] <= 2k.
  3. A sliding window on the sorted array solves this in O(n) after the sort.
  4. The factor of 2 is the crux: each value may move by up to k in either direction, so the total spread allowed is 2k.

💻 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 k instead of 2k: 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 equal 2k exactly, 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems