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
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
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.
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...
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
#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.
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
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]
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 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
@@shikherdwivedi4559counting 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
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);
@@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
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 ??
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
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 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.
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?
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?
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 @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); }
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
Hi Striver, I am Btech CSE 4th sem student. I have been following your UA-cam 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.
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
Mine is still giving me TLE, why ? class Solution { public: int countPairs(vector arr, int low, int mid, int high){ int cnt=0; int right=mid+1; for(int i=low;i
@@user-xb1st2pm6i idk, but check this code, its giving me proper value. Both of our codes look similar but one is giving TLE and other is not 🤔 class Solution { public: void merge(vector &arr, int s, int mid, int e) { int left = s; int right = mid + 1; vector temp; while(left
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.
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
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 ?
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
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...
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 ?
#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.
Your effort in making us understand the whole approach is commendable! Thanks a lot :)
Perfectly Explained and Best series
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
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
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!
Thanks bhai maja aya question solve krke, pata nhi kaise batau kitna maza aarha hai code karke abb.
Understood! Another super amazing explanation as always, thank you so so SO much for your effort!!
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]
Toughest problem understood as a piece of cake..
Understood, You are The Best Striver
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
Medium questions are a combination of two easy questions
And hard questions are combination of two medium problems
That's my observation till now
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.
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
@@shikherdwivedi4559 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
@@shikherdwivedi4559counting 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!
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
Amazing guy!
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
Understood your previous explanation and current explanation both are good
thankyou for such a wonderful explanation striver✨✨
Understood it very well
Thanks for this amazing video
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
Wondering if we can solve this through TreeSet
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
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).
According to me, it's a medium level question... because I understood clear concept of mergeSort by your tutorial. Thankyou Striver
Amazing. Thank you.
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;
}
};"
Understood 🙏🏻
UNDERSTOOD;
class Solution {
public int reversePairs(int[] nums) {
return countInversionsRec(nums);
}
int countInversionsRec(int[] arr){
int l=arr.length;
if(l
(mid+1)-i will also work just fine but keep that inside the while loop
Can't thank you enough Man!!
Great explanation
Awesome explanation.
Maamaamiyaa!!!
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.
Thanks brother!❤
In leet code its taking 232 MB ..means temp arr taking extra spaces right striver??
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.
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?
start by learning english
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 striver💥
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
superb
thanks striver💙
Understood✅🔥🔥
Understood.
THANKU BHAI
Can you please explain same codes in java
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
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++;
}
Understood 👍
Superb
Understood.............
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
Understood :)
Aug'9, 2023 09:11 pm
how to show all the pairs can you help me out or anyone pls
Sir it is also showing time limit exeeded error
understood
😍😍😍😍😍
understood :)
Hi Striver, I am Btech CSE 4th sem student. I have been following your UA-cam 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.
Got it
Thanks
understoood🤩
Am I the only one who understood everthing as crystal clear till dry run but during code the mind stopped working
Ubderstood ❤
ok
#Understood
😊😊
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
void merge(vector&arr,int low,int mid,int high)
{
vectortemp;
int left=low,right=mid+1;
while(left
Can anybody say what is wrong with my code...?...it's giving wrong answer.
Its giving me TLE on LeetCode, but the code passed all cases on GFG
It works in leetcode, only change needed: 2LL * arr[right]
@@takeUforward thanks!! working now
Mine is still giving me TLE, why ?
class Solution {
public:
int countPairs(vector arr, int low, int mid, int high){
int cnt=0;
int right=mid+1;
for(int i=low;i
@@user-xb1st2pm6i idk, but check this code, its giving me proper value. Both of our codes look similar but one is giving TLE and other is not 🤔
class Solution {
public:
void merge(vector &arr, int s, int mid, int e)
{
int left = s;
int right = mid + 1;
vector temp;
while(left
@@user-xb1st2pm6i take array by reference in count Pairs function
😯
wow
❤❤❤
Understood
understood
Understood!
understood :)
Understood
Understood
Understood
Understood
understood
understood
understood
understood