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

[@VikasKumar-nb2pn]

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

[@techdose4u]

Welcome :)

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

[@mansiagrawal4039]

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

[@techdose4u]

Welcome :)

[@SinghFlex]

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

[@techdose4u]

Welcome :)

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

[@RaGa_BABA]

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

[@techdose4u]

Nice :)

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

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

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

[@elizabethr5161]

Crystal clear explanation..

[@techdose4u]

Thanks :)

[@deepakprajapati5064]

this is called explanation with good knowledge

[@Mandeepsingh-jo5cf]

time complexity for BIT method is O(nlogn)

[@b9944236]

Picture explains everything, thanks.

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

[@KathanShah03]

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

[@javadsayevand8273]

The Best explanation ever... 🙏🙏🙏

[@techdose4u]

Thanks

[@jarno9340]

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

[@techdose4u]

Welcome :)

[@sagargupta1615]

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

[@sukritkapil2562]

Crystal clear explanation. Thanks a lot!!

[@techdose4u]

Welcome :)

[@jpakash1999]

You are genius :-) Thank You

[@techdose4u]

😅 Welcome

[@kaushikramabhotla4635]

The best explanation for this problem 👏 👌

[@yuktykhandelia5312]

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

[@AyushJain-ot9yv]

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

[@techdose4u]

Thanks :)

[@vipulkrishna19]

very very good explanation

[@techdose4u]

Thanks :)

[@vikashkumarchaurasia1299]

very nice explaination ever seen .thanks a lot

[@techdose4u]

Welcome

[@shubhammishra3783]

very clear explanation thank you

[@changjeffreysinto3872]

Clear explanation dude

[@vasujain1970]

This was an amazing explanation! Thank you!

[@techdose4u]

Welcome :)

[@paragroy5359]

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

[@techdose4u]

Thanks :)

[@PizzaGamingTheReal]

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

[@techdose4u]

Nice 😃

[@biswamohandwari6460]

Man I got understood everything, I saw there

[@techdose4u]

Nice :)

[@ranjanpanda2586]

RIP english

[@Joyddep]

Great explanation!

[@techdose4u]

Thanks

[@lifecodesher5818]

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

[@techdose4u]

Software Developement Engineer.

[@anjana1700]

Awesome Sir!
Sir please make a video on BIT also

[@techdose4u]

Yea...will make it.

[@divyareddy7622]

thankk you bhaiya!! amazing

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

[@kollivenkatamadhukar5059]

Excellent Explanation

[@techdose4u]

Thanks

[@todo1553]

Thanks for the explanation

[@techdose4u]

Welcome

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

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

[@sunwado]

Precise and too the point :)

[@techdose4u]

Thanks

[@shubhamprashar7676]

Why do we need to merge the partitions?

[@anitasingh-jw1lc]

merge sort is very understandi all us

[@shobhitbajaj9667]

Wow what a great explanation 👍

[@techdose4u]

Thanks

[@siddhantjaiswal4231]

pls discuss the BIT method

[@techdose4u]

Yes sure

[@jakubfraczek1208]

THANK YOU SO MUUUUUUUUCH

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

[@siddhantsingh8721]

best explanation

[@techdose4u]

Glad you think so!

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

[@SudhanshuKumar-jl8iw]

great explanation

[@techdose4u]

Thanks

[@22.jananidileepan44]

Superb

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

[@dayanandraut5660]

merge sort technique is the best for this problem

[@excessreactant9045]

Thanks for this my book didnt show this well

[@techdose4u]

😁

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

[@patilsoham]

Helped a lot!
Thank you!

[@techdose4u]

Welcome :)

[@priyasharma3549]

thank you so much

[@diptamoy12]

Atlast understood ❤❤

[@techdose4u]

Great :)

[@tusharkumar3277]

nice video ,really helpful

[@techdose4u]

Thanks :)

[@manavmalhotra8513]

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

[@manavmalhotra8513]

i think your inversion is wrng

[@satyamgupta5234]

we can use stack also

[@MohitKumar-rq8hv]

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

[@sharuk3545]

Awesome 👍

[@anjalipatel5643]

Can you please explain this question in single file programming.

[@yyndsai]

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

[@sutirthasadhukhan78]

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

[@techdose4u]

I will do it after DP.

[@ayushkawatra7436]

really helped a lot

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

[@_PAYALGAIKWAD]

thnx a lot

[@gokulnaathb2627]

Multiset😍

[@techdose4u]

😅

[@hadeerzayat355]

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

[@mukulrustagi9404]

Awesome

[@techdose4u]

Thanks

[@ShreyaSingh-vr9qi]

Nice explaination, BIT method too (:

[@techdose4u]

Okay

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

[@spetsnaz_2]

Last method was 💖

[@techdose4u]

😂 Using multiset is the easiest :P

[@shivanshujaiswal7635]

Hi please explain BIT method

[@techdose4u]

Sure.

[@ankitsinghgautam1274]

Thanks

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

[@dayanandraut5660]

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

[@AliObaid1992]

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

[@techdose4u]

😅

[@rajneeshyadav9728]

can you explain the BIT method

[@techdose4u]

Yea....I will cover this problem when I cover 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?

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

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

[@ROSHANKUMAR-rl6bf]

multiset me minus nhi hota h sir

[@schan263]

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

[@shivangitomar5557]

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

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

[@softwaredevelopment4392]

Please explain BIT

[@nishayadav9988]

sir please also provide a code of this problem

[@techdose4u]

Please try to code yourself

[@nishayadav9988]

Ok sir

[@ROSHANKUMAR-rl6bf]

difference kaise nikale

[@mtr2936]

Sir can you share the source code

[@techdose4u]

Please try to search in comment section

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

[@margolikesbees]

:)

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

[@rohitpal7739]

maal