# Maximum Beauty of an Array After Applying Operation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-beauty-of-an-array-after-applying-operation)
Canonical: https://scaleengineer.com/dsa/problems/maximum-beauty-of-an-array-after-applying-operation
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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.

**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`

# Approaches
## Brute Force with Sorting
The core idea is that a group of numbers can be made equal if the difference between the maximum and minimum number in the group is at most `2k`. To simplify finding such groups, we can first sort the array. After sorting, any such group will form a contiguous subarray. The problem then becomes finding the longest subarray `nums[i...j]` where `nums[j] - nums[i] <= 2k`. This approach iterates through all possible subarrays of the sorted array, checks the condition, and keeps track of the maximum length found.
**Time:** O(N^2), where N is the number of elements in `nums`. Sorting takes O(N log N), but the nested loops to check all subarrays take O(N^2), which dominates the complexity. · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm used. This space is for the recursion stack or auxiliary array for sorting.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** Highly inefficient for large input sizes due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error on competitive programming platforms for the given constraints.
### Explanation
This approach begins by sorting the input array `nums`. This is a crucial step because it allows us to easily find the minimum and maximum elements of any subarray. For a subarray starting at index `i` and ending at index `j` in a sorted array, `nums[i]` is the minimum and `nums[j]` is the maximum. We then use two nested loops to examine every possible contiguous subarray. The outer loop selects a starting element `nums[i]`, and the inner loop extends the subarray by including subsequent elements `nums[j]`. For each subarray, we check if `nums[j] - nums[i] <= 2 * k`. If this condition holds, it means all elements in this subarray can be transformed into a single common value, and we update our maximum beauty with the current subarray's length. If the condition fails, we can stop extending the current subarray and move to the next starting element, as the array is sorted.

```java
import java.util.Arrays;

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int maxBeauty = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] - nums[i] <= 2 * k) {
                    maxBeauty = Math.max(maxBeauty, j - i + 1);
                } else {
                    break; // Optimization
                }
            }
        }
        return maxBeauty;
    }
}
```
### Algorithm
1. Sort the input array `nums` in non-decreasing order.
2. Initialize a variable `maxBeauty` to 0.
3. Use a nested loop to iterate through all possible subarrays. The outer loop with index `i` defines the start of the subarray, and the inner loop with index `j` defines the end.
4. For each subarray `nums[i...j]`, the minimum element is `nums[i]` and the maximum is `nums[j]`.
5. Check if the condition `nums[j] - nums[i] <= 2 * k` is met.
6. If it is, the subarray's length `j - i + 1` is a potential answer. Update `maxBeauty = max(maxBeauty, j - i + 1)`.
7. If the condition is not met, we can break the inner loop as any further element `nums[j+1]` will also not satisfy the condition due to the sorted nature of the array.
8. After checking all possible starting points `i`, `maxBeauty` will hold the maximum possible beauty.

## Sorting and Sliding Window
This approach significantly improves upon the brute-force method by using a more efficient technique to find the longest valid subarray. After sorting the array, we can use a sliding window, defined by two pointers `left` and `right`. We expand the window by moving the `right` pointer and shrink it by moving the `left` pointer whenever the condition `nums[right] - nums[left] <= 2k` is violated. This way, we find the longest valid subarray in a single pass over the sorted array, making it much faster.
**Time:** O(N log N), dominated by the initial sorting of the array. The subsequent sliding window scan takes O(N) time. · **Space:** O(log N) or O(N), for the space required by the sorting algorithm.
**Pros:** Efficient and passes the time limits for the given constraints.; It's a standard, elegant, and easy-to-reason-about solution for this class of problems.
**Cons:** The overall performance is bottlenecked by the initial sorting step, making it slightly less optimal than non-sorting-based approaches for specific data distributions.
### Explanation
The sliding window technique is a powerful tool for problems involving finding an optimal subarray or substring. After sorting `nums`, we maintain a 'window' of elements `nums[left...right]`. The key idea is to efficiently expand and shrink this window. We iterate through the array using a `right` pointer. For each `nums[right]`, we add it to our window. Then, we check if the window's property (`nums[right] - nums[left] <= 2 * k`) is maintained. If not, the window is too wide, so we slide the window forward by incrementing the `left` pointer. We repeat this until the window is valid again. At each step, after ensuring the window is valid, we calculate its size and update our `maxBeauty`. Since both `left` and `right` pointers only move forward, each element is visited at most twice, leading to a linear time complexity for the scan after sorting.

```java
import java.util.Arrays;

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int left = 0;
        int maxBeauty = 0;
        for (int right = 0; right < n; right++) {
            while (nums[right] - nums[left] > 2 * k) {
                left++;
            }
            maxBeauty = Math.max(maxBeauty, right - left + 1);
        }
        return maxBeauty;
    }
}
```
### Algorithm
1. Sort the input array `nums`.
2. Initialize two pointers, `left = 0` and `right = 0`, representing the start and end of a sliding window.
3. Initialize `maxBeauty = 0`.
4. Iterate with the `right` pointer from `0` to `nums.length - 1` to expand the window.
5. Inside the loop, check if the window is valid: `nums[right] - nums[left] <= 2 * k`.
6. If the window is invalid (`nums[right] - nums[left] > 2 * k`), shrink the window from the left by incrementing the `left` pointer until the condition is met again.
7. Once the window `[left, right]` is valid, its length is `right - left + 1`. Update `maxBeauty = max(maxBeauty, right - left + 1)`.
8. After the `right` pointer has traversed the entire array, return `maxBeauty`.

## Sweep-line Algorithm with Difference Array
This approach rephrases the problem into a classic interval problem: for each number `num`, it can be transformed into any integer in the range `[num - k, num + k]`. We want to find an integer `x` that is included in the maximum number of these ranges. This can be solved efficiently using a sweep-line algorithm. We use a difference array to mark the start (`+1`) and end (`-1`) of each interval. By taking a prefix sum of this array, we can find the point of maximum overlap, which corresponds to the maximum beauty.
**Time:** O(N + V), where N is the number of elements and V is the range of values. O(N) to populate the difference array and O(V) to find the maximum overlap. This is faster than O(N log N) for the given constraints. · **Space:** O(V), where V is the range of values from `min(num-k)` to `max(num+k)`. Given the constraints, this is O(max(nums) + 2k), which is a constant amount of space (approx. 3*10^5).
**Pros:** Asymptotically the fastest solution for the given constraints, as it avoids the O(N log N) sorting step.; Operates in time linear to the number of elements and the range of values.
**Cons:** Requires a large auxiliary array, which might lead to high memory usage if the range of values is very large.; Can be slightly more complex to implement correctly due to the need for coordinate offsetting.
### Explanation
Instead of sorting the input array, this method focuses on the ranges of possible values. Each `nums[i]` generates a range `[nums[i] - k, nums[i] + k]`. We want to find a point with the highest overlap among all these ranges. The sweep-line algorithm is perfect for this. We create a large array, let's call it `line`, that represents the number line. Since `num - k` can be negative, we apply an offset to all coordinates to map them to valid array indices. For each number `num`, we increment `line` at the index corresponding to `num - k` and decrement it at the index for `num + k + 1`. This way, `line[i]` stores the net change in the number of active intervals at point `i`. Finally, we iterate through the `line` array, accumulating the values. The running sum at any point `i` gives the total number of intervals covering `i`. The maximum running sum we encounter is the maximum beauty.

```java
class Solution {
    public int maximumBeauty(int[] nums, int k) {
        // The values for our sweep line can range from num-k to num+k.
        // With num, k <= 10^5, min(num-k) = -10^5, max(num+k) = 2*10^5.
        // We use an offset to map these to non-negative array indices.
        int offset = 100001;
        // Size needs to accommodate max(num+k+1) + offset, which is roughly 3*10^5.
        int[] line = new int[300003];

        for (int num : nums) {
            int start = num - k + offset;
            int end = num + k + offset;
            line[start]++;
            if (end + 1 < line.length) {
                line[end + 1]--;
            }
        }

        int maxBeauty = 0;
        int currentBeauty = 0;
        for (int count : line) {
            currentBeauty += count;
            maxBeauty = Math.max(maxBeauty, currentBeauty);
        }

        return maxBeauty;
    }
}
```
### Algorithm
1. Realize the problem is equivalent to finding a point on the number line covered by the maximum number of intervals `[num - k, num + k]`.
2. Use a difference array (or sweep-line array), `line`, to store the changes in overlap count. To handle potentially negative start points (`num - k`), use an offset to map all coordinates to non-negative indices.
3. The range of coordinates is from `min(num-k)` to `max(num+k)`. An offset of `k` or slightly more is sufficient. The array size should accommodate `max(num) + 2k + 2`.
4. For each `num` in `nums`, calculate its interval `[start, end] = [num - k, num + k]`. Apply the offset to these coordinates.
5. Increment the count at the start of the interval: `line[start + offset]++`.
6. Decrement the count just after the end of the interval: `line[end + 1 + offset]--`.
7. After processing all numbers, iterate through the `line` array, calculating a running prefix sum (`currentBeauty`).
8. The maximum value of this running sum is the answer, `maxBeauty`.

# Solutions
### Java

```java
class Solution {
public
  int maximumBeauty(int[] nums, int k) {
    int m = Arrays.stream(nums).max().getAsInt() + k * 2 + 2;
    int[] d = new int[m];
    for (int x : nums) {
      d[x]++;
      d[x + k * 2 + 1]--;
    }
    int ans = 0, s = 0;
    for (int x : d) {
      s += x;
      ans = Math.max(ans, s);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumBeauty(vector<int> &nums, int k) {
    int m = *max_element(nums.begin(), nums.end()) + k * 2 + 2;
    vector<int> d(m);
    for (int x : nums) {
      d[x]++;
      d[x + k * 2 + 1]--;
    }
    int ans = 0, s = 0;
    for (int x : d) {
      s += x;
      ans = max(ans, s);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int: m = max(nums) + k * 2 + 2 d = [0] * m for x in nums: d[x] += 1 d[x + k * 2 + 1] -= 1 ans = s = 0 for x in d: s += x ans = max(ans, s) return ans

```