<p>You are given a <strong>0-indexed</strong> array <code>nums</code> and a <strong>non-negative</strong> integer <code>k</code>.</p>

<p>In one operation, you can do the following:</p>

<ul>
	<li>Choose an index <code>i</code> that <strong>hasn&#39;t been chosen before</strong> from the range <code>[0, nums.length - 1]</code>.</li>
	<li>Replace <code>nums[i]</code> with any integer from the range <code>[nums[i] - k, nums[i] + k]</code>.</li>
</ul>

<p>The <strong>beauty</strong> of the array is the length of the longest subsequence consisting of equal elements.</p>

<p>Return <em>the <strong>maximum</strong> possible beauty of the array </em><code>nums</code><em> after applying the operation any number of times.</em></p>

<p><strong>Note</strong> that you can apply the operation to each index <strong>only once</strong>.</p>

<p>A&nbsp;<strong>subsequence</strong> 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.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,6,1,2], k = 2
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1,1], k = 10
<strong>Output:</strong> 4
<strong>Explanation:</strong> In this example we don&#39;t have to apply any operations.
The beauty of the array nums is 4 (whole array).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i], k &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        # nums length of 10^5
        # k: 10^5
        # nums[i] and k are less than 10^5

        # the number that the most amount of nums[i] can be replaced to
        # number line method

        # [nums[i] - k, nums[i] + k]
        # for every number in nums: O(N)
            # construct the range: [nums[i] - k, nums[i] + k], make a hashmap and count the occurences O(2N)
        # time complexity: O(n^2) space complexity O(N)
        # We would find the key in the hashmap with the highest value / occurrences


        # number line array goes up to the max in nums
        # for every number in nums:
            # we going to create intervals that represent all the values that nums[i] could take
        m = max(nums) + k
        number_line = [0] * (m + 1) # number_line[max] it's  still valid
        for i in range(len(nums)): # O(N) n = length of nums
            start = max(nums[i] - k, 0) # nums[i] = 2, k = 3, technically the start is -1, but we want to bound it at 0
            number_line[start] += 1
            end = nums[i] + k + 1
            if end < len(number_line): # then it's out of our interest, we don't need to put a negative
                number_line[end] -= 1
            # |---3--|   
        # [0, 1, 0, 0, -1] -> [1, 5]
        # nums[i] = 3, and k = 1 -> [3 - 1, 3 + 1] = [2, 5)
        beauty = 0
        counter = 0
        for i in range(len(number_line)): # O(M) M = max(nums) + k, and that is at most 2 * 10^5, space complexity : O(M)
            counter += number_line[i] # if number_line > 0, that means we found the reach of a number, number_line < 0, that means we have left the reach of a number, so we're subtracting
            beauty = max(counter, beauty)
        # the way we count the beauty:
        # now our number line, at each number will have an integer that represents the count of numbers that can reach that integer, so we're going to accumulate that count and keep a running max
        # iterate through running line and keep a max

        return beauty

    # Test case: [4, 6, 1, 2], k = 2
    # [2, 0, 1, 0, 0, -1, 0, -1, 0]
953