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

[MyrinNew]

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(vectorint>& nums, int k) {
std::bitset100001> 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










✅ Final Thoughts

This problem is a textbook greedy strategy built on sorting:

• Group the values tightly
• Start a new subsequence only when necessary

It's efficient and intuitive once visualized as a scan over sorted data.





Drop a ❤️ if this helped, and follow along for more LeetCode breakdowns and optimizations!


Happy coding! 🚀




More...