👓Beginner-Friendly Guide "Partition Array Such That Maximum Difference Is K" LeetCode 2294 (C++ | Python | JavaScript)

#programming #cpp #javascript #python

LeetCode 2294 | Medium | Greedy + Sorting

🧠 Problem Summary

You are given:

An integer array nums
An integer k

You must partition nums into one or more subsequences such that:

Every element appears in exactly one subsequence
In each subsequence, the difference between the maximum and minimum value is at most k

Return the minimum number of subsequences needed to satisfy the above condition.

🧩 Intuition

To minimize the number of subsequences, we should group as many nearby values as possible within each group while maintaining the max difference ≤ k.

Key Insight:

If you sort the array, then every group must start at some element start, and include as many consecutive numbers as possible while current - start ≤ k.

This naturally leads to a greedy approach.

🧮 C++ Code

class Solution {
public:
    int partitionArray(vector<int>& nums, int k) {
        std::bitset<100001> exists;
        int minV = nums[0], maxV = nums[0];

        for (int v : nums) {
            minV = min(minV, v);
            maxV = max(maxV, v);
            exists[v] = true;
        }

        int seq = 1;
        int start = minV;

        for (int v = minV; v <= maxV; ++v) {
            if (exists[v]) {
                if (v - start > k) {
                    start = v;
                    ++seq;
                }
            }
        }

        return seq;
    }
};

📝 Key Notes:

We track which values exist using a bitset (space-efficient).
The loop from minV to maxV simulates grouping valid adjacent values.
Whenever the difference exceeds k, we start a new subsequence.

Time Complexity: O(max(nums))
Space Complexity: O(1) (fixed-size bitset)

💻 JavaScript Code

var partitionArray = function(nums, k) {
    nums.sort((a, b) => a - b);
    let count = 1;
    let start = nums[0];

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] - start > k) {
            count++;
            start = nums[i];
        }
    }

    return count;
};

🔍 Explanation:

Sort the array so that nearby values are grouped.
Track the start of the current subsequence.
When a value exceeds the allowed difference, start a new subsequence.

🐍 Python Code

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

        for num in nums:
            if num - start > k:
                count += 1
                start = num

        return count