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
#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.
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.
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
@@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.
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
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...
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.
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 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.
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
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
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!
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]
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
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
@@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
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
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
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).
@@mohdnabeel702 nope thats not right , if 6 is not greater than twice of3 we increment "i" which means for 13 we will check if 3 could be a possible value so we are not missing out on any case ig
@@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
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
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);
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 ??
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?
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
cpp code if u want it.. dont know why the inside loop counting didnt works u need a new loop itseems code: class Solution { public: int merge(vector& nums , int low ,int mid, int high){ vector temp; int left = low; int right = mid+1; int cnt = 0; // new loop only for counting for(int i=low;i
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); }
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.
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?
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:)
@@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.
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; } };"
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
@@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.
class Solution { public void merge(int [] nums, int low, int mid, int hi){ ArrayList temp = new ArrayList(); int left = low; int right = mid+1; while(left
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
Hi Striver, I am Btech CSE 4th sem student. I have been following your RUclips 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.
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
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
Did you clear the interview?
The amount of clarity you have over concepts is truly remarkable! Hope to be as good as you one day.
#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.
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.
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
@@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.
@@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
Thanks Nirupam!!
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
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...
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
i was also using this logic but no this doesnt work ...maybe i am doing something wrong
It is better.
It's similar to inversion of array question. Just change
arr[i] > arr[j] to arr[i]/2 > arr[j] and you are done. Same Complexity
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
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.
use typecasting
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]
@@wttc4 this worked and code is submitted but can you please explain how it works
@@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.
@@wttc4 so basically the whole multiplication is taking place in long long i assume right ?
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
yup... ease this using upper bound
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
Understood! Another super amazing explanation as always, thank you so so SO much for your effort!!
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!
Your effort in making us understand the whole approach is commendable! Thanks a lot :)
Crystal Clear Explaination Understood in one GO ❤️🥇💯
Understood, You are The Best Striver
Perfectly Explained and Best series
Thanks bhai maja aya question solve krke, pata nhi kaise batau kitna maza aarha hai code karke abb.
a[i] > 2* a[right] condition may cause overflow...
rewrite as 0.5 * a[i] > a[right]
thanks
it worked thanks
or cast 2*a[right] to long
thanks a lot
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]
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
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
@@shikher4559 yes is this working ?
@@btechstudent1620 its working with a bit modification
1) run a loop for calculating pairs separately
2) do the same as this code
@@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
Understood, You are The Best Man!
Understood your previous explanation and current explanation both are good
Toughest problem understood as a piece of cake..
truly understand , nicely explained
thankyou for such a wonderful explanation striver✨✨
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
Did your code get accepted ?
@@abhinavraj6507 yes this will work.
Great Explanation
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
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).
i got the same doubt!!!!
did u get clarity?
@@mohdnabeel702 nope thats not right , if 6 is not greater than twice of3 we increment "i" which means for 13 we will check if 3 could be a possible value so we are not missing out on any case ig
understood, thanks for the great explanation
Understood it very well
Thanks for this amazing video
can someone explain why the if condition i put in else block would not work here
while(left
yes i have the same doubt it should work i felt i was the only one
Can someone explain this.Thanks in advance:)
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.
@@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
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
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
got it , Striver thank you
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
actually that should be the way it will have analogy between count inverison and this
Awesome explanation.
Amazing guy!
Amazing. Thank you.
Can't thank you enough Man!!
According to me, it's a medium level question... because I understood clear concept of mergeSort by your tutorial. Thankyou Striver
Great explanation
Thanks brother!❤
Understood✅🔥🔥
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 ??
the right pointer stops at one place greater , we are adding total number of elements before the right pointer(excluding right)
Thanx brother
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?
The articles are new, if you go though them, they are updated... We did not create a new article, instead updated the older ones.
Medium questions are a combination of two easy questions
And hard questions are combination of two medium problems
That's my observation till now
understood striver💥
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
Done on 9 Jan 2025 at 12:02
Place : Study Room 2 , Hotel 5, IIT Bombay
int countPairs(vector &arr, int low, int mid, int high) {
int right = mid + 1;
int cnt = 0;
for (int i = low; i
UNDERSTOOD !!
Wondering if we can solve this through TreeSet
Understood 🙏🏻
thanks striver💙
use long long to avoid integer overflow!
(mid+1)-i will also work just fine but keep that inside the while loop
Maamaamiyaa!!!
understood 💗
cpp code if u want it..
dont know why the inside loop counting didnt works u need a new loop itseems
code:
class Solution {
public:
int merge(vector& nums , int low ,int mid, int high){
vector temp;
int left = low;
int right = mid+1;
int cnt = 0;
// new loop only for counting
for(int i=low;i
Understood 👍
understood
😍😍😍😍😍
understood👍
Can you please explain same codes in java
understood sir
understoood🤩
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++;
}
In leet code its taking 232 MB ..means temp arr taking extra spaces right striver??
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.
Superb
superb
Sir it is also showing time limit exeeded error
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?
start by learning english
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:)
Because if we compare with twice the values, the array doesnot end up being sorted in each iteration, which will contradict our assumption.
your code will work correct thought process
@@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.
why cnt is not added with merge...In counting pairs cnt is added with merge..but here its not..why
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;
}
};"
THANKU BHAI
will this code work for already sorted array??
because for sorted array, every left element will be smaller than element in right/right array???
😂😂there will be no pair in that case so obviously count will be 0
Understood.
Understood!
Please make an {Android App Development} course
I am a full stack dev, I have no experience in it 😅
@@takeUforward Please make a full stack web dev course
@@tapansonak1431 There are diff courses on yt watch out that for instance hitesh choudhary, and some foreign yt channels/ udemy courses which are good
understood :)
UNDERSTOOD;
understood
how to show all the pairs can you help me out or anyone pls
cant we do this using map?
how?
count inversion logic is working fine whats wrong with this function
int i = low;
int j = mid+1;
while(i
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
see do the sorting and counting separately
@@abhijeettripathi7615 why can't we do it together
@@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.
Am I the only one who understood everthing as crystal clear till dry run but during code the mind stopped working
happened initiallty will take time ..learn basics of coding first
class Solution {
public int reversePairs(int[] nums) {
return countInversionsRec(nums);
}
int countInversionsRec(int[] arr){
int l=arr.length;
if(l
class Solution {
public void merge(int [] nums, int low, int mid, int hi){
ArrayList temp = new ArrayList();
int left = low;
int right = mid+1;
while(left
Understood
Understood :)
Aug'9, 2023 09:11 pm
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
Understood.............
Hi Striver, I am Btech CSE 4th sem student. I have been following your RUclips 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.
Follow his A2Z sheet.
Ubderstood ❤
Thanks
am i tripping or he keeps saying merge short?
Understood
Got it
understood :)
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