Counting inversions in an array

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

[@RaGa_BABA]

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

[@techdose4u]

Nice :)

[@mansiagrawal4039]

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

[@techdose4u]

Welcome :)

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

[@kaushikramabhotla4635]

The best explanation for this problem 👏 👌

[@sagargupta1615]

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

[@elizabethr5161]

Crystal clear explanation..

[@techdose4u]

Thanks :)

[@Mandeepsingh-jo5cf]

time complexity for BIT method is O(nlogn)

[@deepakprajapati5064]

this is called explanation with good knowledge

[@javadsayevand8273]

The Best explanation ever... 🙏🙏🙏

[@techdose4u]

Thanks

[@AyushJain-ot9yv]

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

[@techdose4u]

Thanks :)

[@jarno9340]

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

[@techdose4u]

Welcome :)

[@sukritkapil2562]

Crystal clear explanation. Thanks a lot!!

[@techdose4u]

Welcome :)

[@b9944236]

Picture explains everything, 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

[@vasujain1970]

This was an amazing explanation! Thank you!

[@techdose4u]

Welcome :)

[@paragroy5359]

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

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

[@changjeffreysinto3872]

Clear explanation dude

[@todo1553]

Thanks for the explanation

[@techdose4u]

Welcome

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

[@vikashkumarchaurasia1299]

very nice explaination ever seen .thanks a lot

[@techdose4u]

Welcome

[@shubhammishra3783]

very clear explanation thank you

[@jpakash1999]

You are genius :-) Thank You

[@techdose4u]

😅 Welcome

[@vipulkrishna19]

very very good explanation

[@techdose4u]

Thanks :)

[@Joyddep]

Great explanation!

[@techdose4u]

Thanks

[@shobhitbajaj9667]

Wow what a great explanation 👍

[@techdose4u]

Thanks

[@biswamohandwari6460]

Man I got understood everything, I saw there

[@techdose4u]

Nice :)

[@ranjanpanda2586]

RIP english

[@KathanShah03]

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

[@divyareddy7622]

thankk you bhaiya!! amazing

[@kollivenkatamadhukar5059]

Excellent Explanation

[@techdose4u]

Thanks

[@anjana1700]

Awesome Sir!
Sir please make a video on BIT also

[@techdose4u]

Yea...will make it.

[@PizzaGamingTheReal]

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

[@techdose4u]

Nice 😃

[@sunwado]

Precise and too the point :)

[@techdose4u]

Thanks

[@yuktykhandelia5312]

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

[@diptamoy12]

Atlast understood ❤❤

[@techdose4u]

Great :)

[@SudhanshuKumar-jl8iw]

great explanation

[@techdose4u]

Thanks

[@tusharkumar3277]

nice video ,really helpful

[@techdose4u]

Thanks :)

[@patilsoham]

Helped a lot!
Thank you!

[@techdose4u]

Welcome :)

[@shubhamprashar7676]

Why do we need to merge the partitions?

[@dayanandraut5660]

merge sort technique is the best for this problem

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

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

[@lifecodesher5818]

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

[@techdose4u]

Software Developement Engineer.

[@anitasingh-jw1lc]

merge sort is very understandi all us

[@manavmalhotra8513]

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

[@manavmalhotra8513]

i think your inversion is wrng

[@MohitKumar-rq8hv]

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

[@excessreactant9045]

Thanks for this my book didnt show this well

[@techdose4u]

😁

[@yyndsai]

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

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

[@ShreyaSingh-vr9qi]

Nice explaination, BIT method too (:

[@techdose4u]

Okay

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

[@theSilentPsycho]

best explanation

[@techdose4u]

Thanks :)

[@hadeerzayat355]

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

[@AliObaid1992]

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

[@techdose4u]

😅

[@22.jananidileepan44]

Superb

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

[@siddhantjaiswal4231]

pls discuss the BIT method

[@techdose4u]

Yes sure

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

[@jakubfraczek1208]

THANK YOU SO MUUUUUUUUCH

[@ayushkawatra7436]

really helped a lot

[@dayanandraut5660]

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

[@priyasharma3549]

thank you so much

[@sutirthasadhukhan78]

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

[@techdose4u]

I will do it after DP.

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

[@spetsnaz_2]

Last method was 💖

[@techdose4u]

😂 Using multiset is the easiest :P

[@satyamgupta5234]

we can use stack also

[@anjalipatel5643]

Can you please explain this question in single file programming.

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

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

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

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

[@gokulnaathb2627]

Multiset😍

[@techdose4u]

😅

[@_PAYALGAIKWAD]

thnx a lot

[@shivanshujaiswal7635]

Hi please explain BIT method

[@techdose4u]

Sure.

[@ankitsinghgautam1274]

Thanks

[@techdose4u]

Welcome

[@ROSHANKUMAR-rl6bf]

multiset me minus nhi hota h sir

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

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

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

[@PhenomenalInitiations]

getting TLE with set

[@softwaredevelopment4392]

Please explain BIT

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

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

[@margolikesbees]

:)

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