Count Inversions | GFG Count Inversions Solution | Seaching and Sorting
Vložit
- čas přidán 10. 05. 2021
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Manisha ma'am is a legend. She gave such a wonderful explanation!
i wasted my whole day to understand this problem but after that i luckily found this solution and believe me i understood 100%
what a great explanation by mam
thankyou so much mam
I was frustrating to understand merge sort, then I saw this and every thing is clear. Thank you
Thankyou
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
I literally wasted an hour to understand gfg code but when I watch your solution,
I just get in one click simplest code &
explanation is🙌
literally great explanation ..lot better than anyone..
the way you approach the question is by far the best in internet.
In love with pepcoding these days.
She is a DIVA so beautifully explained. Keep doing the good work and helping students like me
Your explanting style is soo sooo soooo good and please put video on recursion and how to do though process on recursion please make video.
This is the best ever explaination ever for this
Great Great Explanation. Pepcoding is the reason i love doing problem solving.
had seen many videos but was not able to understand this concept and this video made me understand in a single shot... kudos to the teaching style..... keep growing pepcoding!!!!!
Kitna accha padhati ho aap..see, zero dislikes!
Thanks for very easy explanation of using merge sort to calculate inversion
I guarantee this is the best ever explanation 😃 thanks pepcoding
Hats off!! For the level of explanation 🙏🙏
great ...again i am seeing you as my trainer
You made it easy. Great Explanation !!!
thank you so much for a soothing explanation. Keep it up Pepcoding.
Great explaination mam i have watched a lot of videos before but couldn't understand the code but finally this video is very helpful for me ....Love the way you explain❤️❤️👍👍
This channel deserve millions of subs.....awesome ♥
Your explanation always outstanding 🙏🔥
Pepcoding never dissapoints!!!Awesome explanation!!
Glad you liked it
For better experience and well organised content sign up on nados.io
Don't forget to follow us on Instagram instagram.com/pepcoding/
Thank you for this! really great explanation.
Amazing explanation !! thank you so much!!!
better,better,better than many!.Thanku mam
This code failed to pass tetscases on gfg
Thanks a lot...really great explanation
great mem i love it your exprenation of code..
kya smjhaya h .....behtareen
Best explanation of count inversions. Great!
Glad it was helpful!
Keep learning.
And for better experience and well organised content visit nados.pepcoding.com
plz you make more video. much clear explanation
pepcoding always rocks , thnxx for this .
If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
sir ye recursive algo hai aur humne global variable ka use kiya hai interview mei problem to nhi hogi na iss method se
Best Explaination !!
Thanks. it was the most difficult question
Excellent Video!
Your explanation is very clear and outstanding.
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
So good... thanks a ton....
Awesome !! 🔥
Best explanation 👍
Shandarrrr Explanation
Thankyou ma'am!!
thankyou
you are amazing
Clear and excellent explaination
Thank you so much and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
mindblowing
Excellent explanation manisha ma'am!!
Glad you liked it For better experience and well organised content sign up on nados.io and start learning.
Best explanation...loved it 💫
Glad you liked it:) To watch more content like nados.pepcoding.com
really appreciate
it help a lot .....almost die before came here
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
Best ma'am best
Nice..
Thankyou for this! really helped.
Glad it helped and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
@@Pepcoding sure 👍
will this videos solution work for 1,9,6,4,5 ? i tried but it doesnt show correct ans it says 3 but answer is 5
You are a legend.
Thankyou for your compliment.
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
Such a wonderful explanation... thank you mam.. _/\_
Great video! Plz also upload the video for count of smaller nodes after self. That is also done by mergesort
As soon as possible
will this videos solution work for 1,9,6,4,5 ? i tried but it doesnt show correct ans it says 3 but answer is 5
@@yoyocontact5181 yes
👍👍👍👍
nice and easy
very good explanationn
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
Thanks🙏✨💯
You’re welcome 😊
simple code in 10 lines
def count_inversions(a):
res = 0
counts = [0]*(len(a)+1)
rank = { v : i+1 for i, v in enumerate(sorted(a)) }
for x in reversed(a):
i = rank[x] - 1
while i:
res += counts[i]
i -= i & -i
i = rank[x]
while i
thik h jiii
Will this work for array having duplicates values
yup ,inversion just means a ele on index i>index j ele on right ,duplicates won't matter here , 4 5 4 4,here 5-4 and 5-4 are making two inversion
Hatts off 🙏
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
🙌👌⭐
If this que comes up in the interview and if he asks have u done this question first when i try to explain him this method after explaining the brute force method then what i should say?Bec merge sort method is not intuitive..concept used is intuitive but method is not?How should one proceed in such scenerio?
will this videos solution work for 1,9,6,4,5 ? i tried but it doesnt show correct ans it says 3 but answer is 5 , bro can you please try
@@freshcontent3729 yes it is working
we can also solve it using fenwick tree....
At geeksForGeeks portal at different test cases this solution is not giving the desired result.
Can you please explain me how to write 28 and 29 line of code in c++...plz help me
Use vector instead of array in cpp, vector has a size function and it is easy to use.
will this videos solution work for 1,9,6,4,5 ? i tried but it doesnt show correct ans it says 3 but answer is 5
It will work, output is 5.
aapke white board ka ky name h
plzz reply
Openboard
Thanks Mam :-)
Hope you like the video, for better experience and well organised content visit - nados.io
can we write code in c++ by returning array ?
Yes you can
int* fun() {} , you have to receive this like int*arr = fun();
visit nados.pepcoding.com; post your query, there our community will help you out.
22:48
493. Reverse Pairs
isi way se leetcode 493 kia pr tle aa rha hai
code kr do share idhr
it took me 1 hr to understand why this video has got zero dislikes
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
@@Pepcoding and onemore thing i wanted to ask im currently in begin of 3rd year(B.tech) will i be able to learn every thing in 1 year and get product based companies
why always pepcoding...
Your explanation is good. However, returning the array from merge sort functions is not good.
Also taking global static variables is also not good. Ideally, a function should return the answer.
A good company's interviewer won't accept this.
So this could be the code without any global static variable:
class Solution {
int getInversionCount(int[] array) {
return mergeSort(array, 0, array.length - 1);
}
private int mergeSort(int[] array, int low, int high){
int count = 0;
if(low < high){
int mid = low + (high - low) / 2;
count += mergeSort(array, low, mid);
count += mergeSort(array, mid + 1, high);
count += merge(array, low, mid, high);
}
return count;
}
private int merge(int array[], int low, int mid, int high){
int inversion = 0;
int tempArray[] = new int[high - low + 1];
int index1 = low;
int index2 = mid + 1;
int arr1Size = mid + 1;
int arr2Size = high + 1;
int mergedArrIndex = 0;
while(index1 < arr1Size && index2 < arr2Size){
if(array[index1]
very good explanation
thank you @pepcoding team for such a amazing video
Glad you liked it!
For better experience, visit nados.io, where you will get well curated content and career opportunities.
sir ye recursive algo hai aur humne global variable ka use kiya hai interview mei problem to nhi hogi na iss method se
Sir kon h is vdo m😂😂
Thankyou... Really awesome explanation
Thank you so much and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
will this videos solution work for 1,9,6,4,5 ? i tried but it doesnt show correct ans it says 3 but answer is 5
@@yoyocontact5181
class Solution
{
// arr[]: Input Array
// N : Size of the Array arr[]
//Function to count inversions in the array.
private static long count=0;
static long inversionCount(long arr[], long N)
{
// Your Code Here
long arr1[]=mergeSort(arr,0,arr.length-1);
//System.out.println(Arrays.toString(arr1));
return count;
}
private static long[] mergeSort(long arr[],long left,long right){
if(left==right){
long[] a=new long[1];
a[0]=arr[(int)left];
return a;
}
long mid=left+(right-left)/2;
long leftArr[]=mergeSort(arr,left,mid);
long rightArr[]=mergeSort(arr,mid+1,right);
long mergedArr[]=merge(leftArr,rightArr);
return mergedArr;
}
private static long[] merge(long leftA[],long rightA[]){
long[] mArr=new long[leftA.length+rightA.length];
int i=0,j=0,k=0;
while(i