thanks for explaining. and for those who don't understand why we can not solve this by sorting in ascending order . it is because , if we do sorting in ascending order then for each inversion i.e ( arr [ i ] > arr[ j ] ) we will be counting the number of elements from which the element arr[ j ] is smaller. but we have to count the number of elements which are smaller than the element arr [ i ]. this can be achieved by sorting in descending order.
class Pair{ int element; int index; Pair(int element,int index){ this.element = element; this.index = index; } } class Solution { private void merge(Pair[] elements,int low,int mid,int high,Integer[] counter){ Pair[] temp = new Pair[high-low+1]; int left = low,right = mid+1; int k = 0; while(left
I think , we could also do it by sorting in ascending order but the code would become messy and a lot of cases have to be covered . But if sorted in descending order one can directly get the desired smaller elements clearly
This is a standard Merge sort, so will have the same TC. And yes we are comparing n/2 elements with n/2 elements but for every element, we are not comparing with n/2 other elements
JAVA code class Solution { static class Pair{ int val; int idx; Pair(){ } Pair(int val,int idx){ this.val = val; this.idx = idx; } } int[] constructLowerArray(int[] arr, int n) { // code here // for particular i and j // arr[i] > arr[j] && i
thanks for explaining.
and for those who don't understand why we can not solve this by sorting in ascending order .
it is because ,
if we do sorting in ascending order then for each inversion i.e ( arr [ i ] > arr[ j ] ) we will be counting the number of elements from which the element arr[ j ] is smaller.
but we have to count the number of elements which are smaller than the element arr [ i ]. this can be achieved by sorting in descending
order.
Similar problem- count inversion in an array problem
Please also explain, how to solve this using AVL tree 🙏🏻
Jo main line thi wo toh samjhayi hi nhi
Baaki Puri ramayan samjha di ☕
Really nice explaination, Thanks!! understood and coded your approach in just one go. Keep making such videos.
Thank you Manas :)
Literally great explanation di, thank you. Aapne ye git repo kaise banaya step by step, ek video bana do pls.
class Pair{
int element;
int index;
Pair(int element,int index){
this.element = element;
this.index = index;
}
}
class Solution {
private void merge(Pair[] elements,int low,int mid,int high,Integer[] counter){
Pair[] temp = new Pair[high-low+1];
int left = low,right = mid+1;
int k = 0;
while(left
Well tried🔥
kuch smajh nahi aya
I think you missed base case(i.e. if left>=right return;)
Please make more such videos
Sure :)
Thanks for such a crystal clear explanation.
Thanks Puspendra, glad it was helpful 😊
Superb explanation.
best approach with best explanation
Thanks Lucifer :)
Thanks
Welcome :)
really nice explanation
videos going better!!!
Didn’t realise until this comment, thanks 😊
Didn’t realise until this comment, thanks 😊
Nice clean solution
Thanks Nishant :)
congrats for starting your journey with walmart
Thanks Vikas😊
Thanks for the amazing explanation
Thanks Sai :)
Well Explained, Thanks:)
Thanks Sachin, glad it was helpful :)
☆☞Avl tree pe bhi bna do kripya kr🙏
Zaroor. 👍🏻
Great video!! Could you please explain more on why we are merging in desc order? What if we had used the merging in increasing order?
Because here we want to find the numbers which are smaller than the element after it.
I think , we could also do it by sorting in ascending order but the code would become messy and a lot of cases have to be covered . But if sorted in descending order one can directly get the desired smaller elements clearly
Thank U very much ❣️
Welcome 🙂Glad it helped.
simplest explanation ever
Thank you :)
mostly sound is coming from right earphone .....didi please correct the sound
Yes, working on the issue. 👍🏻
Great work ❤️👍
Thank you :). Please share with your friends and juniors.
noicee explanation .
Glad you liked it🤗
Well explained
Thanks Yogesh🤗
Vry well explained
Thanks🙂
thanks a lot
Welcome Vikas😊
Thank you
Welcome :)
Appreciated 👏
Thank you :). Please share with your friends and juniors.
WHy it is V[i] = temp[i-left] not v[i] = temp[i] ? I am not able to understand this line. Can somebody tell me?
bcz temp is starting with index 0 and V is starting from low ...
thanks!
Welcome Mandeep :)
👍👍
Thanks🙂
Nice Explanation!!!!!!!!!!
pls make a video on avl too..
Okay, will make ASAP🙂
very bad
Why all aayushi 's are toppers 😂😂
Ohh, that needs to be checked on🤗😂
Thanks ayushi, simplest explanation ever (•‿•)
Thanks Ritesh :)
but how is this not n^2-> for n/2 elements ( Left half) you are going through n/2 elements (right half) -> n/2 * n/2 == n^2
This is a standard Merge sort, so will have the same TC. And yes we are comparing n/2 elements with n/2 elements but for every element, we are not comparing with n/2 other elements
@@sauravchandra10 yep gotit
please explain avl tree
Sure will make a video on it :)
@@AyushiSharmaDSA thanks
aapki aawaaz bahut annoying hai
JAVA code
class Solution {
static class Pair{
int val;
int idx;
Pair(){
}
Pair(int val,int idx){
this.val = val;
this.idx = idx;
}
}
int[] constructLowerArray(int[] arr, int n) {
// code here
// for particular i and j
// arr[i] > arr[j] && i
Thanks ayushi, simplest explanation ever (•‿•)
Welcome. Glad it helped :)
Jhut bolta h sala