COUNT INVERSIONS in an ARRAY | Leetcode | C++ | Java | Brute-Optimal

[@takeUforward]

Please watch the new video which covers it in more depth, and also prints it: kzbin.info/www/bejne/d6TIhqCti7OUpbs Understood or nott? am waiting in the comment section ;) . Check me out at Instagram: instagram.com/striver_79/ . If you appreciate the channel's work, you can join the family: bit.ly/joinFamily

[@vaibhavsethia70]

Understood

[@sahilchoudhary1473]

Understood

[@ashishdwivedi5190]

Hey u forgot to upload link to this video on sde sheet....

[@mafiaco1257]

No 🥺

[@pleasesirmorevideos4684]

Understoood

[@shardulkhadye5875]

i sincerely feel that this problem should not be marked as medium level as its extremely difficult to figure out this answer in an interview if not solved previously.

[@codding32world50]

Yes I was stuck for whole day literally then came here😢

[@aakashmehta9474]

Not at all possible to figure out this solution unless you are genius 😃

[@ritikashishodia675]

Maine to phele kiya tha ye to jb dubara kiya after months nahi hua.😔😔

[@garvgoel1743]

@@ritikashishodia675 This is very normal 😂

[@mdhaidarparwez968]

For this type of problem, you should make a note and revise weekly

[@muditkhanna8164]

180 questions form sde sheet with striver's solution>>> 1000 self practice questions , you get to learn so many tricks and concepts with in each question. the key is to not fast forward the question. give each question its deserving time. that's all then striver's sheet is enough to you ! thank you dude!

[@yashisrivastava5482]

Sir you are really a motivation , after so much of busy schedule your are still selflessly helping us in every way (hats off to you) . I wait the whole day just for your video and only after watching and learning the concept I sleep. Thank you so much sir

[@takeUforward]

Yashi Srivastava glat that you wait, this things keeps me motivated!!

[@abhijitroy1958]

The alpha rule : never lose the concentration while watching striver's video . Best explanation

[@rohitanjane1668]

Highly agree with you 👍🏻🙌🏻

[@neerajsinghjr]

Seriously, this guy is Awesome. but its also true... you can't doze off for a single bit. If you do then rewind ...

[@baljotsinghchoudhary7434]

this question is very interesting one should try to solve with all approches merge sort, fenwick and trie

[@tanayshah275]

Great Explanation! One more thing if anyone is implementing it then the invertion count will increase by mid - i + 1

[@tarungopal3065]

@Anand Pandey As you are calling merge() function with 'mid' as as the argument..you have to write " mid- i + 1" But the In video... He is calling as merge(left, mid+1, right)

[@tusharvaish8096]

Why.? Can you explain.

[@tusharvaish8096]

@Anand Pandey why we need to add 1 ? Can you explain

[@mohitsingh7793]

Merge-Sort with small modification : void merge(int l1, int h1, int l2, int h2, vector&nums, int &count) { int n1 = h1 - l1 + 1; int n2 = h2 - l2 + 1; vectora(n1), b(n2), c(n1 + n2); for (int i = 0; i < n1; i++) a[i] = nums[l1 + i]; for (int i = 0; i < n2; i++) b[i] = nums[l2 + i]; int i = 0, j = 0, k = 0; while (i < n1 and j < n2) { if (a[i] l) { int mid = l + (h - l) / 2; merge_sort(l, mid, nums, count); merge_sort(mid + 1, h, nums, count); merge(l, mid, mid + 1, h, nums, count); } }

[@shreeramgoyal84]

Hey Striver! was wondering if we could do it by Priority Queue. I mean we can but then we would need an extra storage for storing the popped values and an additional complexity to push back to pq. What do you suggest?

[@prashantbisht2219]

Yeah but wouldn't it be O(n^2).For every element you traversing the entire queue in worst case.

[@pranav288]

@@prashantbisht2219 yup

[@krisnerdscave394]

12:22 I guess there should by said number of elements to the right of the 'i' not 'mid' so the number of elements from left that the right element needed to jump over it. And this is what Striver said here 12:27 basically :) 11:56 K should not be set to zero, as we won't to have indexes in temp as in original arr. 13:01 Do we rally need that copying for anything?

[@krisnerdscave394]

Love to discuss with myself :) but yeah we really need that copying and by saying that K should not be zero I've automatically confirmed that it's needed :)

[@vershamishra8763]

@@krisnerdscave394 yes, Thank you for the first statement, I got confused then this helped me to clarify.

[@shivalikagupta3433]

Truly each and every word you speak is in align with the question's essence and explanation 1 minute apart and I need to watch the video again. Its a thorough explanation. Wonderful!!!

[@devanshmesson2777]

You Speak So Clearly! Great Video Quality and Awesome Explaination!!

[@dhanubhardwaj6935]

why not inv_count=mid-i+1 bcz both i and mid are inclusive

[@BattlefieldAWWWClips]

Hi striver meet gandhi , here again revising few tough code , i think there is a mistake wen u are doing inv_count =inv_count +(mid-1) ; U are telling this for right side of array but ideally we are counting from mid to left (i.e. i) . I think it is left right do correct asap plz if wrong .

[@mohitsingh7793]

Hey Stiver,I can easily solve that question using fenwick tree data structure.But what about if maximum element in array can be upto 10^9.How to solve that using fenwick tree ? Or we can't do incase of large elements of array?

[@mdazeen8820]

this can be done by compressing the array because size of array is 10^5 .For example {10^8,10^9} can be compressed as {1,2}

[@adityasai550]

Bro can u tell me from where you learned Fenwick tree. There are not many good videos about Fenwick tree in KZbin

[@mohitsingh7793]

@@adityasai550 kzbin.info/www/bejne/b6bEiXpsZ75ri9k

[@Sahil-nm7di]

I am already done this question but after that i am loving to see your solution video its helps us to how we should explain our solution in front of interviewer thanx..

[@takeUforward]

Thanks! Cheers!!

[@aasthajain4210]

You are so hardworking man!! I just look up to this✨

[@rudranilacharya5293]

Can we use ordered set in interviews, this ques is much easier with ordered set

[@SurajVerma-lx6ik]

Hey striver I have one suggestion for placement series U could add 3 similar ques for practice in each vdo of placement series starting from Day -1 ... I am not sure i am right or wrong plzz tell striver is it correct or not bas man me kya isliye suggest kar diye . Plzz reply #striver 🤔

[@jayeshgupta8618]

Bro when you solve these questions on leetcode then leetcode suggest similar questions , just do one or two from the suggestions maybe .

[@SurajVerma-lx6ik]

@@jayeshgupta8618 uske liye leetcode premium lena padega kya ????

[@sasiraj1594]

@@SurajVerma-lx6ik no

[@SurajVerma-lx6ik]

@@sasiraj1594 ok

[@shivendrsrivastava7315]

So can we say that the crux is doing inversion is basically sorting ? and merge sort is the most appropriate one

[@himanshusinghal5299]

I think we can use binary search(lower_bound stl) which would take O(nlogn)

[@takeUforward]

No pro it will not.. you will have to use set, so after lower bound to find number of elements you need to subtract the iterator which will take n time making it total of n^2

[@himanshusinghal5299]

@@takeUforward yeah got it thanx

[@KathanShah03]

@@takeUforward is there any other method to solve this problem using hash/set/maps?

[@shanayaarora198]

Happy Teachers Day :) Thanks for such a great content.

[@venuvenu2719]

I have been thinking of an alternate easy approach. Let's say I sort the array in nlogn, then count every element inversion count using O(N) approach where we just count the number of elements on the right side of the array. total TC= nlogn + n = nlogn Wouldnt this be an easier solution? Please correct me if this is wrong.

[@sak3579]

can't sort the array

[@brahmkaransingh8804]

No its wrong bcoz it will count that inversions also which was not a inversion in real array . It will work if array is sorted in descending order, then only your approach will follow good. Hope you understand. If have any doubt let me know

[@acxd]

It would have been much much clearer if you had modified the code of merge sort from gfg because using temp as parameter is confusing and the gfg article from where you have taken the code is also not easy to understand.

[@takeUforward]

I did not want to modify because a bunch kf students follow gfg 😅

[@smartwaytolearn2425]

why can't we solve this with gap method??? please reply.......

[@ranasauravsingh]

UNDERSTOOD... !!! Thanks striver for the video... :)

[@amitsamratmaurya3170]

Can you explain why you are using -> (mid-i) isnt it supposed to be (mid-i+1), but why your code works?

[@VinayKumar-oi4yq]

Yeah, my code worked with mid-i+1 as well

[@atmanirbharladka4467]

I really appreciate you explaining the prerequisite too for the question.

[@demonslayer4607]

tum dhanush fan ko kya ?

[@souravchakraborty9777]

Would you kindly explain the Fenwick tree method?

[@stith_pragya]

Thank You very much for providing this video.........👍👍👍👍👍👍

[@MrJoyRana]

Solution in javascript function merge(left, right, obj) { let result = []; let l = 0; let r = 0; while (l < left.length && r < right.length) { if (left[l] < right[r]) { result.push(left[l++]); } else { obj.count++; // this is one pair as a[i]>a[j] obj.count += left.slice(l + 1).length; // if left[l]>left[r], and left array is sorted in ascending order, then all elements to to the right also can be pair result.push(right[r++]); } } return [...result, ...left.slice(l), ...right.slice(r)]; } function mergeSort(arr, obj) { const length = arr.length; if (length < 2) return arr; let midPoint = Math.floor(length / 2); const left = arr.slice(0, midPoint); const right = arr.slice(midPoint); return merge(mergeSort(left, obj), mergeSort(right, obj), obj); } function countInversion(arr) { const obj = { count: 0 }; const mergedArr = mergeSort(arr, obj); return obj.count; }

[@amrithapatil4595]

I think line number 28 should be inv_count = inv_count + mid - i+1;

[@brahmkaransingh8804]

Yes that was the doubt which i was searching for in the comment section

[@brahmkaransingh8804]

@Anand Pandey bro can you tell me whats wrong with the below code. Just ignore as i am not maintaining the temp array and just looking for inv_count. Thanks in advance Code -> long long merge(long long arr[], long long l, long long mid, long long r){ long long i = l; long long j = mid + 1; long long inv_count = 0; while(i

[@imtiyazuddin4827]

yep, i had the same doubt

[@SatyaMantha]

Striver, i make sure i like and comment on every video that i watch. I am learning a lot from your videos.

[@darshantank554]

What do you think about a "binary indexed tree" with O(N) ?!?!?!?!?!

[@greedycat9845]

your diagram had made me reailze the core part of the solution.very nice explanatio

[@peter9759]

Nice video totally understood optimal approach

[@Ayush-ir3wi]

inv_count += merge(arr, temp, left, mid + 1, right); why are we passing mid+1 here when the starting index of the 2nd array is mid??

[@pulkitahuja4750]

Can you please the solution using BIT, I saw it on leetcode but I am not so familiar to using BIT except for the range sums. It would be very helpful if we could learn some applications of BIT.

[@amitguptapc]

whats the name of this problem on leetcode?

[@saishree8886]

@takeuforward using global variables gives wrong o/p y?But doing the same by adding subtrees gives the crct o/p

[@bhaveshkumar6842]

Thank you so much bro!!!!!

[@goodpeople7615]

Awesome content shows how good preparation it needs and you nail every time . Happy teachers day ʕ´•ᴥ•`ʔ

[@mannthakkar]

Very interesting question once you practice it

[@AdityaKumar-rs5jn]

Bhai bahut bdiya explain krte.. Fully understood..

[@takeUforward]

Thanks! Cheers :)

[@nayanbhuyan8156]

Nice explanation, I would love to see more videos on critical questions

[@maulikdev5040]

Amazingly taught the concept. Thank you so much!!

[@joyalmeida6565]

why do we need temp array? I'm not getting in what way will the existing array will be modified. Please Explain

[@yatinarora1252]

U can watch merge sort it that u need a array so that you can basically store your elements and find comparison

[@ankitdubey9310]

can we just move in the array and use stl sort to sort the right half and then compare each element to the one on the right and if its greater we are good to go, however after every sort i want to my array back to normal, is there a way around this?

[@nuclearnadal69]

Bro this approach sounds more brute than the brute force itself

[@ankitdubey9310]

@@nuclearnadal69 my programming 4 months back was "brutal" lol 😂😂

[@MallistParasite]

The Struggle Between Sort and Shot.Very Evident😛. Great Explaination.Understood.

[@farazahmed7]

bolo aunty tau kya

[@nayanbhuyan8156]

Your sde sheet link for this video is not working, directing the spoj

[@SHASHANKRUSTAGII]

I tried to think, when i saw nlogn, heapsort, merge sort came to my mind. my mind tried to think, but could not develop intuition for O(nlogn) :( Although, brute force is easy for me, but how do i optimise?

[@farazahmed7]

no one can come up with the optimal soln until and unless you have already solved it before.

[@SHASHANKRUSTAGII]

@@farazahmed7 no after 1 ye if practice now i can see why merge sort is the key to solve this problem. We can make use of merge sort in order to find the number of inversions optimally

[@aniketdubey7363]

Can this be solved using policy based data structure ?

[@gurharpartapdhaliwal3087]

We can do this in 4-5 lines using PBDS bt obv. they will not allow us to use PBDS.

[@arshadmanxoori07]

How can i think that, it will be solve using merge sort ??

[@shashankbhattacharya5861]

I am facing one issue with the code. would you care to have a look at my code? if yes, should i post it here or in a file i can attach?

[@ankitkushwaha6269]

Simple code in java public class Solution { static long count = 0; public static long getInversions(long arr[], int n) { mergeSort(arr, 0, arr.length - 1); return count; } public static long[] mergeSort(long[] arr, int lo, int hi){ if(lo == hi){ long[] base = new long[1]; base[0] = arr[lo]; return base; } int mid = (lo + hi) / 2; long[] left = mergeSort(arr, lo, mid); long[] right = mergeSort(arr, mid + 1, hi); long[] merge = merge2Sort(left, right); return merge; } public static long[] merge2Sort(long[] left, long[] right){ int i = 0; int j = 0; int k = 0; long[] merge = new long[left.length + right.length]; while(i < left.length && j < right.length){ if(left[i]

[@mohitratanpal27]

thx bro actually i did merge sort like this,but the video showed a different method,which after 45 min of debugging I understood😅

[@sjaishree2275]

guys one question ,how long did it take for you to solve one striver solution(some say it depends on question ,in that case tell avg time or time for this sol)

[@ishaanverma1969]

Can't we start from the right and hash the digits which occur, and then for each digit we encounter, check the dictionary to find out how many digits to the right are smaller than the current digit, and increment count by that number? This would take O(10) i.e. O(1) space and O(10n) i.e. O(n) time?

[@takeUforward]

Areh areh numbers can be huge, its not only 0-9

[@ishaanverma1969]

Oh right!

[@breakthecode8323]

Thanks For Your Efforts

[@kaashplays1393]

I didn’t understand why copying the temp array to the original array was necessary, since we already have the count of inversion and we can return it without modifying the original array. Anyone can help…?

[@SreyesSrinivasan]

Fabulous solution!

[@hunnysunaria2450]

can we do this without using temp array??

[@gautamarora6516]

Yes, you can. Use the concept of shell sort.

[@roushanraj8530]

Great work bro, please never stop these explanation videos 💯💯

[@karthikpaladugula5424]

Segmentation fault: (Help !!!) long long int inversionCount(long long arr[], long long N) { if(N==1) return 0; long long mid = (N-1)/2; long long s1=mid+1; long long left[s1]; for(int i=0;i

[@zahidcoc4646]

Following from bangladesh..😇😇

[@vartikasinghania9723]

amazing explanation, thank you for your efforts:)

[@ravishankar9247]

Note: Please start solving this SDE sheet if and only if you have studied DSA atleast twice or else you won't be able to understand even through the video solution of the problem.

[@saunaknandi1814]

What is the thought process behind the Merge sort?

[@satvrii]

Kitna accha samjhaate ho 🥲🥲💋

[@codingaid2753]

Such a easy way of explanation ThanKs @ striver

[@shivampokhriyal_]

MergeSort approach : 3:04

[@pradeepsaravanau]

javascript solution function mergeSortAndCount(arr) { let count = 0; helper(arr); return count; function helper(nums) { if (nums.length right[rightIndex]) { count += left.length - leftIndex; rightIndex++; } else { leftIndex++; } } leftIndex = 0; rightIndex = 0; let sortedArray = []; while (leftIndex < left.length || rightIndex < right.length) { if (leftIndex >= left.length || left[leftIndex] > right[rightIndex]) { sortedArray.push(right[rightIndex]); rightIndex++; } else { sortedArray.push(left[leftIndex]); leftIndex++; } } return sortedArray; } }

[@sahilchoudhary1473]

Great explanation

[@ritikdubey3338]

The way you teach, how can anyone one not understand 🔥🙏

[@harshkumargupta8538]

just the way i did.

[@xd9050]

A small tip for those who are watching this for the first time -understand merge sort properly before jumping into this

[@mukulbindal2303]

Bro, can you tell me whether waqar ahmed is Ses or PP .. plz I can't contact him anywhere

[@aadityaupadhyay6264]

PP

[@voldemort576]

what is sess or pp

[@willturner3440]

First video I used to watch at ×0.75

[@rajatagrawal7016]

thanks for the explanation

[@atharvameher5880]

Yo CAME UP WITH MY OWN SOLUTION Checks from back of array and maintains a stack of Smaller elements, if larger count is incremented Its like the naive approach but optimised class Solution { // arr[]: Input Array // N : Size of the Array arr[] //Function to count inversions in the array. static long inversionCount(long arr[], long N) { long count=0; int flag=0; ArrayListal=new ArrayList(); al.add(arr[(int)N-1]); for(int i=(int)N-1;i>=0;i--){ if(arr[i]

[@nimishgupta8357]

Cant we use set for the same? It will be quite easy to implement.

[@takeUforward]

how do you count numbers on left ? Subtracting iterators take O(n)

[@nimishgupta8357]

@@takeUforward It means with set the complexity will become O(n2) right. Thanks bhai

[@takeUforward]

Nimish Gupta yes bro.

[@ardhendureja3785]

No bhaiya set ke lower bound nikal lunga and deklunga usse bara elements kitne hai jo usse pahle aya hai

[@ardhendureja3785]

Time complexity is nlogn

[@rhythmbhatia8906]

Awesome explanation!

[@ashwinvarma9349]

bro, at line 52 and 53 why do we need to increment the count? only the 'merge' function is incrementing and returning the count not the '_mergeSort' func, right?

[@remmargorpp]

line 52 and 53 keep track of total count while the merge function counts the inv_count for the two current merging array and return it to line 52 and 53 adding up to total count.

[@aditikhandelwal135]

@takeUforward In interview thwy always ask us to code it or only explanation is enough???

[@takeUforward]

Explanation, then the code

[@code.tle_]

understood clearly..

[@harshdasila6680]

GFG SOLUTION: C++ Public: long long int mergeIt(long long arr[], long long temp[], long long left, long long mid, long long right) { long long inv_count=0; long long i=left; long long j =mid; long long k =left; while((i

[@varshasingh6627]

I didn't understand why we have counted the inversions so many times instead of one time in merge sort?

[@priyabratroutray8184]

you can pass a reference variable which only updates at the merge function void merge(long long *arr,long long *temp,int s,int mid,int e,long long int& x) { int i=s; int j=mid+1; int k=s; while(i

[@rocklee3254]

I thought this one and minimum no. of swaps required to sort an array are same

[@yashjain1492]

Thank you very much👍

[@ashwinvarma9349]

whats wrong in the code below? #include using namespace std; int merge(vector& nums, int start, int mid, int end){ int count = 0; int n1 = mid - start + 1; int n2 = end - mid; vector leftArray(n1); vector rightArray(n2); for(int i = 0; i < n1; i++){ leftArray[i] = nums[start + i]; } for(int i = 0; i < n2; i++){ rightArray[i] = nums[mid + 1 + i]; } int i = 0, j = 0, k = start; while(i < n1 && j < n2){ if(leftArray[i] = end) return 0; int count = 0; int mid = (start + end) / 2; count += mergeSort(nums, start, mid); count += mergeSort(nums, mid + 1, end); count += merge(nums, start, mid, end); return count; } int countInversions(vector& nums) { return mergeSort(nums, 0, nums.size() - 1); //return nums; }

[@yasaswinibingimalla4602]

Thank you sir

[@anshumaan1024]

better than gfg's explaination

[@bhushanbhosale2394]

bro link is wrong on sheet for this video...please look into it

[@sheikhaman6218]

Legends are watching this during online class🤣🤣 cos your way of solving a problem is so addictive

[@takeUforward]

Haha, what if your prof sees this comment 🤣

[@sheikhaman6218]

@@takeUforward then he will reward me with great internal marks, you know what i mean🤪🤣🤣

[@funenjoynilaypatel4553]

understood nicely 1-Aug-2022

[@hemanthvarmas]

Great Explanation as always! Thanks anna.😅

[@abhishekh_p2721]

This is awesome ❤

[@sanjeevchandranm2818]

I used this algo but one of the case failed while in coded in codeninja

[@goswami46457]

Great explanation sir

[@ManojKumar-bk1kp]

Please, continue with this series closely following your videos.

[@gouravkumarshaw5467]

great explanation : D

[@rohitjaiswal2563]

You help us a lot!!!