< Back





2294. Partition Array Such That Maximum Difference Is K

Another greedy problem, but we recognize it's greedy after we determine that we need to sort the
array. We need to create a subsequence of numbers, so it's not really a sliding window because that
would be a subarry or substring. Since we can reorder the numbers in any way we please, sorting them
makes this much easier to track the max and min of a subsequence, otherwise, a solution would be
convoluted and require like O(n^2) or something.

Now that we're sorted, we'll maintain a leftmost pointer, l, and a rightmost pointer, r, and take
the difference of them at each round. By default, our answer starts at 1 because that's the minimum
number of subsequences we can create. If the difference between the two pointers is greater than k,
we increment our answer and move the left pointer to the right pointer. This is because we can't
create a subsequence with a difference greater than k, so we need to start a new one.

The solution is as follows:


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

        for r in range(len(nums)):
            if nums[r] - nums[l] > k:
                ans += 1
                l = r

        return ans


_ Time Complexity:

  O(n log(n)) - We have to sort the array.

_ Space Complexity:

  O(n) - Python sorting uses O(n) space.