Maximum Beauty of an Array After Applying Operation

Medium
799.

Maximum Beauty of an Array After Applying Operation

Maximum Beauty of an Array After Applying Operation is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Atlassian interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumBeauty = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Beauty of an Array After Applying Operation Solution

Maximum Beauty of an Array After Applying Operation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Beauty of an Array After Applying Operation is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Atlassian interviews.

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

Hints for Maximum Beauty of an Array After Applying Operation

  1. Hint 1

    A subsequence, not a subarray — so order does not matter and you may sort.

  2. Hint 2

    Two elements can be made equal exactly when their values differ by at most 2k.

  3. Hint 3

    Find the largest group of sorted values whose spread is at most 2k.

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

  1. Sort nums.
  2. Slide a window; while a[r] - a[l] > 2k, advance l.
  3. 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

Java

public static int maximumBeauty(int[] nums, int k) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int l = 0, best = 0;
    for (int r = 0; r < a.length; r++) {
        while (a[r] - a[l] > 2 * k) l++;
        best = Math.max(best, r - l + 1);
    }
    return best;
}

C++

int maximumBeauty(vector<int>& nums, int k) {
    vector<int> a = nums;
    sort(a.begin(), a.end());
    int l = 0, best = 0;
    for (int r = 0; r < (int) a.size(); r++) {
        while (a[r] - a[l] > 2 * k) l++;
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms