Maximum Beauty of an Array After Applying Operation

Maximum Beauty of an Array After Applying Operation - Problem

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 i that 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: 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,6,1,2], k = 2

› Output: 3

💡 Note: We can transform the array to [4,4,3,4]. Elements at indices 0, 2, and 3 become equal (ignoring order), so beauty = 3.

Example 2 — Large k Value

$ Input: nums = [1,1,1,1], k = 10

› Output: 4

💡 Note: All elements are already equal, so we can make all 4 elements the same value. Beauty = 4.

Example 3 — No Overlap Possible

$ Input: nums = [1,10], k = 2

› Output: 1

💡 Note: Element 1 can become [1-2,1+2] = [-1,3]. Element 10 can become [10-2,10+2] = [8,12]. No overlap possible, so beauty = 1.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i], k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

[4,6,1,2] with k=2, each element can change by ±2

Transform Ranges

Each element gets a range: 4→[2,6], 6→[4,8], 1→[-1,3], 2→[0,4]

Find Overlaps

Target value 3 can be reached by elements 4,1,2 (beauty=3)

Key Takeaway

🎯 Key Insight: Sort the array first, then use sliding window to find the maximum number of elements whose transformation ranges can overlap

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is that after each element can be transformed to a range [nums[i]-k, nums[i]+k], we need to find the maximum number of ranges that can overlap at some common target value. The optimal approach uses sliding window on sorted array - sort first, then use two pointers to find the maximum window where nums[right] - nums[left] ≤ 2k. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window on Sorted Array	O(n log n)	O(1)	Sort array then use sliding window to find maximum overlapping ranges
Brute Force - Try All Target Values	O(n² × k)	O(1)	Try every possible target value and count how many elements can reach it
Binary Search on Answer	O(n log n)	O(1)	Binary search on the answer length and check if it's achievable

Sliding Window on Sorted Array — Algorithm Steps

Sort the array
Use sliding window to find maximum elements with overlapping ranges
The window size gives the maximum beauty

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort elements to group similar values

Expand Window

Expand right pointer while ranges can overlap

Shrink Window

Shrink left pointer when ranges can't overlap

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), compare);
    int maxBeauty = 1;
    int left = 0;
    
    for (int right = 1; right < numsSize; right++) {
        // Check if nums[left] and nums[right] can have overlapping ranges
        while (nums[right] - nums[left] > 2 * k) {
            left++;
        }
        int current = right - left + 1;
        if (current > maxBeauty) {
            maxBeauty = current;
        }
    }
    
    return maxBeauty;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), sliding window takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using pointers and variables, sorting can be done in-place

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

324 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window on Sorted Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler