Reverse Pairs | Hard Interview Question

[@abhishekverma7604]

i have been asked this question in my intuit online assesement for an intern role... and i know how inversion count principal works..so i did it comfortably.. but that too only bcoz of old video of striver.... thanks bhya ..love u

[@sanjayav6461]

Did you clear the interview?

[@shubhamagarwal1434]

#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.

[@junaid61747]

The amount of clarity you have over concepts is truly remarkable! Hope to be as good as you one day.

[@nirupamsuraj1634]

Those people wondering why cant we just multiply a 2 in the count inversion logic. Because if we compare with twice the values, the array doesnot end up being sorted in each iteration, which will contradict our assumption. Try yourselves with different testcase, you will get it.

[@HarshKumar-ip5nr]

Where I am missing, can you pin point with example class Solution { private: int count=0; void merge( vector &nums, int start, int mid, int end){ vector temp; int i=start; int j=mid+1; while( i

[@nirupamsuraj1634]

@@HarshKumar-ip5nr bro try not doing temp.pushback inside nums[i] >2*nums[j]. It is not the logic for sorting. nums[i] >2*nums[j] should be handled inside another while loop seperately, and just increase your count there and nothing else. Keep the while loops for sorting as it is in merge sort.

[@nirupamsuraj1634]

​@@HarshKumar-ip5nr Try referring this python code def merge(nums,l,m,r,count): arr1 = nums[l:m+1] arr2 = nums[m+1:r+1] n1 = len(arr1) n2 = len(arr2) i,j,k = 0,0,l ptr1,ptr2 = 0,0 while ptr1

[@puneetnj]

Thanks Nirupam!!

[@manvendrasingh4369]

But I have not changed the original logic of merge sort but I write this new logic separately inside that else in if-else. So can any one tell me why it is still wrong because now it is not disturbing sorting. okay I got it

[@ravishkumar6060]

The energy with you explain the problem and it's solution is really amazing Sir!!! Your teaching methodology is so simple and convincing that even if you make 1-2hr video for a problem, I can watch it with 100% attention...

[@AdityaSharma-er3gs]

25:09 Here you can also use private static int countPairs(int[] nums, int s, int m, int e){ int i = s; int j = m+1; int count = 0; while(i

[@12anikeshguhaxa5]

i was also using this logic but no this doesnt work ...maybe i am doing something wrong

[@sohilpathan9006]

In Leetcode it will give buffer overflow because int can't store 2x value of INT_MAX So u can use nums[i] > (long long)2*nums[right] OR 0.5*nums[i] > nums[right] any one of them in while loop condition in countPairs.

[@shashanktripathi6277]

use typecasting

[@wttc4]

or you can do like this also: nums[i] > 2LL * nums[right]. (we're comparing int to long long) To be more safe, do this: 1LL * nums[i] > 2LL * nums[right]

[@shivanshpatel1898]

@@wttc4 this worked and code is submitted but can you please explain how it works

[@wttc4]

@@shivanshpatel1898 simply 2 means 2 is int, whereas 2LL means 2 is of type long long. 1LL * nums[i] means we are multiplying long long and int, so 1LL * nums[i] is of type long long. Similarly, in some cases, you can also do 0LL + some_int to make the type of result to long long.

[@lakshsinghania]

@@wttc4 so basically the whole multiplication is taking place in long long i assume right ?

[@namanchandak1532]

here is more optimized code you also should apply binary search in the counting pair function instead of increasing right because right portion of the array is sorted int countP(vector& nums, int l, int m, int h) { long long int right=m+1,cnt=0; for(int i=l;i

[@sunny_23561]

yup... ease this using upper bound

[@yashwanthyerra2820]

But it is taking more time to execute than this class Solution { private int countAndMerge(int[] nums, int left, int mid, int right) { int count = 0; int j = mid + 1; for (int i = left; i

[@mehulthuletiya497]

00:40 Problem Statement 00:59 Explanation 02:58 Brute-force approach 03:03 Intuition 03:28 Pseudocode 04:21 Complexity 04:55 Optimal solution 05:22 Intuition 14:20 Approach + Dry-run 22:06 Pseudocode 25:16 Code 29:16 Complexity

[@SHASHANKRUSTAGII]

i did this question during my placement prep and yes i saw with my naked eyes how we can make use of merge sort and in general count inversion in nlogn time :) Good work striver!

[@cinime]

Understood! Another super amazing explanation as always, thank you so so SO much for your effort!!

[@mdzaidhassan426]

Your effort in making us understand the whole approach is commendable! Thanks a lot :)

[@neerajkumar-ts6om]

Thanks bhai maja aya question solve krke, pata nhi kaise batau kitna maza aarha hai code karke abb.

[@shyampawar8893]

Perfectly Explained and Best series

[@aafilburner]

a[i] > 2* a[right] condition may cause overflow... rewrite as 0.5 * a[i] > a[right]

[@saisri5953]

thanks

[@harshjha1616]

it worked thanks

[@SairamSudiReddy]

or cast 2*a[right] to long

[@YN__YN]

thanks a lot

[@wttc4]

or you can do like this also: nums[i] > 2LL * nums[right]. (we're comparing int to long long) To be more safe, do this: 1LL * nums[i] > 2LL * nums[right]

[@juhichoudhary9281]

Understood, You are The Best Striver

[@ksankethkumar7223]

Toughest problem understood as a piece of cake..

[@jeeveshkumar9682]

i thought of sorting the whole array and then using two pointers to compare the values and increase the count accordingly. But the problem with this solution is that the constraint of keeping i

[@shikher4559]

are you talking about thIs solution ? public int merge(int[] arr, int low, int mid, int high){ int left = low; int right = mid+1; int pairs = 0; ArrayList temp = new ArrayList(); while(left

[@btechstudent1620]

@@shikher4559 yes is this working ?

[@shikher4559]

@@btechstudent1620 its working with a bit modification 1) run a loop for calculating pairs separately 2) do the same as this code

[@078_garlapatilikhitreddy8]

​@@shikher4559counting the pairs seperately is fine i thought while merging we can modify the count as with counting inversion. After doing a dry run i understood that I have count the pairs seperately and then do the merging

[@dayashankarlakhotia4943]

Understood your previous explanation and current explanation both are good

[@cricketobserver178]

Medium questions are a combination of two easy questions And hard questions are combination of two medium problems That's my observation till now

[@055_meetmakwana9]

Understood, You are The Best Man!

[@ShahNawaz-cx3pi]

Count Pair function can also be implemented as:- int CountPairs(vector&arr,int low,int mid, int high){ int i = low; int j = mid+1; int cnt = 0; while(i

[@abhinavraj6507]

Did your code get accepted ?

[@shaikhmoin849]

@@abhinavraj6507 yes this will work.

[@242deepak]

Easier way: class Solution { public: int merge(int l,int mid,int r,vector &nums) { vector temp; int i=l,j=mid+1,count=0; while(i

[@abhijeettripathi7615]

actually that should be the way it will have analogy between count inverison and this

[@Manishgupta200]

According to me, it's a medium level question... because I understood clear concept of mergeSort by your tutorial. Thankyou Striver

[@vikashH-h1v]

int countPairs(vector &arr, int low, int mid, int high) { int right = mid + 1; int cnt = 0; for (int i = low; i

[@narasimhann2814]

Can someone tell why the below fails. It clears 33 TC but not all. Its a modification to no of inversion pair where for each element in right I find the left array range to satisfy the condition int merge(vector&arr, int start,int mid,int end){ int n1 = mid-start+1; int n2 = end-mid; int i,j,x; long long count=0; vector a1(n1); vector a2(n2); for(x=0,i=start; i

[@kaichang8186]

understood, thanks for the great explanation

[@RohitKumar-dy2gc]

thankyou for such a wonderful explanation striver✨✨

[@iamxpossible]

use long long to avoid integer overflow!

[@kavyahegade6477]

whle comparing, if one element from 2nd array does not form a pair with an element in 1st array, you said you will miss out the next element. but in reality we do not. because we increment the 1st array i des and check again, if it works then all other works, so count inversion algorithm works

[@mohdnabeel702]

In count inversion we are trying to find the smaller number suppose we are at 6 and 3, we see 3 is smaller, we add 3 to our answer list, and increment the right pointer to compare next pointer with 6, missing out on comparing 3 with the next elements in left array. (this is how I understood).

[@vikasbagri1225]

Understood it very well Thanks for this amazing video

[@paneercheeseparatha]

Amazing guy!

[@AdityaSingh-uy8ms]

UNDERSTOOD !!

[@gyanendrasaurav877]

(mid+1)-i will also work just fine but keep that inside the while loop

[@nikhilchobhiyal]

Maamaamiyaa!!!

[@studynewthings1727]

Awesome explanation.

[@inspiringzone12]

Great explanation

[@akilesh6379]

understood sir

[@praveensoni1119]

Can't thank you enough Man!!

[@torishi82]

Amazing. Thank you.

[@akshaygill4692]

can someone explain why the if condition i put in else block would not work here while(left

[@shivasai7707]

yes i have the same doubt it should work i felt i was the only one

[@kishore4262]

Can someone explain this.Thanks in advance:)

[@mohdnabeel702]

Same thing we just have to modify the if condition rather than doing arr[i]>arr[j] Iam using arr[i] > 2*arr[j]; Both are getting accepted.

[@mohdnabeel702]

@@shivasai7707 It works import java.util.ArrayList; class Solution { public int reversePairs(int[] nums) { return mergeSort(nums,0,nums.length-1); } public static int mergeSort(int[] arr,int lo, int hi){ if(lo >= hi) return 0; int mid = (lo + hi)/ 2; int counter=mergeSort(arr,lo,mid); counter+=mergeSort(arr,mid+1,hi); counter+=countPairs(arr,lo,mid,hi); merge(arr,lo,mid,hi); return counter; } public static void merge(int []arr,int lo,int mid,int hi){ List tempList = new ArrayList(); int i = lo; int j = mid+1; while(i

[@kishore4262]

Hey @@mohdnabeel702 ; can you explain me whats wrong with this: class Solution { public: void merge(vector &nums,int low,int mid,int high,int &c){ int i = low; int j = mid+1; vector temp; while(i

[@shashvatsinghal2574]

I did this using a multiset, got a time complexity of O(3nlogn) but still i got tle "class Solution { public: int reversePairs(vector& nums) { multiset ms; for(auto i:nums) ms.insert(i); long long final=0; for(int i=nums.size()-1;i>=0;i--){ auto it=ms.find(nums[i]); ms.erase(it); auto lb = ms.lower_bound((2 * (long long)nums[i])+1); final += distance(lb, ms.end()); } return final; } };"

[@DeadPoolx1712]

UNDERSTOOD;

[@harshilpatel3205]

Understood 🙏🏻

[@googleit2490]

Understood :) Aug'9, 2023 09:11 pm

[@YourCodeVerse]

Understood✅🔥🔥

[@venup2813]

understood striver💥

[@umangsharma7364]

Wondering if we can solve this through TreeSet

[@aniketkhorwal7289]

thanks striver💙

[@shubha_jagadeesh]

understood 💗

[@AjaySaini-hc9ho]

Thanks brother!❤

[@akashsingh9301]

THANKU BHAI

[@hemantpatel1413]

Understood.

[@AppaniMadhavi]

Superb

[@mohan-xx8ih]

Leetcode solution class Solution { void merge(vector &nums, int low, int mid, int high){ int *temp = new int[high - low + 1]; int i = low; int j = mid + 1; int k = 0; while((i

[@anshbathla3850]

Am I the only one who understood everthing as crystal clear till dry run but during code the mind stopped working

[@anithusiast.]

happened initiallty will take time ..learn basics of coding first

[@harshitpatil6138]

Ubderstood ❤

[@aayush5474]

am i tripping or he keeps saying merge short?

[@sarangkumarsingh7901]

Understood.............

[@suheabkhan2546]

Great explanation.. understood.... Why is the notes for the previous videos , are linked to old articles.. will the new articles replace them or new articles will not be written for them?

[@takeUforward]

The articles are new, if you go though them, they are updated... We did not create a new article, instead updated the older ones.

[@AmanSingh-yc4cw]

Understood 👍

[@HoneySingh-yp7zc]

superb

[@ashnakohli6763]

class Solution { public int reversePairs(int[] nums) { return countInversionsRec(nums); } int countInversionsRec(int[] arr){ int l=arr.length; if(l

[@anshulrai6058]

understood👍

[@Appcgubn]

why cant we use treemap and traverse through the array and store the occurences of the number and checking them upto the condition verifies in the tree map

[@dewanandkumar8589]

Understood

[@AmanKumarSinhaOfficial]

Please make an {Android App Development} course

[@takeUforward]

I am a full stack dev, I have no experience in it 😅

[@tapansonak1431]

@@takeUforward Please make a full stack web dev course

[@lakshsinghania]

@@tapansonak1431 There are diff courses on yt watch out that for instance hitesh choudhary, and some foreign yt channels/ udemy courses which are good

[@avijeetswain7101]

25:00 can somebody help me please? Here we are using a zero index array so when we are doing (right -(mid+1)) can't we write it as (right-(mid+2)) we also did in count inversion (mid -(left+1)). Or (right-(mid+1)) means how far right is from its initial position mid+1 ??

[@S.s-tz9fo]

the right pointer stops at one place greater , we are adding total number of elements before the right pointer(excluding right)

[@avijeetswain7101]

Thanx brother

[@shivasai7707]

im totally confused if 6 is greater than twice of 2 then 13 21 25 will be greater than twice of 2 as they are greater count of inversions method should work striver please help thanks:)

[@nirupamsuraj1634]

Because if we compare with twice the values, the array doesnot end up being sorted in each iteration, which will contradict our assumption.

[@abhijeettripathi7615]

your code will work correct thought process

[@nirupamsuraj1634]

@@abhijeettripathi7615 the code will work as long as you seperate the counting logic from sorting logic. In sorting logic dont compare with twice the values.

[@bhagyashri863]

understoood🤩

[@reassume4826]

I dont get why do we need to put this function before merge method? When I am putting in merge method, it gives wrong answer. Can anyone point out why? I put this logic before actual merge operation inside merge function, still giving wrong answer.

[@PriyaSharma-v8u]

Understood!

[@jeetoppers3150]

understood 😍😍😍😍😍

[@sarvansingh6736]

Got it

[@AbjSir]

understood

[@culeforever5408]

understood :)

[@gauravkabdwal309]

Understood

[@akshatverma8086]

Hey @striver , recently I started doing ur a2z DSA sheet. After learning array from ur playlist I am doing string but the problem I am able to solve the questions even medium level. What approach should I apply. I give 20 mins to understanding n more and then code. It gives results 60%but not 💯. How should I start?

[@vishwasgupta6149]

start by learning english

[@____priyanka_b_]

Can you please explain same codes in java

[@priyotoshsahaThePowerOf23]

In leet code its taking 232 MB ..means temp arr taking extra spaces right striver??

[@anuragroy9045]

#Understood

[@saillaanil6948]

can anyone please help me, why this code is not working int merge(vector &arr, int low, int mid, int high) { vector temp; // temporary array int left = low; // starting index of left half of arr int right = mid + 1; // starting index of right half of arr int count=0; //storing elements in the temporary array in a sorted manner// while (left

[@abhijeettripathi7615]

see do the sorting and counting separately

[@saillaanil6948]

@@abhijeettripathi7615 why can't we do it together

[@edu_77218]

​@@saillaanil6948This is because even if arr[left] > 2*arr[right] is not satisfied, right will be incremented as arr[left] > arr[right]. To calculate cnt, right has to be incremented only when arr[left] > 2*arr[right] is true. So, this requires an extra while loop.

[@vikasgupta1828]

Thanks

[@GeneralistDev]

Why below code doesn't work ? class Solution { int cnt = 0; void merge(vector &nums, int s, int mid, int e) { vector temp; int i = s, j = mid + 1; while (i

[@aayushichouhan775]

understood

[@akshayvakharia7552]

Hi @takeUForward UNDERSTOOD. But can we align with the previous solution by tricking a bit like else { //For this question condition change int tempPointer = leftPointer; while (tempPointer (2 * input[rightPointer]))) { tempPointer++; } if (input[tempPointer] > (2 * input[rightPointer])) { count += (mid - tempPointer + 1); } // Existing Merge code list.add(input[rightPointer]); rightPointer++; }

[@pc8803]

Hi Striver, I am Btech CSE 4th sem student. I have been following your KZbin channel for a 2-3 weeks now. I had a doubt about your SDE Sheet and A-Z DSA sheet .That which one should I complete first I already know basics of Cpp, Java and DSA ( I had started doing 375Qs sde sheet of apna college ) I was able to solve questions of problem but my solutions were not optimal approach . Please help.

[@113_manshi4]

Follow his A2Z sheet.

[@kamleshverma9724]

will this code work for already sorted array?? because for sorted array, every left element will be smaller than element in right/right array???

[@OrderEmperor]

😂😂there will be no pair in that case so obviously count will be 0

[@vibhutijoshi07]

cant we do this using map?

[@kurma.4932]

how?

[@abhimanyuthapliyal5823]

US

[@luckshaeey]

understood :)

[@GeetainSaar]

😊😊

[@m.rnaganathan7492]

how to show all the pairs can you help me out or anyone pls

[@alphaCont]

ok

[@karthikarthik1795]

Sir it is also showing time limit exeeded error

[@satvrii]

❤❤❤

[@apoorva5961]

😇

[@ananthalakshmi]

int cnt = 0; class Solution { public: void merge(vector & nums, int left, int mid, int right){ int i = left; int j = mid + 1; int k = 0; int ans_arr[right - left + 1]; while(i

[@banothutharun2743]

wow

[@prajwalshaw9217]

void merge(vector&arr,int low,int mid,int high) { vectortemp; int left=low,right=mid+1; while(left

[@prajwalshaw9217]

Can anybody say what is wrong with my code...?...it's giving wrong answer.