<p>You are given an integer array <code>nums</code> and an integer <code>k</code>. You may partition <code>nums</code> into one or more <strong>subsequences</strong> such that each element in <code>nums</code> appears in <strong>exactly</strong> one of the subsequences.</p>

<p>Return <em>the <strong>minimum </strong>number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is <strong>at most</strong> </em><code>k</code><em>.</em></p>

<p>A <strong>subsequence</strong> is a sequence that can be derived from another sequence by deleting some or no elements 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 = [3,6,1,2,5], k = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong>
We can partition nums into the two subsequences [3,1,2] and [6,5].
The difference between the maximum and minimum value in the first subsequence is 3 - 1 = 2.
The difference between the maximum and minimum value in the second subsequence is 6 - 5 = 1.
Since two subsequences were created, we return 2. It can be shown that 2 is the minimum number of subsequences needed.
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,2,3], k = 1
<strong>Output:</strong> 2
<strong>Explanation:</strong>
We can partition nums into the two subsequences [1,2] and [3].
The difference between the maximum and minimum value in the first subsequence is 2 - 1 = 1.
The difference between the maximum and minimum value in the second subsequence is 3 - 3 = 0.
Since two subsequences were created, we return 2. Note that another optimal solution is to partition nums into the two subsequences [1] and [2,3].
</pre>

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

<pre>
<strong>Input:</strong> nums = [2,2,4,5], k = 0
<strong>Output:</strong> 3
<strong>Explanation:</strong>
We can partition nums into the three subsequences [2,2], [4], and [5].
The difference between the maximum and minimum value in the first subsequences is 2 - 2 = 0.
The difference between the maximum and minimum value in the second subsequences is 4 - 4 = 0.
The difference between the maximum and minimum value in the third subsequences is 5 - 5 = 0.
Since three subsequences were created, we return 3. It can be shown that 3 is the minimum number of subsequences needed.
</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] &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= k &lt;= 10<sup>5</sup></code></li>
</ul>

MAX_VAL = 10^5

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        nums.sort()
        curr_min = nums[0]
        num_partitions = 1

        for i in range(1, len(nums)):
            if nums[i] - curr_min > k:
                num_partitions += 1
                curr_min = nums[i]

        return num_partitions
    
    def partitionArray_v1(self, nums: List[int], k: int) -> int:
        keys = [-1] * MAX_VAL
        partitions = []

        for num in nums:
            if keys[num] == -1:
                p = Partition(num, k)
                partitions.append(p)
                partitions_num = len(partitions) - 1

                for i in range(p.ml, p.mr + 1):
                    keys[i] = partitions_num
            else:
                p = partitions[keys[num]]
                if not p.is_fixed:
                    if num < p.l:
                        diff = p.l - num
                        p.l = num
                        old_mr = p.mr
                        p.mr -= diff
                        
                        if p.ml == p.l:
                            p.is_fixed = True
                        
                        for j in range(old_mr, p.mr, -1):
                            keys[j] = -1
                    elif num > p.r:
                        diff = num - p.r
                        p.r = num
                        old_ml = p.ml
                        p.ml += diff
                        
                        if p.mr == p.r:
                            p.is_fixed = True
                        
                        for j in range(old_ml, p.ml):
                            keys[j] = -1
            
            print(keys[:10])

        print(partitions) 
        return len(partitions)
        

class Partition:
    def __init__(self, val: int, k: int):
        self.l = val
        self.r = val
        self.ml = max(val - k, 0)
        self.mr = min(val + k, MAX_VAL)
        self.is_fixed = False
    
    def __repr__(self):
        return f"P(l={self.l}, r={self.r}, ml={self.ml}, mr={self.mr}, is_fixed={self.is_fixed})"

31000