Use the Fewest Value-Range-Bounded Subsequences
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Partition all occurrences of `nums` into subsequences, using each occurrence exactly once. Within each subsequence, the largest value minus the smallest must be at most k. Return the smallest number of subsequences; no actual partition is returned.
```cpp
class Solution {
public:
int partitionArray(vector<int>& nums, int k);
};
```
### Examples
**Example 1:**
```text
Input: nums = [8,1,3,7], k = 2
Output: 2
Explanation: Use groups containing values {1,3} and {7,8}. Each group can be read as a subsequence in original order, and each range is at most 2.
```
**Example 2:**
```text
Input: nums = [4,4,9], k = 0
Output: 2
Explanation: The two occurrences of 4 can share a group. The value 9 needs a separate group because k is zero.
```
### Constraints
- `1 <= nums.length <= 100000`.
- `0 <= nums[i], k <= 100000`.
### Clarifying Questions
- Must groups be contiguous? No; they are subsequences, so elements may be skipped while preserving their original order.
- Can a value occur in more than one group? Each occurrence belongs to exactly one group. Equal occurrences may share a group.
- Is equality at the limit allowed? Yes; a range of exactly `k` is valid.
- Must the groups be returned? No, only their minimum count.
```hint Check the boundary
Check how the rule treats equal values when `k = 0`.
```
Overview: Partition an array into the fewest subsequences whose maximum and minimum differ by at most k, using every occurrence exactly once.
