Counting inversions in an array

This video explains how to find number of inversions in an array using 3 methods. The video first explains what is inversion and its conditions followed by solutions. The first solution is a brute-force method. The second solution is based on merge sort technique. The third technique is based on multiset using c++ STL. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[@AarshSharma]

I always thought it was an extremely hard problem. This explanation made it look so easy. Thanks.

[@techdose4u]

Welcome :)

[@ShivamSingh-me1nb]

Best explanation I have seen so far

[@techdose4u]

Thanks :)

[@tanayvartak4362]

This is the best video to understand the merge sort method for count inversion. Explanation was really very clear and straight forward. Thanks a lot 😊

[@techdose4u]

Welcome :)

[@VikasKumar-nb2pn]

One best thing is that
U always take tough example which explain all the possible situation....
Awesome explanation..
Thanks sir...

[@techdose4u]

Welcome :)

[@SinghFlex]

Clear and crisp explanation. Thankyou for creating such a good stuff.

[@techdose4u]

Welcome :)

[@deepakprajapati5064]

this is called explanation with good knowledge

[@jarno9340]

Very clear explained! Thanks. That's what I needed!

[@techdose4u]

Welcome :)

[@kaushikramabhotla4635]

The best explanation for this problem 👏 👌

[@sagargupta1615]

you are really tech dose....ur explanation is very good.

[@sukritkapil2562]

Crystal clear explanation. Thanks a lot!!

[@techdose4u]

Welcome :)

[@b9944236]

Picture explains everything, thanks.

[@shubhammishra3783]

very clear explanation thank you

[@mansiagrawal4039]

After seeing this video this problem became a very easy problem. Thank you

[@techdose4u]

Welcome :)

[@AyushJain-ot9yv]

Best Channel Ever! You are doing good work. :)

[@techdose4u]

Thanks :)

[@vasujain1970]

This was an amazing explanation! Thank you!

[@techdose4u]

Welcome :)

[@patilsoham]

Helped a lot!
Thank you!

[@techdose4u]

Welcome :)

[@javadsayevand8273]

The Best explanation ever... 🙏🙏🙏

[@techdose4u]

Thanks

[@RaGa_BABA]

bhai 1 number....I always prefer your video when I get stuck on any problem.

[@techdose4u]

Nice :)

[@changjeffreysinto3872]

Clear explanation dude

[@sunwado]

Precise and too the point :)

[@techdose4u]

Thanks

[@praveenchouhan6388]

BEST EXPLAINATION SEEN SO FAR, UR VIDEO IS GENERALLY THE LAST VIDEO I SEE BECAUSE IT MAKES ALL CLEAR, PLEASE CONSIDER CAPS AS A SALUTE TO YOU NOT HARSH!!!!!!!!!!!!!

[@techdose4u]

Nice to hear this :)

[@PizzaGamingTheReal]

Thanks man, explaining step by step is the clearest method. Now I got this algorithm.

[@techdose4u]

Nice 😃

[@divyareddy7622]

thankk you bhaiya!! amazing

[@elizabethr5161]

Crystal clear explanation..

[@techdose4u]

Thanks :)

[@jpakash1999]

You are genius :-) Thank You

[@techdose4u]

😅 Welcome

[@shobhitbajaj9667]

Wow what a great explanation 👍

[@techdose4u]

Thanks

[@ayushkawatra7436]

really helped a lot

[@paragroy5359]

Nice explanation sir....you are doing a great job

[@techdose4u]

Thanks :)

[@Joyddep]

Great explanation!

[@techdose4u]

Thanks

[@vikashkumarchaurasia1299]

very nice explaination ever seen .thanks a lot

[@techdose4u]

Welcome

[@todo1553]

Thanks for the explanation

[@techdose4u]

Welcome

[@sharuk3545]

Awesome 👍

[@sainathsingineedi2922]

I think it's O(nlogn) for Fenwick trees too correct me if I'm wrong
O(n) traversing
-> O(logn) for quering the sum
-> O(logn) for updating
Overall O(nlogn)

[@priyasharma3549]

thank you so much

[@kollivenkatamadhukar5059]

Excellent Explanation

[@techdose4u]

Thanks

[@amit36666]

In the 3rd method, the std::distance time complexity on std::multiset is O(n), so the overall time complexity is O(n^2)

[@abhisheks8017]

I don’t know c++, but Java has treeset which can be used to solve the problem in O(n logn). We cannot achieve this time complexity using hash set. Tree set basically is an implementation of red black trees. Also using fenwick trees will take O(n log n) instead of O(n) as told in the video.

[@aeroabrar_31]

Hey Man!
How to access the indexOf an elem in TreeSet ..?

[@TJVargasS]

@@aeroabrar_31 treeSet.headSet().size

[@vipulkrishna19]

very very good explanation

[@techdose4u]

Thanks :)

[@tusharkumar3277]

nice video ,really helpful

[@techdose4u]

Thanks :)

[@jakubfraczek1208]

THANK YOU SO MUUUUUUUUCH

[@diptamoymitra7486]

Atlast understood ❤❤

[@techdose4u]

Great :)

[@ShreyaSingh-vr9qi]

Nice explaination, BIT method too (:

[@techdose4u]

Okay

[@siddhantsingh8721]

best explanation

[@techdose4u]

Glad you think so!

[@22.jananidileepan44]

Superb

[@excessreactant9045]

Thanks for this my book didnt show this well

[@techdose4u]

😁

[@SudhanshuKumar-jl8iw]

great explanation

[@techdose4u]

Thanks

[@dayanandraut5660]

merge sort technique is the best for this problem

[@anitasingh-jw1lc]

merge sort is very understandi all us

[@_PAYALGAIKWAD]

thnx a lot

[@anjana1700]

Awesome Sir!
Sir please make a video on BIT also

[@techdose4u]

Yea...will make it.

[@KathanShah03]

Thank You for the explanation. Where can I find Method - 5 explanation?

[@biswamohandwari6460]

Man I got understood everything, I saw there

[@techdose4u]

Nice :)

[@ranjanpanda2586]

RIP english

[@harshitagrawal789]

I think the time complexity of upper_bound in a multiset is log(n) so the third method can be O(nlogn). Not sure though!

[@kunalpahwa7720]

@techdose can you explain the complexity of the 3rd method?

[@softwaredevelopment4392]

Ya exactly I have the same doubt ..

[@adelikomtyagi5324]

He used distance function which take O(n) time

[@kanishkagupta5801]

Could you please provide its code. I am not able to find it anywhere

[@kashishsharma6809]

by BIT method also it takes O(nlogN) where N is maximum no present in array. if anyone trying BIT method check for method where there are negative integers also. And if by chance its floating array then merge sort method is best.

[@AliObaid1992]

انت راقي احبك😘

[@techdose4u]

😅

[@spetsnaz_2]

Last method was 💖

[@techdose4u]

😂 Using multiset is the easiest :P

[@Navneetkumar-os5cl]

Sir in BiT updating value and getting prefix sum takes O(log(n)) time then how it is supposed to be O(n)

[@UnKnown-id7ih]

It would be very good if you shown code also,by the way it is fabulous.

[@techdose4u]

Yea I am doing it from March 2019.

[@manavmalhotra8513]

a[i]>a[j] and j>i , this is the inversion

[@manavmalhotra8513]

i think your inversion is wrng

[@Mandeepsingh-jo5cf]

time complexity for BIT method is O(nlogn)

[@yuktykhandelia5312]

The multiset method doesn't satisfy the time constraint as the distance method takes O(n) for multisets.

[@Samir-ll3kj]

Please make a video on AVL tree and BIT. It would be very helpful.

[@techdose4u]

It will come later when I resume Segment tree and TREE.

[@kishalaybhattacharya8312]

do u have any video on inversion in 2D array, in my code the time complexity is O(n^4), I want to reduce it

[@karanshah838]

I think the MultiSet implementation is O(nlogn)
upper_bound => O(logn) in multiset
We do upper_bound 'n' times
Therefore, O(nlogn)

[@vetald1979]

Thinking it N*Log(N)*Log(N) - to insert all element in a set is N*Log(N) - N-elements * Log N to insert * get the index for each insertion is LogN

[@aesthetic_vibes_404]

N² bcz a loop is outside for insertion O(n) and distance stl gonna take O(n) for calucating distance.
Hence N²

[@karanshah838]

@@aesthetic_vibes_404 Upper bound will give index and that can be used to calculate distance. So calculating distance is just O(log n) and we calculate the distance for 'n' elements. So O(nlogn)

[@shubhamprashar7676]

Why do we need to merge the partitions?

[@yyndsai]

So it's like checking if they are sorted or not?

[@MohitKumar-rq8hv]

method 2-merge sort 4:30
method 3-multiset 14:30

[@mukulrustagi9404]

Awesome

[@techdose4u]

Thanks

[@satyamgupta5234]

we can use stack also

[@ankitsinghgautam1274]

Thanks

[@techdose4u]

Welcome

[@hadeerzayat355]

Is the second method based on the merge sort called Piggybacking on merge sort also?

[@siddhantjaiswal4231]

pls discuss the BIT method

[@techdose4u]

Yes sure

[@lifecodesher5818]

I am very curious you make very good videos..what do you do full time?

[@techdose4u]

Software Developement Engineer.

[@gokulnaathb2627]

Multiset😍

[@techdose4u]

😅

[@vivekshaw2437]

can you make a video for the inversion count using BIT??

[@techdose4u]

I will make it once I cover BIT. For now I am covering graph. After that I can. Actually everyone is requesting to teach different stuffs, so it's becoming very difficult to switch. As soon as i upload some videos on graph interview prep then I will switch to your idea of BIT and other DS :) I hope you understand.

[@softwaredevelopment4392]

Please explain BIT

[@TomerBenDavid]

Which software do you use for the anntoations?

[@techdose4u]

Ink2go :)

[@TomerBenDavid]

@@techdose4u thanks! may I ask which pad do you use to do the actual writing?

[@hitaishidas4955]

Can you please tell me the Space Complexity of the 2nd method??

[@prateeksinghal630]

space complexity is actually O(n) like merge sort since you need extra array to store the numbers in sorted order

[@PhenomenalInitiations]

getting TLE with set

[@bhuvaneshwaranr5566]

could you give the code for method 2?

[@nemaligirisai2896]

import java.lang.*;
import java.io.*;
class GFG {
public static void main (String[] args){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
int arr[]=new int[n];
for(int i=0;i

[@kislayapant6119]

Sir can u pls provide the explanation for Binary indexed method for the same problem

[@techdose4u]

Sure.... When I get time I will

[@kislayapant6119]

@@techdose4u thanks sir

[@shivanshujaiswal7635]

Hi please explain BIT method

[@techdose4u]

Sure.

[@rajneeshyadav9728]

can you explain the BIT method

[@techdose4u]

Yea....I will cover this problem when I cover BIT

[@sutirthasadhukhan78]

Sir I can't apply Fenwick tree properly. Please apply Fenwick tree to solve this problem .

[@techdose4u]

I will do it after DP.

[@AnkitKumarCoder]

From where I get the code?

[@techdose4u]

I dint provide code for this. This is an old video. Back then I was not sharing code. Sorry. But I provide all codes now.

[@purushottamkumar3140]

Code Using Multiset
```
long long int inversionCount(long long arr[], long long N)
{
long long int ans=0;
multisetm;
for( long long int i = 0; i

[@sayantangupta1403]

Sir, can you please provide the code for all the methods and explain all the methods in another video. Please sir.

[@techdose4u]

CODE LINK: www.geeksforgeeks.org/counting-inversions/

[@techdose4u]

I will explain the methods in detail later.

[@sayantangupta1403]

@@techdose4u You are doing a great job sir. Could you please share your FB Id so that i can connect.

[@dayanandraut5660]

why is this solution not working for gfg and leetcode problems?

[@priyabratasingha174]

I think in the method 3 ,the time complexity should be o(nlogn).

[@soumyadeepdash4805]

No, because the distance function has linear complexity O(n), and we are calculating this for every index, so in the worst case time complexity will be O(n^2)

[@nishayadav9988]

sir please also provide a code of this problem

[@techdose4u]

Please try to code yourself

[@nishayadav9988]

Ok sir

[@ROSHANKUMAR-rl6bf]

difference kaise nikale

[@shivangitomar5557]

3rd method should be O(nlogn) right? ( we dont need to use "distance")

[@margolikesbees]

:)

[@ROSHANKUMAR-rl6bf]

multiset me minus nhi hota h sir

[@mtr2936]

Sir can you share the source code

[@techdose4u]

Please try to search in comment section

[@schan263]

I know the solution but not the intuition that leads to merge sort.

[@ShivamGupta-cx3hy]

you should change your name to Placement Cracker

[@techdose4u]

Let it be techdose :P

[@ShivamGupta-cx3hy]

@@techdose4u Thank you So much ,Sir you are a great help .

[@aneeshkulkarni1739]

At 3:10 you accidentally said 4 is greater than 6 hence there is inversion.
Got confused for a bit 😛

[@techdose4u]

:P

[@aneeshkulkarni1739]

Great explanation!
Could you also make a video about how to get the number of inversions per element in the original array?

[@techdose4u]

Sure.....but can you suggest me a proper title for that. That will be helpful to see if users need it or not.

[@aneeshkulkarni1739]

How about "count of smaller numbers after self" ?

[@techdose4u]

I guess I should have explained that in video itself 😅

[@rohitpal7739]

maal

[@purushottamkumar3140]

Code Using Merge Sort
long long int inversionCount(long long arr[], long long n)
{
return mergeSort(arr,0,n-1);
}
long long int mergeSort(long long arr[],long long low,long long high)
{
long long res=0;
if(low

[@theSilentPsycho]

best explanation

[@techdose4u]

Thanks :)