Maximum Beauty of an Array After Applying Operation — Medium Problem & Solution

You may apply this operation to each index at most once: choose an index not chosen before and replace nums[i] with any integer in [nums[i] - k, nums[i] + k].

Difficulty: Medium
Topics: Arrays, Sorting, Binary Search, Sliding Window
Asked at: Amazon, Google, Atlassian
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You may apply this operation to each index at most once: choose an index not chosen before and replace nums[i] with any integer in [nums[i] - k, nums[i] + k].

The beauty of an array is the length of its longest subsequence of equal elements. Return the maximum beauty achievable.

Example 1

Input: nums = [4,6,1,2], k = 2
Output: 3
Explanation: Turn 4, 6 and 2 all into 4 — each moves by at most 2.

Example 2

Input: nums = [1,1,1,1], k = 10
Output: 4
Explanation: They are already equal.

Example 3

Input: nums = [10,1,20], k = 3
Output: 1

Constraints

1 <= nums.length <= 100000
0 <= nums[i], k <= 100000

How to solve Maximum Beauty of an Array After Applying Operation

Element x can become any value in [x-k, x+k], so two elements can meet exactly when their intervals overlap, i.e. when they differ by at most 2k. A set of elements can all meet at one value precisely when its spread is within 2k — and after sorting, the best such set is contiguous.

Approach

Sort nums.
Slide a window; while a[r] - a[l] > 2k, advance l.
Track the widest valid window.

Why it works

Intervals on a line have the Helly property: a family of intervals has a common point exactly when every pair overlaps, which for equal-radius intervals reduces to max - min <= 2k. On sorted data that is a[r] - a[l], and since widening the window on the left only increases the spread, the predicate is monotone and one left pointer suffices.

Complexity

Time — O(n log n)
Space — O(n)

Pitfalls

Using k rather than 2k halves every window — both endpoints may move.
Treating it as a subarray problem forbids the sort and gives a smaller answer.
k = 0 reduces to the largest count of a repeated value.

Reference solution

Python

from typing import List

def maximumBeauty(nums: List[int], k: int) -> int:
    a = sorted(nums)
    l = 0
    best = 0
    for r in range(len(a)):
        while a[r] - a[l] > 2 * k:
            l += 1
        best = max(best, r - l + 1)
    return best

JavaScript

var maximumBeauty = function(nums, k) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var l = 0, best = 0;
    for (var r = 0; r < a.length; r++) {
        while (a[r] - a[l] > 2 * k) l++;
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue