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 :)

[@jarno9340]

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

[@techdose4u]

Welcome :)

[@AyushJain-ot9yv]

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

[@techdose4u]

Thanks :)

[@sagargupta1615]

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

[@deepakprajapati5064]

this is called explanation with good knowledge

[@kaushikramabhotla4635]

The best explanation for this problem 👏 👌

[@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 :)

[@sukritkapil2562]

Crystal clear explanation. Thanks a lot!!

[@techdose4u]

Welcome :)

[@RaGa_BABA]

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

[@techdose4u]

Nice :)

[@shubhammishra3783]

very clear explanation thank you

[@b9944236]

Picture explains everything, thanks.

[@mansiagrawal4039]

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

[@techdose4u]

Welcome :)

[@vasujain1970]

This was an amazing explanation! Thank you!

[@techdose4u]

Welcome :)

[@PizzaGamingTheReal]

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

[@techdose4u]

Nice 😃

[@patilsoham]

Helped a lot! Thank you!

[@techdose4u]

Welcome :)

[@sunwado]

Precise and too the point :)

[@techdose4u]

Thanks

[@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)

[@javadsayevand8273]

The Best explanation ever... 🙏🙏🙏

[@techdose4u]

Thanks

[@changjeffreysinto3872]

Clear explanation dude

[@divyareddy7622]

thankk you bhaiya!! amazing

[@sharuk3545]

Awesome 👍

[@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)

[@jpakash1999]

You are genius :-) Thank You

[@techdose4u]

😅 Welcome

[@elizabethr5161]

Crystal clear explanation..

[@techdose4u]

Thanks :)

[@shobhitbajaj9667]

Wow what a great explanation 👍

[@techdose4u]

Thanks

[@paragroy5359]

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

[@techdose4u]

Thanks :)

[@Joyddep]

Great explanation!

[@techdose4u]

Thanks

[@ayushkawatra7436]

really helped a lot

[@vikashkumarchaurasia1299]

very nice explaination ever seen .thanks a lot

[@techdose4u]

Welcome

[@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

[@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

[@priyasharma3549]

thank you so much

[@todo1553]

Thanks for the explanation

[@techdose4u]

Welcome

[@kollivenkatamadhukar5059]

Excellent Explanation

[@techdose4u]

Thanks

[@tusharkumar3277]

nice video ,really helpful

[@techdose4u]

Thanks :)

[@22.jananidileepan44]

Superb

[@KathanShah03]

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

[@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

[@vipulkrishna19]

very very good explanation

[@techdose4u]

Thanks :)

[@jakubfraczek1208]

THANK YOU SO MUUUUUUUUCH

[@ShreyaSingh-vr9qi]

Nice explaination, BIT method too (:

[@techdose4u]

Okay

[@SudhanshuKumar-jl8iw]

great explanation

[@techdose4u]

Thanks

[@theSilentPsycho]

best explanation

[@techdose4u]

Thanks :)

[@diptamo]

Atlast understood ❤❤

[@techdose4u]

Great :)

[@anjana1700]

Awesome Sir! Sir please make a video on BIT also

[@techdose4u]

Yea...will make it.

[@_PAYALGAIKWAD]

thnx a lot

[@excessreactant9045]

Thanks for this my book didnt show this well

[@techdose4u]

😁

[@shubhamprashar7676]

Why do we need to merge the partitions?

[@yyndsai]

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

[@hadeerzayat355]

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

[@biswamohandwari6460]

Man I got understood everything, I saw there

[@techdose4u]

Nice :)

[@ranjanpanda2586]

RIP english

[@anitasingh-jw1lc]

merge sort is very understandi all us

[@dayanandraut5660]

merge sort technique is the best for this problem

[@yuktykhandelia5312]

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

[@lifecodesher5818]

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

[@techdose4u]

Software Developement Engineer.

[@AliObaid1992]

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

[@techdose4u]

😅

[@mukulrustagi9404]

Awesome

[@techdose4u]

Thanks

[@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?

[@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.

[@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.

[@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.

[@spetsnaz_2]

Last method was 💖

[@techdose4u]

😂 Using multiset is the easiest :P

[@ankitsinghgautam1274]

Thanks

[@techdose4u]

Welcome

[@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.

[@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

[@satyamgupta5234]

we can use stack also

[@manavmalhotra8513]

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

[@manavmalhotra8513]

i think your inversion is wrng

[@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

[@Mandeepsingh-jo5cf]

time complexity for BIT method is O(nlogn)

[@gokulnaathb2627]

Multiset😍

[@techdose4u]

😅

[@siddhantjaiswal4231]

pls discuss the BIT method

[@techdose4u]

Yes sure

[@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)

[@MohitKumar-rq8hv]

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

[@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

[@anjalipatel5643]

Can you please explain this question in single file programming.

[@sutirthasadhukhan78]

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

[@techdose4u]

I will do it after DP.

[@softwaredevelopment4392]

Please explain BIT

[@dayanandraut5660]

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

[@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.

[@PhenomenalInitiations]

getting TLE with set

[@shivanshujaiswal7635]

Hi please explain BIT method

[@techdose4u]

Sure.

[@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.

[@rajneeshyadav9728]

can you explain the BIT method

[@techdose4u]

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

[@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

[@ROSHANKUMAR-rl6bf]

multiset me minus nhi hota h sir

[@shivangitomar5557]

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

[@nishayadav9988]

sir please also provide a code of this problem

[@techdose4u]

Please try to code yourself

[@nishayadav9988]

Ok sir

[@ROSHANKUMAR-rl6bf]

difference kaise nikale

[@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)

[@schan263]

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

[@mtr2936]

Sir can you share the source code

[@techdose4u]

Please try to search in comment section

[@margolikesbees]

:)

[@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