Partition Array Such That Maximum Difference Is K

main.md

Question

Approach

I first sorted the array so I could group elements more easily. Then I used a greedy strategy, starting from the smallest ungrouped element and including as many consecutive elements as possible within the difference constraint k. I repeated this process until all elements were grouped, incrementing the count of subsequences each time I started a new group.

Implementation

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        nums.sort()
        count = 0
        i = 0
        n = len(nums)
        
        while i < n:
            start = nums[i]
            count += 1
            i += 1
            while i < n and nums[i] - start <= k:
                i += 1
        
        return count

Complexities

• Time: O(n logn)
• Space: O(1)