Count Inversions in an Array | Brute and Optimal

Problem Link: bit.ly/3GJcuYj
Notes/C++/Java/Python codes: takeuforward.org/data-structu...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
0:00 Introduction of Course
00:40 Problem Statement
02:11 Brute force approach
02:52 Pseudocode
03:35 Complexity
04:05 Optimmal solution
04:22 Intuition
10:33 Approach + Dry-run
18:02 Code
22:37 Complexity

[@takeUforward]

Please watch our new video on the same topic: kzbin.info/www/bejne/d6TIhqCti7OUpbs

[@namannema3349]

this link take u to the same video we are watching

[@yogeshkaushik8316]

@@namannema3349 thats what recursion means

[@satvrii]

Nowadaya strivers voice has become so calm and soft 😅❤

[@anuradha3868]

True...as compared to his previous vdos 😂

[@newsbuster2194]

😂

[@shubhamkumar-hx1fb]

​@@anuradha3868 same thought 😂

[@saswatrath4646]

abe mic kharap tha pehle😂

[@anuplohar23]

Best count inversion video on KZbin, your method of teaching is very best that it gets me understand very easily 🌟🌟🌟

[@_AASHISHSHAH]

this is the best playlist in world. thank you stiver for your effort.

[@bmishra98]

Completed the playlist. This was the best recursion playlist I ever went through. Thanks a lot Striver.

[@gajendrakumar8271]

Finally completed this recursion playlist and Thanks a lot striver for great explanation throughout and patiently drawing recursion tree. patience is the key to solve and teach anything . And you have it man and you are teaching that too. Thanks a lot again

[@SuvradipDasPhotographyOfficial]

The best count inversion video on KZbin.. Thanks a lot Raj.. stay blessed❤

[@Manishgupta200]

I'm trying this problem and solved it by myself by taking count as global variable.. But you taught us in a vary optimal way without taking count as a global variable. Really best optimal approach. Thankyou ❤

[@bishakhdutta8427]

whats the complexity of your solution? can you share it?

[@Manishgupta200]

@@bishakhdutta8427 same as merger sort merge algorithm

[@cinime]

Understood! Super amazing explanation as always, thank you very very very much for your effort!!

[@senseiAree]

Striver your voice is very soothing and calm bro ❤.... I use it to sleep at night AND study... and I don't feel sleepy

[@akritisneh2849]

So much crystal clear!!!!Thank youu❤

[@vikasbagri1225]

Understood it very well Thanks for this amazing series

[@user-jm6bc3rt5e]

Understood THE BEST EXPLANATION Excellent playlist 👌 👏 ❤

[@prateekgoyal7009]

This is the best explanation I've ever got.

[@cartidise]

I usually don't comment but wanted to say that just subbed your channel. This is the best explanation I've ever got. THANKS A LOT:>)

[@selvaarumugam370]

As usual your teaching jus made coding much easier than it is bruh!! Waiting for Binary Search series bruh!!!!

[@aditijagtap7853]

Best teaching approach so far!!!!

[@pallavi22222]

your problem solving approach explanation is superb

[@mehulthuletiya497]

Timestamps: --------------------- 00:40 Problem Statement 02:11 Brute force approach 02:52 Pseudocode 03:35 Complexity 04:05 Optimmal solution 04:22 Intuition 10:33 Approach + Dry-run 18:02 Code 22:37 Complexity

[@lakshaysawhney9988]

Thoroughly enjoyed the problem!!

[@chiragbirla5606]

Best explanation ever for this problem

[@mohd786ishaan]

UNDERSTOOD SIR ! GREAT EXPLAINATION

[@prateek5208]

such an awesome expalination bhaiya just approach dekhkr hi dimag ma intution agya ki merge ma kase implement krenge , you are best

[@shiveshgupta1705]

i just imagine if all the problems would be available on this channel in future

[@SaumyaSharma007]

OMG Bawal explanation Striver Bhaiya.😃

[@unnatishukla8513]

awesome as always!!!!🤩

[@pavanjegurupati]

Great explanation!!

[@theresilientpianist7114]

Really it was a great series Striver.🔥🔥

[@gauristar4094]

Superb logic, Understood!!!

[@ishangujarathi10]

loved the optimal solution, intuition op!

[@abhaypatel379]

thanks striver for making a complex question into very easy question 🤗

[@8bit_hero850]

Can we realistically solve this if it comes in an interview given we haven't solved it before? I mean how do can you get the intuition of merge sort from this problem? I really don't get it.

[@unknown47896]

no way bro

[@Sumeet_100]

Thank you for this video !!

[@GuruPrasadShukla]

understood the approach sir thanks alot

[@sukhpreetsingh5200]

Understood amazing explanation

[@sivasaimanchem4399]

All i can say is Thankyou so much ❤🙌

[@xtzyrox2764]

I am happy with the brute force now I will see optimal 1 week before interview bcz University exams are in this month

[@b39_navkaransingh73]

Did anyone ask you?

[@ishasinghal3457]

Best explanation ever

[@NazeerBashaShaik]

Understood, thank you.

[@the_haryannvi_coder]

If u don't wanna use cnt in mergeSort function, you can do this:- int mergeSort(vector &arr, int low, int high) { if (low >= high) return 0; int mid = (low + high) / 2 ; int left = mergeSort(arr, low, mid); // left half int right = mergeSort(arr, mid + 1, high); // right half int m = merge(arr, low, mid, high); // merging sorted halves return left + right + m; }

[@HR-pz7ts]

Amazing I solved two questions using the same logic.

[@saitehith6647]

Superb Explanation

[@vaibhav56]

I was struggling with the solution but as soon as you mentioned merge sort it clicked in my mind

[@steverogers7050]

very nice explanation bhaiya

[@yashisrivastava6196]

just wow explanation

[@rohitkumarpilania94]

Badhiya kaam kar rahe ho, see you soon

[@sarangkumarsingh7901]

Nice lecture................

[@hashcodez757]

understood Bhaiya!!

[@navdeepkumar9160]

Great video

[@user-ck6kn1ty8x]

Thank You Bhaiya

[@nishant4595]

understood!!!

[@NoniSabharwal]

The way he said wow! Uff in love with the voice

[@grm642]

Thank you😊

[@YourCodeVerse]

Understood✅🔥🔥

[@venup2813]

Understood brother❤️

[@anshasati1920]

Understood Sir🥳

[@GhostVaibhav]

Understood🔥

[@her_soulmate]

Understood 🎉

[@nikhilprakashahir5730]

so aweesome

[@ShubhamKumar-uf3gc]

loved that bhaiya

[@ravalikatalks5285]

thanks alot bhaiya

[@satyamgupta4808]

very nice video

[@RituSingh-ne1mk]

Understood!

[@abhishekverma4693]

thank you so much for watching

[@atharva3571]

I understood the problem

[@divyaanandhan6021]

Thanks 😊👍

[@HarshChoudhary-vm6eh]

Understood thats great...

[@muqeemuddin8057]

Hey, can you make a video on binary insertion sort and compare it's time complexities with insertion sort. Thanks for your videos on DSA.

[@user-nk1mb5fy7j]

UNDERSTOOD

[@anushkajain8480]

Understood.

[@abhishekahirvar7783]

thanks mate

[@AbjSir]

// Everytime while sorting you move an element to the left (assume nobody moves to right agar chote walo ko aana hoga to left me aa jayenge) // if an element crosses another element while moving to the left for the purpose of sorting then it should increase the count of inversion

[@vikasgupta1828]

Thanks

[@vivekbhore5722]

thank u striver

[@varunpalsingh3822]

understood 👍👍

[@nayankhuman1043]

Understood :)

[@user-lw9dj8we7k]

Understood sir

[@hetchaudhari]

Is it fine to pass variables by reference?Or should we avoid that too in the interviews?

[@TheNullDeveloper]

understood the solution . But how do i get the intution that it will solve in this way i.e using this approach 😕 in most of the cases i don't have idea about the optimal one how would I approach it

[@culeforever5408]

understood :)

[@VaibhavSethF]

Hi Striver , is creating static variables in interview is a bad practice?

[@hemantpatel1413]

understood.

[@pritipatil4021]

Understood...!!!!

[@mount2020]

Thank u bhai

[@RIyaGupta-iz9iw]

Understand bhaiya

[@user-sm7zo5zd9t]

Understood

[@soumiyamuthuraj3516]

awesome

[@ChhaviAayushi-qh4zx]

Good Afternoon sir sir in my college it's hard to get on campus INTERNSHIP can you please advice so that I can get an internship in my third year . Thanks

[@addy1268]

can anybody pls explain why we cant/ should'nt declare the 'cnt' variable globally ?

[@MasterChief-jy2zg]

I tried it in a new approach. 2 pointer method. time complexity is near about O(n). but don't know why it is showing O(n^2) striver can u help me? int numberOfInversions(vector&a, int n) { int cnt=0,left=0,right=left+1; while(left < (n-1)){ if(right == n){ left++;right=left+1; } else if(a[left] > a[right]){ cnt++;right++; } else right++; } return cnt; }

[@user-je7tz6le4k]

These types of questions always demotivate me... like how you can think of such kind of solution in an interview

[@infomania_by_ayush7901]

Understood, but I am gonna need some time to implement this.

[@infomania_by_ayush7901]

Implemented.

[@AnjuGupta-sz1uk]

understood

[@pushankarmakar1783]

understood! def merge(arr,l,mid,h): temp=[] i=l j=mid+1 cnt=0 while i

[@MJBZG]

didn't understand much but will try again

[@vk-mc5tq]

Global vs Local In Global variables values updated dynamically but in local variables we need to pass updated values (manually) to subsequent functions

[@error-my9ut]

understood this but sir i am not really sure that if it would hit in my head at the time of interview how can i make that sure sir

[@vaibhavverma6120]

you cansolve these type of questions if only you have done it or similar type of question earlier otherwise no one can get this intuition on the spot.

[@shaurya2608]

Is there any chance we can solve this problem using unordered map?

[@bishakhdutta8427]

i was thinking the same thing, but use ordered map instead

[@priyotoshsahaThePowerOf23]

yes u can use map because it is a paring problem but this will not for interview ..In Cp it's ok,

[@bishakhdutta8427]

@@priyotoshsahaThePowerOf23 can you explain your solution, everyone uses only this merge sort method

[@priyotoshsahaThePowerOf23]

@@bishakhdutta8427 bro nothing just declare a map ..mapmap , and store the sorted elements of both array simultaneously then just print the keys...very much easy But know the problem is whenever you using inbuilt tools like map it used auxiliary space so space complexity is = O(N) Second thing is the time complexity also O( nlogn +mlogm)

[@sourabhmittal6862]

can someone tell me what is wrong with my code it is written in js class Solution { // Function to count inversions in the array. count = 0; inversionCount(arr, N) { this.count = 0; const sorted = this.isArraySorted(arr, N); if (sorted === "asc") { return 0; } else if (sorted === "desc") { return ((N - 1) * N) / 2; } this.mergeSort(0, N - 1, arr, N); return this.count; } mergeSort(low, high, arr, N) { if (low >= high) return; const mid = low + Math.floor((high - low) / 2); this.mergeSort(low, mid, arr, N); this.mergeSort(mid + 1, high, arr, N); this.mergeArr(low, mid, high, arr, N); } mergeArr(low, mid, high, arr, N) { const arr1 = arr.slice(low, mid + 1); const arr2 = arr.slice(mid + 1, high); let i1 = 0; let i2 = 0; let m = low; while (i1 < arr1.length && i2 < arr2.length) { if (arr[i1] > arr[i2]) { this.count = this.count + arr1.length - i1; arr[m++] = arr1[i1++]; } else { arr[m++] = arr2[i2++]; } } while (i1 < arr1.length) { arr[m++] = arr1[i1++]; } while (i2 < arr2.length) { arr[m++] = arr2[i2++]; } } isArraySorted(arr, N) { let ascSorted = true; let descSorted = true; for (let i = 0; i < N - 1; i++) { if (arr[i] > arr[i + 1]) { ascSorted = false; } if (arr[i] < arr[i + 1]) { descSorted = false; } } if (ascSorted) { return "asc"; } else if (descSorted) { return "desc"; } else { return ""; // Not sorted } } }

[@hardikg6858]

can i solve this question using pbds