Count Inversions in an Array | Brute and Optimal

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

[@user-ic7xs9vh7i]

@@yogeshkaushik8316 😆

[@anuplohar23]

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

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

[@THEReFleX]

ladki ka chakar

[@attackgaming9940]

Making the complex problem looks simpler is a kind of skill that striver only has🛐

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

[@bmishra98]

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

[@_AASHISHSHAH]

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

[@SuvradipDasPhotographyOfficial]

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

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

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

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

[@mranonymous1982]

Bro what

[@MehtabReviews]

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

[@vaibhav56]

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

[@cinime]

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

[@shiveshgupta1705]

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

[@PriyaGanti-m7c]

I understood the solution clearly... Thank you very much, sir.

[@selvaarumugam370]

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

[@aradhyaagrawal4766]

00:06 Count the number of pairs in an array where the left element is greater than the right element. 02:12 Brute Force solution 04:10 Counting the number of pairs in two sorted arrays where the left element is from the left array and the right element is from the right array, and the right element is smaller than the left element. 06:11 Inversion count can be found by counting the number of elements greater than the element on its right in a sorted array 08:28 The number of pairs formed in an array can be determined using the merge sort algorithm. 10:41 Counting inversions in an array by merging sorted subarrays. 13:03 Count the inversions in an array using a merge sort algorithm 15:17 Merge sort algorithm helps in counting inversions in an array 17:25 Count the number of inversions in an array 19:15 Count the number of inversions in an array 21:08 The solution uses a recursive function to merge and count inversions in an array. 22:51 The time complexity of counting inversions is O(n log n) and it requires extra space to merge arrays.

[@InduAnuga]

Understood THE BEST EXPLANATION Excellent playlist 👌 👏 ❤

[@prateek5208]

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

[@aditijagtap7853]

Best teaching approach so far!!!!

[@bgmihighlights6378]

Omg Striver you are great , someday will love to reach at your level!

[@prateekgoyal7009]

This is the best explanation I've ever got.

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

[@SaumyaSharma007]

OMG Bawal explanation Striver Bhaiya.😃

[@sourabhsoni5065]

Just cleared the intution so well.

[@pallavi22222]

your problem solving approach explanation is superb

[@pranavdharkar]

I feel so happy when i saw that the merge function returns the cnt and then add it to the ans i had exactly done the same

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

[@lakshaysawhney9988]

Thoroughly enjoyed the problem!!

[@chiragbirla5606]

Best explanation ever for this problem

[@shashwatpandey3285]

took me 1 day to solve this problem on my own , no outside help or anything , when i first saw the problem it was like hmm , we want total number of elements less than arr[i] on its right side , so it was basically like the array was being spilt, at first i coded the bruteforce which was very easy ofcoursse , and then i had to brainstorm for hours , in the question it was said the inversion count tells us how far or close the array is from being sorted , thats when merge sort came into my mind , because as i said earlier we want number of elements less than arr[i] on the right side of i , merge sort was the only soritng algo i studied in which arrays were being split and i thought while merging 2 sorted arrays we can count the number of elements smaller than arr[i[, from the right side of the splitted array

[@vikasbagri1225]

Understood it very well Thanks for this amazing series

[@akritisneh2849]

So much crystal clear!!!!Thank youu❤

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

[@flakky626]

Exactly my thought, No way you gonnna come up with something like that on your own

[@NoniSabharwal]

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

[@iamnoob7593]

Brilliant video. Thank you striver

[@abhishekverma4693]

thank you so much for watching

[@the_avii_7]

Please take care, in this problem inside 1st while loop if-condition should be { lesser than equal to ---> if ( arr[left]

[@vishakhakhanna8115]

Understood! Great explaination.

[@abhaypatel379]

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

[@GnaniDarshan]

Nice intution! Thanks

[@elamaran350]

Understood ❤ At last

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

[@creepitup]

[@mohd786ishaan]

UNDERSTOOD SIR ! GREAT EXPLAINATION

[@HR-pz7ts]

Amazing I solved two questions using the same logic.

[@theresilientpianist7114]

Really it was a great series Striver.🔥🔥

[@rushidesai2836]

Crazy good solution.

[@harigs72]

Happy teacher day 🎉❤

[@kaichang8186]

Thanks for the great video, well understood

[@shaikhanuman8012]

good explanation on count inversion

[@ishangujarathi10]

loved the optimal solution, intuition op!

[@pushankarmakar1783]

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

[@gauristar4094]

Superb logic, Understood!!!

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

[@KapilMaan-vw9sd]

thanks sir for making this wonderful video sir !!!

[@shivanshagrawal4179]

understood the solution striver thankyou

[@harim7945]

Striver is my man crush now lol after Tom cruise....jk You are great man....your videos help me a lot!

[@JatinKumar-pl4sq]

Bro u have destroyed all so called tech schools

[@ishasinghal3457]

Best explanation ever

[@pavanjegurupati]

Great explanation!!

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@prabhakaran5542]

Understood ❤

[@ajaykr2811]

13:05 the kind of excitement I want while learning DSA.

[@unnatishukla8513]

awesome as always!!!!🤩

[@MJBZG]

didn't understand much but will try again

[@yashisrivastava6196]

just wow explanation

[@sivasaimanchem4399]

All i can say is Thankyou so much ❤🙌

[@sukhpreetsingh5200]

Understood amazing explanation

[@309_dussasainath8]

arr=[2,4,1,3,5] count=0 res=[] for i in range(len(arr)-1,-1,-1): res.append(arr[i]) res.sort() j=0 while jres[j]: count+=1 j+=1 print(count) try this

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

[@steverogers7050]

very nice explanation bhaiya

[@Sumeet_100]

Thank you for this video !!

[@SukanyaGhosh-c4t]

Thank You Bhaiya

[@cursed_nerd]

Badhiya kaam kar rahe ho, see you soon

[@GuruPrasadShukla]

understood the approach sir thanks alot

[@calmcrussader]

can we pass our counter integer by reference in the functions ?

[@creepopsub2936]

Understood! but how to get this approach in interview pressure. Such a Unique Solution ngl.

[@saitehith6647]

Superb Explanation

[@anshasati1920]

Understood Sir🥳

[@TathagatTiwari-t6b]

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

[@sarangkumarsingh7901]

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

[@hashcodez757]

understood Bhaiya!!

[@NazeerBashaShaik]

Understood, thank you.

[@atharva3571]

I understood the problem

[@grm642]

Thank you😊

[@YourCodeVerse]

Understood✅🔥🔥

[@gautamsaxena4647]

understood bhaiya

[@ShubhamKumar-uf3gc]

loved that bhaiya

[@navdeepkumar9160]

Great video

[@satyamgupta4808]

very nice video

[@ravalikatalks5285]

thanks alot bhaiya

[@mridulathya1201]

Should'nt the line at 19:30 be "cnt += (mid - left + 1) - i "

[@venup2813]

Understood brother❤️

[@GhostVaibhav]

Understood🔥

[@parasarora5869]

Epic 🔥

[@her_soulmate]

Understood 🎉

[@anshulrai6058]

understood👍

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

[@infomania_by_ayush7901]

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

[@infomania_by_ayush7901]

Implemented.