Facebook Pixel

2779. Maximum Beauty of an Array After Applying Operation

MediumArrayBinary SearchSortingSliding Window
Leetcode Link

Problem Description

You have an array nums (0-indexed) and a non-negative integer k. You can perform operations on this array to maximize its "beauty".

For each operation:

  • Select an index i that hasn't been used before (from 0 to nums.length - 1)
  • Replace nums[i] with any integer in the range [nums[i] - k, nums[i] + k]

The beauty of an array is defined as the length of the longest subsequence where all elements are equal.

Your goal is to find the maximum possible beauty after applying any number of operations (remembering that each index can only be chosen once).

Key points:

  • Each index can only be modified once
  • When you modify an element at index i, you can change it to any value between nums[i] - k and nums[i] + k (inclusive)
  • A subsequence maintains the relative order of elements from the original array but can skip elements
  • You want to maximize the count of equal elements that can form a subsequence

Example understanding: If you have nums = [1, 3, 5] and k = 2:

  • Element at index 0 can become any value in [1-2, 1+2] = [-1, 3]
  • Element at index 1 can become any value in [3-2, 3+2] = [1, 5]
  • Element at index 2 can become any value in [5-2, 5+2] = [3, 7]

By choosing value 3 for all elements (which is possible given the ranges), you can achieve a beauty of 3 (all elements equal).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is to think about this problem from a different angle: instead of trying to figure out which value each element should become, we can ask "what values could potentially be the target value that maximizes our beauty?"

For any target value t, an element nums[i] can be changed to t if and only if t falls within the range [nums[i] - k, nums[i] + k]. This means each element contributes to a specific range of possible target values.

Now here's the crucial observation: if we want to maximize beauty for some target value t, we need to count how many elements from the original array can be transformed to t. This is equivalent to counting how many intervals [nums[i] - k, nums[i] + k] contain the value t.

This transforms our problem into: find the value t that is covered by the maximum number of intervals.

Think of it like this: each element "votes" for a range of values it can become. The value with the most votes is our answer, and the number of votes is our maximum beauty.

To efficiently count overlapping intervals, we can use a difference array technique. When an interval [a, b] starts, we add 1 at position a. When it ends, we subtract 1 at position b + 1. After processing all intervals, the prefix sum at any position tells us how many intervals cover that position.

Since we're dealing with ranges like [nums[i] - k, nums[i] + k], each element essentially creates an interval of width 2k. To handle potential negative values and simplify indexing, the solution shifts everything by adding k to ensure all values are non-negative.

The beauty of this approach is that instead of trying different combinations of transformations, we directly find the optimal target value by counting interval overlaps in linear time after sorting.

Learn more about Binary Search, Sorting and Sliding Window patterns.

Solution Approach

The solution uses a difference array technique to efficiently count overlapping intervals.

Step 1: Understanding the transformation

  • Each element nums[i] can be changed to any value in range [nums[i] - k, nums[i] + k]
  • This creates an interval of length 2k + 1 for each element
  • To avoid negative indices in our difference array, we shift all values by adding k

Step 2: Setting up the difference array

m = max(nums) + k * 2 + 2
d = [0] * m
  • We create a difference array d with size m
  • The size accounts for: maximum value in nums + the maximum possible increase (k * 2) + extra space for boundary handling (+ 2)

Step 3: Marking intervals in the difference array

for x in nums:
    d[x] += 1
    d[x + k * 2 + 1] -= 1
  • For each element x in nums, we mark the start and end of its interval
  • Since we're working with the original values (not shifted), the interval for element x is [x - k, x + k]
  • In the difference array representation:
    • We increment at the start of the interval: d[x] (representing x - k after considering the shift)
    • We decrement right after the end: d[x + k * 2 + 1] (representing x + k + 1 after considering the shift)
  • The interval length is 2k + 1, so the decrement happens at position x + 2k + 1

Step 4: Computing the maximum overlapping intervals

return max(accumulate(d))
  • accumulate(d) computes the prefix sum of the difference array
  • At each position, the prefix sum tells us how many intervals cover that position
  • The maximum value in this prefix sum is our answer - it represents the maximum number of elements that can be transformed to the same value

Why this works:

  • The difference array efficiently handles range updates in O(1) per interval
  • The prefix sum converts these range markers back into actual counts
  • By finding the maximum count, we find the value that the most elements can reach, which gives us the maximum beauty

Time Complexity: O(n + m) where n is the length of nums and m is the range of values Space Complexity: O(m) for the difference array

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example: nums = [4, 6, 1, 2] and k = 2

Step 1: Understand what ranges each element can become

  • Element 4 can become any value in [4-2, 4+2] = [2, 6]
  • Element 6 can become any value in [6-2, 6+2] = [4, 8]
  • Element 1 can become any value in [1-2, 1+2] = [-1, 3]
  • Element 2 can become any value in [2-2, 2+2] = [0, 4]

Step 2: Set up the difference array

  • Calculate size: m = max(nums) + k*2 + 2 = 6 + 4 + 2 = 12
  • Initialize: d = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Step 3: Mark intervals in the difference array

For each element, we mark start and end of its interval:

  • For nums[0] = 4:

    • Increment at d[4]: start of interval
    • Decrement at d[4 + 2*2 + 1] = d[9]: after end of interval
    • d = [0, 0, 0, 0, 1, 0, 0, 0, 0, -1, 0, 0]

  • For nums[1] = 6:

    • Increment at d[6], decrement at d[11]
    • d = [0, 0, 0, 0, 1, 0, 1, 0, 0, -1, 0, -1]

  • For nums[2] = 1:

    • Increment at d[1], decrement at d[6]
    • d = [0, 1, 0, 0, 1, 0, 0, 0, 0, -1, 0, -1]
    • Note: d[6] becomes 0 after decrement

  • For nums[3] = 2:

    • Increment at d[2], decrement at d[7]
    • d = [0, 1, 1, 0, 1, 0, 0, -1, 0, -1, 0, -1]

Step 4: Compute prefix sum (accumulate) Starting from index 0, compute running sum:

Index:      0  1  2  3  4  5  6  7  8  9  10  11
Diff array: 0  1  1  0  1  0  0 -1  0 -1  0  -1
Prefix sum: 0  1  2  2  3  3  3  2  2  1  1   0

The prefix sum at each position tells us how many intervals cover that position:

  • Position 4-6 (values 2-4 in original problem space) are covered by 3 intervals
  • This means 3 elements can be transformed to any of these values

Step 5: Find maximum The maximum value in the prefix sum is 3, which occurs at positions 4, 5, and 6.

Verification: Let's verify by choosing target value 4 (which corresponds to position 6 in our array, but represents value 4 in the original space):

  • Element 4 can become 4 ✓ (4 is in range [2, 6])
  • Element 6 can become 4 ✓ (4 is in range [4, 8])
  • Element 1 cannot become 4 ✗ (4 is not in range [-1, 3])
  • Element 2 can become 4 ✓ (4 is in range [0, 4])

Three elements can become 4, giving us a beauty of 3, which matches our answer!

Solution Implementation

1from typing import List
2from itertools import accumulate
3
4class Solution:
5    def maximumBeauty(self, nums: List[int], k: int) -> int:
6        # Calculate the size needed for the difference array
7        # Each number can be adjusted by ±k, so the range is [num-k, num+k]
8        # We need space up to max(nums) + k, plus extra for the difference array technique
9        max_value = max(nums) + k * 2 + 2
10      
11        # Initialize difference array to track range updates
12        difference_array = [0] * max_value
13      
14        # For each number, mark the range [num, num + 2k] in the difference array
15        # This represents the possible range after adjustment
16        for num in nums:
17            # Increment at the start of the range
18            difference_array[num] += 1
19            # Decrement after the end of the range
20            difference_array[num + k * 2 + 1] -= 1
21      
22        # Use prefix sum (accumulate) to get actual counts at each position
23        # The maximum value represents the maximum overlapping ranges
24        return max(accumulate(difference_array))
25
1class Solution {
2    public int maximumBeauty(int[] nums, int k) {
3        // Find the maximum value in nums and calculate the size of the difference array
4        // We add k*2 + 2 to handle the maximum possible range after operations
5        int maxValue = Arrays.stream(nums).max().getAsInt();
6        int differenceArraySize = maxValue + k * 2 + 2;
7      
8        // Initialize difference array to track interval changes
9        int[] differenceArray = new int[differenceArraySize];
10      
11        // For each number, we can change it to any value in range [num-k, num+k]
12        // So we mark the start and end of each possible interval
13        for (int num : nums) {
14            // Increment at the start of the interval [num, num+2k]
15            differenceArray[num]++;
16            // Decrement right after the end of the interval
17            differenceArray[num + k * 2 + 1]--;
18        }
19      
20        // Use prefix sum to find the maximum overlap of intervals
21        int maxBeauty = 0;
22        int currentSum = 0;
23      
24        // Traverse the difference array and calculate running sum
25        for (int difference : differenceArray) {
26            currentSum += difference;
27            // Update maximum beauty (maximum number of overlapping intervals)
28            maxBeauty = Math.max(maxBeauty, currentSum);
29        }
30      
31        return maxBeauty;
32    }
33}
34
1class Solution {
2public:
3    int maximumBeauty(vector<int>& nums, int k) {
4        // Find the maximum possible value after operations
5        // Each number x can be changed to any value in range [x-k, x+k]
6        // So we need to consider up to max_value + k
7        int maxValue = *max_element(nums.begin(), nums.end());
8        int arraySize = maxValue + 2 * k + 2;
9      
10        // Difference array to track range updates efficiently
11        vector<int> differenceArray(arraySize);
12      
13        // For each number, mark the range it can be transformed to
14        // A number x can become any value in [x, x + 2k] after shifting by -k to +k
15        for (int num : nums) {
16            differenceArray[num]++;                    // Start of range
17            differenceArray[num + 2 * k + 1]--;       // End of range + 1
18        }
19      
20        // Calculate prefix sum to get actual counts at each position
21        int maxBeauty = 0;
22        int currentSum = 0;
23      
24        for (int count : differenceArray) {
25            currentSum += count;  // Running sum gives count of numbers that can reach this value
26            maxBeauty = max(maxBeauty, currentSum);
27        }
28      
29        return maxBeauty;
30    }
31};
32
1/**
2 * Finds the maximum beauty value by allowing each number to be modified within range [-k, k]
3 * Uses difference array technique to track overlapping ranges efficiently
4 * 
5 * @param nums - Array of integers to process
6 * @param k - Maximum allowed modification range for each number
7 * @returns Maximum beauty value (maximum overlap count)
8 */
9function maximumBeauty(nums: number[], k: number): number {
10    // Calculate the maximum possible value after modifications
11    // Each number can increase by k, and we need range of 2k, plus buffer
12    const maxValue: number = Math.max(...nums) + k * 2 + 2;
13  
14    // Initialize difference array to track range updates
15    // differenceArray[i] represents the change at position i
16    const differenceArray: number[] = Array(maxValue).fill(0);
17  
18    // For each number, mark the range [x, x + 2k] where it can contribute
19    // Using difference array technique: increment at start, decrement after end
20    for (const num of nums) {
21        differenceArray[num]++;                    // Start of range
22        differenceArray[num + k * 2 + 1]--;       // End of range + 1
23    }
24  
25    // Track the maximum overlap count
26    let maxOverlap: number = 0;
27  
28    // Calculate prefix sum to get actual counts at each position
29    let currentSum: number = 0;
30    for (const delta of differenceArray) {
31        currentSum += delta;
32        maxOverlap = Math.max(maxOverlap, currentSum);
33    }
34  
35    return maxOverlap;
36}
37

Time and Space Complexity

The time complexity is O(M + 2k + n), where:

  • n is the length of the array nums
  • M is the maximum value in the array nums
  • The max(nums) operation takes O(n) time
  • Creating and initializing the difference array d of size m = M + 2k + 2 takes O(M + 2k) time
  • The loop to update the difference array iterates n times with O(1) operations each, taking O(n) time
  • The accumulate(d) function iterates through all m elements, taking O(M + 2k) time
  • The max() on the accumulated values takes O(M + 2k) time
  • Overall: O(n) + O(M + 2k) + O(n) + O(M + 2k) + O(M + 2k) = O(M + 2k + n)

The space complexity is O(M + 2k), where:

  • The difference array d has size m = M + 2k + 2, which is O(M + 2k)
  • The accumulate() function creates an iterator that uses O(1) additional space
  • No other significant auxiliary space is used

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Interval Representation

Pitfall: A common mistake is incorrectly mapping the adjustable range [nums[i] - k, nums[i] + k] to the difference array indices. Developers often confuse whether to use nums[i] or nums[i] - k as the starting point.

Why it happens: The code uses d[x] and d[x + k * 2 + 1] which might seem counterintuitive since the actual range is [x - k, x + k].

Correct understanding: The trick is that we're using a shifted representation. For an element with value x, the range [x - k, x + k] has length 2k + 1. In the difference array:

  • We mark the start at index x (which implicitly represents x - k after considering the overall shift)
  • We mark the end at index x + 2k + 1 (one position after the last valid index)

Solution: Always remember that the difference array indices are relative to the minimum possible value. The interval for element x spans from x to x + 2k in the array indices.

2. Incorrect Array Size Calculation

Pitfall: Using insufficient size for the difference array, leading to index out of bounds errors.

# Wrong: might cause index out of bounds
m = max(nums) + k + 1
d = [0] * m

Why it happens: Forgetting that each element can increase by up to k, and we need an extra position for the difference array technique (marking one position past the end).

Solution: The correct size should be max(nums) + k * 2 + 2:

  • max(nums): base maximum value
  • + k * 2: accounts for the maximum possible increase (since range is 2k + 1 wide)
  • + 2: extra space for the difference array boundary marking

3. Off-by-One Error in Range Marking

Pitfall: Incorrectly marking the end of the interval:

# Wrong: marks the interval incorrectly
d[x + k * 2] -= 1  # Should be x + k * 2 + 1

Why it happens: Confusion about whether to decrement at the last valid position or one position after.

Solution: In the difference array technique, always decrement at end + 1 position. Since our interval ends at x + 2k, we decrement at x + 2k + 1.

4. Forgetting to Handle Edge Cases

Pitfall: Not considering when k = 0 or when the array has only one element.

Solution: The current implementation handles these cases correctly:

  • When k = 0, each element can only stay as itself (interval of length 1)
  • With one element, the beauty is always 1
  • The difference array approach works correctly for both cases

5. Using Regular Array Updates Instead of Difference Array

Pitfall: Trying to mark all positions in each range individually:

# Inefficient approach - O(n * k) time complexity
for num in nums:
    for i in range(num, num + 2*k + 1):
        count_array[i] += 1

Why it's problematic: This approach has O(n * k) time complexity, which can be very slow for large values of k.

Solution: Use the difference array technique as shown in the original solution for O(n) range updates.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Sliding Window Maximum

https assets algo monster cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in the window The window

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More