Max Chunks To Make Sorted | Leetcode 769

[@umeshkaushik710]

00:08 Understanding the Max Chunks To Make Sorted problem on LeetCode.
02:09 Understanding partitioning for sorting in Leetcode 769.
04:09 Determining valid partition points in a sorted array.
06:16 Understanding partition points for sorting permutations.
08:17 Maximize partitions based on anagram groups effectively.
10:17 Partitioning an array requires max left to be less than min right.
12:24 Understanding block creation for array partitioning based on maximum values.
14:26 Creating partitions by tracking maximum values in the array.
16:23 Counting anagrams through an efficient linear time approach.

[@techdose4u]

👌🏽

[@LinhHoang-ml1qo]

Thank you teacher, your explaination is very excellent to approach!

[@techdose4u]

welcome :)

[@rohanp7051]

Another intuitive approach is to compare the prefix sums of the given array and the fully sorted array at each index. If they are the same, it means a new chunk can be created.

[@techdose4u]

yepp :)

[@nitian__himanshu3570]

Thank you sir !!!!!!!!!!!!!!!!!!!!!!!!!!
Understood 100%

[@techdose4u]

great 👍🏼

[@ayushdubey5003]

thanks sir 🤗
small request can you please provide a small post or a code block in which we can refer the brute force approach just to the understand in more depth about the solution ....

[@techdose4u]

that would be too much for me 🥵
You can try and share your issue if you get

[@bharat_india12]

class Solution {
public:
int maxChunksToSorted(vector& arr) {
int chunk=0;
int sum1=0,sum2=0;
int i=0;
for(auto x:arr){
sum1+=i;
sum2+=x;
if(sum1==sum2){
chunk++;
}
i++;
}
return chunk;

}
};

[@techdose4u]

👍🏼

[@sailendrachettri8521]

Thank you sir :)

[@techdose4u]

welcome :)

[@beinghappy9223]

Excellent explanation

[@techdose4u]

thanks :)

[@manishgupta8057]

I really liked this video❤

[@techdose4u]

nice :)

[@eprithvikushwah4754]

Using max-heap
class Solution {
public:
int maxChunksToSorted(vector& arr) {
int ans = 0 ;
int val = 0;
priority_queue pq;
for(int i= 0 ; i < arr.size(); i++){
pq.push(arr[i]);
if(!pq.empty() && val==pq.top()){
ans++;
while(pq.empty()) pq.pop();
}
val++;
}
return ans;
}
};

[@subratamandal2924]

Min-heap

[@indiannerd1189]

sahi hai bhai...bas while(pq.empty()) ke jagah while(!pq.empty()) aayega shyd

[@eprithvikushwah4754]

@@subratamandal2924 its max-heap

[@eprithvikushwah4754]

@@subratamandal2924 yaa my bad !