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

Examples

Example 1:

Input: nums = [4,6,1,2], k = 2
Output: 3
Explanation: In this example, we apply the following operations:
- Choose index 1, replace it with 4 (from range [4,8]), nums = [4,4,1,2].
- Choose index 3, replace it with 4 (from range [0,4]), nums = [4,4,1,4].
After the applied operations, the beauty of the array nums is 3 (subsequence consisting of indices 0, 1, and 3).
It can be proven that 3 is the maximum possible length we can achieve.

Example 2:

Input: nums = [1,1,1,1], k = 10
Output: 4
Explanation: In this example we don't have to apply any operations.
The beauty of the array nums is 4 (whole array).

Constraints:

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

Solution

Method 1 - Number of overlapping events

One of the approach can be to For every element in the array, we can add or subtract any value up to ( k ). This means an element nums[i] can be in the range [nums[i] - k, nums[i] + k]. So, for [4,6,1,2], the range of elements will be: [2,6] [4,8] [-1,3] [0,4].

And we want to find the index range [a, b] where the most number of collisions or conflicts occur, because that is the point where most number of elements can be equal. So, this problem can be translated to “range coverage” problem where we are interested in finding the maximum number of ranges that overlap at any point. Here that range is at [4, 4] where max 3 events meet. This problem variant is covered here - Maximum Intervals Overlap Count.

So, our approach can be to

  1. Generate the events
    • For each number in nums, generate a start and end event.
    • 4 creates events: (4 - 2, +1) -> (2, +1) and (4 + 2 + 1, -1) -> (7, -1)
    • 6 creates events: (6 - 2, +1) -> (4, +1) and (6 + 2 + 1, -1) -> (9, -1)
    • 1 creates events: (1 - 2, +1) -> (-1, +1) and (1 + 2 + 1, -1) -> (4, -1)
    • 2 creates events: (2 - 2, +1) -> (0, +1) and (2 + 2 + 1, -1) -> (5, -1)
    • The range [num - k, num + k] is inclusive, meaning it includes both boundaries num - k and num + k.
    • To distinguish the end of one range from the start of another, we make the end boundary exclusive by adding 1. Thus, the end event is represented as num + k + 1.
    • This prevents counting the end of one range and the start of another at the same point incorrectly as overlapping.
    • events = [(-1, +1), (0, +1), (2, +1), (4, +1), (4, -1), (5, -1), (7, -1), (9, -1)]
  2. Sort events by the position primarily, and by the event type secondarily (+1 before -1 to ensure correct overlapping handling).
  3. Sweep Line Algorithm: Using a sweep line algorithm can efficiently count the number of overlapping ranges by marking the starts and ends of these ranges and then sweeping through these points.

Code

Java
class Solution {
    public int maximumBeauty(int[] nums, int k) {
        List<int[]> events = new ArrayList<>();
        
        // Create events for the start and end of each range
        for (int num : nums) {
            events.add(new int[]{num - k, 1});  // start of the range
            events.add(new int[]{num + k + 1, -1});  // exclusive end of the range
        }
        
        // Sort events based on position, breaking ties by type of event (end before start)
        Collections.sort(events, (a, b) -> (a[0] != b[0]) ? a[0] - b[0] : a[1] - b[1]);
        
        int maxBeauty = 0, current = 0;
        
        // Sweep through events
        for (int[] event : events) {
            current += event[1];
            maxBeauty = Math.max(maxBeauty, current);
        }
        
        return maxBeauty;
    }
}
Python
class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        events = []
        
        # Create events for the start and end of each range
        for num in nums:
            events.append((num - k, 1))  # start of the range
            events.append((num + k + 1, -1))  # exclusive end of the range
        
        # Sort events based on position, breaking ties by type of event (end before start)
        events.sort(key=lambda x: (x[0], x[1]))
        
        max_beauty = 0
        current = 0
        
        # Sweep through events
        for event in events:
            current += event[1]
            max_beauty = max(max_beauty, current)
        
        return max_beauty

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)

Method 2 - Without explicitly creating events and using sliding window

But do we really need to create the events explicitly, given the range of numbers is in fixed length of nums[i] - k, nums[i]+k. Also, in subsequence generally the order matters, for eg. in Longest increasing sequence problem, we want to the sequence in increasing order. But here the subsequence is any element that can be made equal, so ordering doesnt make sense.

Now, once we have ensured that ordering doesn’t help, we can actually sort the array? Why because then we pickup the element and see if it can engulf the element on its left (num -k) and and right (num+k) or not. So, we can apply sliding window of some sort and find the answer.

Lets visualize this with example 1:

nums4612
num - k24-10
num + k6834
We can see that the min element is nums array is 1 and max element is 6.

max_range(1) is 3 and min_range(6) is 4, which don’t overlap ⇨ no matter we replace 1 with it max range value and 6 with its min range value, they wil never be equal.

This can be translated into a condition for a valid window: if min(nums_window) + k >= max(nums_window) - k. Simplified, this condition becomes max(nums_window) - min(nums_window) <= 2 * k.

Here are the steps:

  1. Sort the Array: Sorting helps simplify the problem by allowing us to consider elements in a linear fashion and maintain the order.
  2. Sliding Window Approach: Use two pointers to maintain a window that satisfies the condition max(nums_window) - min(nums_window) <= 2 * k.
  3. Adjust the Window: If the current window does not satisfy the condition, adjust the starting pointer to maintain the valid window.

Code

Java
class Solution {
    public int maximumBeauty(int[] nums, int k) {
        Arrays.sort(nums);
        int start = 0, maxLength = 0;

        for (int end = 0; end < nums.length; end++) {
            // If the window is not valid, move the start pointer forward
            while (nums[end] - nums[start] > 2 * k) {
                start++;
            }
            // The current window [start, end] is valid
            maxLength = Math.max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
}
Python
class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        nums.sort()
        start = 0
        max_length = 0

        for end in range(len(nums)):
            # If the window is not valid, move the start pointer forward
            while nums[end] - nums[start] > 2 * k:
                start += 1
            # The current window [start, end] is valid
            max_length = max(max_length, end - start + 1)
        
        return max_length

Complexity

  • ⏰ Time complexity: O(n log n),  for sorting the array and another O(n) for scanning through the array, resulting in O(n log n) in total.
  • 🧺 Space complexity: O(1)

Dry Run

  1. Sorted nums: [1, 2, 4, 6]
  2. Apply Sliding Window:
    • Initial State: start = 0, maxLength = 0
    • Iterate with end:
      • end = 0: Window [1], 1 - 1 = 0 <= 4 (Valid), maxLength = 1
      • end = 1: Window [1, 2], 2 - 1 = 1 <= 4 (Valid), maxLength = 2
      • end = 2: Window [1, 2, 4], 4 - 1 = 3 <= 4 (Valid), maxLength = 3
      • end = 3: Window [1, 2, 4, 6], 6 - 1 = 5 > 4 (Invalid)
        • Adjust start: start = 1 → Window [2, 4, 6], 6 - 2 = 4 <= 4 (Valid), maxLength = 3