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

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        # partition array sao cho hiệu lớn nhất bằng với K
        # give nums array and an integer k
        # partitions nums thành 1 hoặc nhiều subsequence (là chuỗi các phần tử có cùng thứ tự với các phần tử lấy từ chuỗi gốc) sao cho mỗi phần tử từ mảng gốc chỉ xuất hiện 1 lần duy nhất trong các mảng subsequences
        # trả về số lượng các subsequences nhỏ nhất cần có sao cho hiệu của phần tử min và phần tử max trong mỗi subsequence <= k

        # 3 6 1 2 5 k = 2
        # [3 1 2] max = 3, min = 1 => diff = 2
        # [6 5] max = 6, min = 5 => diff = 1
        # => Có nhiều nhất 2 mảng subsequence thoả mãn điều kiện 

        # 1 2 3 k = 1
        # [1] [2 3] => có nhiều nhất 2 mảng subsequence thoả mãn điều kiện absolute diff <= k
        # [1 2] [3]

        # keywords: 
        # subsequence:
        # maximum difference in each value:
        nums.sort()
        left = 0
        right = 0
        subsequences_count = 1  # Ít nhất sẽ có một subsequence
        N = len(nums)
        while right < N:
            right += 1
            if right < N and nums[right] - nums[left] > k:
                subsequences_count += 1
                left = right
        return subsequences_count

669