Partition Array Such That Maximum Difference Is K | Leetcode 2294

This video explains Partition Array Such That Maximum Difference Is K using the greedy sorting approach.
----------------------------------------------------------------------------------------------------------------------------------------------------------------
🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: [phone]
---------------------------------------------------------------------------------------------------------------------------------------------------------------

[baljeetsharma]

class Solution {
public:
int partitionArray(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int count=0;
int n=nums.size();
int i=0;
while(i<n){
int cur=nums[i];
count++;
i++;
while(i<n && nums[i]-cur<=k){
i++;
}
}
return count;
}
};

[IshaGarg-qtzd]

I understand the approach very easily.

[bytebardic]

By seeing the thumbnail only. I understand your approach to solving.❤

[StephenMuteti-qx]

I really like the way you approach problems and the easy step-wise explanations you put across daily
Here is an O(N + max(nums)) solution. In the worst case this is O(2N) since max(nums) <= N <= 10^5.

class Solution:
def partitionArray(self, nums: List[int], k: int) -> int:
freq = [0] * (10**5 + 1)
st = float("inf")
MAX = -float("inf")
for num in nums:
freq[num] = 1
st = min(st, num)
MAX = max(MAX, num)
idx = st
ans = 1
while idx <= MAX:
if not freq[idx]:
idx += 1
continue
elif (idx - st) > k:
ans += 1
st = idx
idx += 1
return ans

[sharansc-ht]

Sir once we sort the array wont we lose the original ordering and hence whatever we calculate is just not a subsequence all the time

[sanjanapoptani]

This much I was able to think tooo!! How u r gonna avoid duplicates?

[HARISHKS-pe]

sir if possible do recursion playlist and how to master it like how to do in dp

[rajavignesh]

The "subsequence" part on this question is just a bluff

[sougatamaity]

class Solution:
def partitionArray(self, nums: List[int], k: int) -> int:
nums = list(set(nums))
nums.sort()
cur_group_min_val = nums[0]
gorup_count = 1

for n in nums:
if n > cur_group_min_val + k:
gorup_count += 1
cur_group_min_val = n
return gorup_count

gives o(n) t.c