# Partition Array Such That Maximum Difference Is K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/partition-array-such-that-maximum-difference-is-k)
Canonical: https://scaleengineer.com/dsa/problems/partition-array-such-that-maximum-difference-is-k
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` and an integer `k`. You may partition `nums` into one or more **subsequences** such that each element in `nums` appears in **exactly** one of the subsequences.

Return _the **minimum** number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is **at most**_ `k`_._

A **subsequence** is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

**Example 1:**

**Input:** nums = [3,6,1,2,5], k = 2
**Output:** 2
**Explanation:**
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.

**Example 2:**

**Input:** nums = [1,2,3], k = 1
**Output:** 2
**Explanation:**
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].

**Example 3:**

**Input:** nums = [2,2,4,5], k = 0
**Output:** 3
**Explanation:**
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.

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 105`
* `0 <= k <= 105`

# Approaches
## Greedy Approach with Sorting
This approach is based on the key observation that to minimize the number of subsequences, we should make each subsequence as "full" as possible. Since the problem deals with subsequences, the original order of elements does not matter. This allows us to sort the array first. After sorting, we can greedily form subsequences. We start a new subsequence with the smallest available element and include all subsequent elements that fit within the `k` difference constraint.
**Time:** O(N log N), where N is the number of elements in `nums`. The `Arrays.sort()` method takes O(N log N) time. The subsequent single pass through the array takes O(N) time. Thus, the total time complexity is dominated by the sorting step. · **Space:** O(log N) or O(N). The space complexity depends on the implementation of the sorting algorithm used. `Arrays.sort()` in Java for primitive types uses a dual-pivot quicksort, which has an average space complexity of O(log N) for the recursion stack. The worst-case space complexity can be O(N).
**Pros:** The greedy logic is simple and intuitive.; The implementation is straightforward.; It is a general approach that works for any range of numbers, as its performance only depends on the number of elements `N`.
**Cons:** The time complexity is dominated by the sorting step, which is O(N log N). This can be slower than linear-time approaches if the range of values in the array is constrained and allows for faster sorting methods like counting sort.
### Explanation
The core idea is that if we sort the array `nums`, we can process the elements in increasing order. This simplifies the problem of finding the minimum and maximum within a potential subsequence.

We initialize the count of subsequences to 1 and take the first element of the sorted array, `nums[0]`, as the minimum value (`minVal`) for our first subsequence.

We then iterate through the rest of the sorted array. Any element `nums[i]` can be added to the current subsequence as long as `nums[i] - minVal <= k`. Since the array is sorted, we are guaranteed that `nums[i]` will be the maximum element considered so far for the current subsequence, and `minVal` will remain the minimum.

When we encounter an element `nums[j]` such that `nums[j] - minVal > k`, we know that `nums[j]` (and all elements after it, due to the sorted order) cannot belong to the current subsequence. At this point, we must finalize the current subsequence and start a new one. We do this by incrementing our subsequence counter and setting `nums[j]` as the `minVal` for this new subsequence.

This greedy process is repeated until all elements in the sorted array have been placed into a subsequence. The final count is guaranteed to be the minimum number of subsequences required.

```java
import java.util.Arrays;

class Solution {
    public int partitionArray(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int partitions = 1;
        int minVal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - minVal > k) {
                partitions++;
                minVal = nums[i];
            }
        }
        return partitions;
    }
}
```
### Algorithm
- If the input array `nums` is empty, return 0.
- Sort the array `nums` in non-decreasing order.
- Initialize a counter for the number of subsequences, `partitions`, to 1.
- Set the minimum value of the current subsequence, `minVal`, to the first element of the sorted array, `nums[0]`.
- Iterate through the sorted array starting from the second element (`i = 1` to `n-1`):
  - For each element `nums[i]`, check if the difference `nums[i] - minVal` is greater than `k`.
  - If it is, the current element `nums[i]` cannot be part of the current subsequence. We must start a new one.
  - To do this, increment `partitions` and update `minVal` to `nums[i]`.
- After the loop finishes, return the total `partitions` count.

## Greedy Approach with Counting
This approach improves upon the sorting-based method by leveraging the constraint on the range of values in `nums` (`0 <= nums[i] <= 10^5`). Instead of a general-purpose O(N log N) sort, we can use a technique similar to counting sort to achieve a linear time complexity. We use a boolean array to mark the presence of each number and then iterate through this array to greedily form partitions.
**Time:** O(N + M), where N is the number of elements in `nums` and M is the maximum possible value of an element. We iterate through `nums` once to populate the `present` array (O(N)), and then we iterate through the `present` array once (O(M)). · **Space:** O(M), where M is the maximum possible value of an element. We need to store the `present` array of size M+1. Given the constraint `0 <= nums[i] <= 10^5`, M is 100000, so the space is O(10^5), which is constant and acceptable.
**Pros:** Achieves linear time complexity, which is asymptotically optimal.; Faster than the sorting-based approach for the given problem constraints.
**Cons:** This approach requires extra space proportional to the maximum possible value of an element (`M`). If `M` were very large, this approach could be memory-intensive or infeasible.; The approach is less general than sorting; its efficiency is contingent on the values of `nums` being within a manageable range.
### Explanation
This method avoids the O(N log N) sorting cost by using an auxiliary data structure to record which numbers are present in the input array. Given the constraint `0 <= nums[i] <= 10^5`, a boolean array is a very efficient choice for this purpose.

First, we create a boolean array, `present`, of size `100001`. We then make a single pass through the input `nums` array, and for each number `x`, we mark its corresponding index in the `present` array as true (i.e., `present[x] = true`). This gives us a sorted, duplicate-free representation of the numbers in `nums`.

Next, we apply the same greedy strategy as in the sorting approach, but on the `present` array. We iterate through the `present` array with a pointer, `current`. When we find the first `current` for which `present[current]` is true, we know this is the smallest number that needs to be partitioned. We start a new partition (incrementing our count) with `current` as its minimum element. This partition can accommodate any present number up to `current + k`. Therefore, we can skip checking all indices in this range and continue our search for the next present number by jumping our pointer to `current + k + 1`.

This process is repeated until we have scanned the entire `present` array. The final count will be the minimum number of partitions.

```java
class Solution {
    public int partitionArray(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // As per constraints 0 <= nums[i] <= 10^5, we can use a boolean array.
        boolean[] present = new boolean[100001];
        for (int num : nums) {
            present[num] = true;
        }
        
        int partitions = 0;
        int current = 0;
        while (current < present.length) {
            // Find the first number for a new partition
            while (current < present.length && !present[current]) {
                current++;
            }
            
            // If we found a number that exists in the input
            if (current < present.length) {
                partitions++;
                // This partition covers numbers up to current + k.
                // The next search for a new partition should start from current + k + 1.
                current += k + 1;
            }
        }
        
        return partitions;
    }
}
```
### Algorithm
- If `nums` is empty, return 0.
- Given the constraint `0 <= nums[i] <= 10^5`, create a boolean array `present` of size `100001` and initialize all its entries to `false`.
- Iterate through the input array `nums`: for each element `num`, set `present[num] = true`.
- Initialize `partitions = 0` and a pointer `current = 0`.
- Loop while `current` is within the bounds of the `present` array:
  - Find the next available number by advancing `current` until `present[current]` is `true`.
  - If an available number is found (i.e., `current` is still within bounds):
    - This number must start a new partition, so increment `partitions`.
    - This new partition can contain all numbers up to `current + k`. Therefore, we can jump our pointer past this range by setting `current = current + k + 1` to find the start of the next partition.
- Return the final `partitions` count.

# Solutions
### CSharp

```csharp
public class Solution {
    public int PartitionArray(int[] nums, int k) {
        Array.Sort(nums);
        int ans = 1;
        int a = nums[0];
        foreach(int b in nums) {
            if (b - a > k) {
                a = b;
                ans++;
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int partitionArray(int[] nums, int k) {
    Arrays.sort(nums);
    int ans = 1, a = nums[0];
    for (int b : nums) {
      if (b - a > k) {
        a = b;
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int partitionArray(vector<int> &nums, int k) {
    sort(nums.begin(), nums.end());
    int ans = 1, a = nums[0];
    for (int &b : nums) {
      if (b - a > k) {
        a = b;
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int: nums . sort() ans, a = 1, nums[0] for b in nums: if b - a > k: a = b ans += 1 return ans

```