Those who didn't understood this part -----> low = max(0,k-m), high = min(k,n); Let's understand with the help of the example used in 22:30 . Here n = 4 and m=6 and k=7. Since k>m , so we can't take 0 elements as the lowest no. of elements picked from array1 . It should be (k-m) i.e. 7-6=1 and the high is obvious min(k,n) i.e min(7,4) i.e 4 (4 elements can be taken at max from array 1) My Code: #include int median(vector& nums1, vector& nums2,int k){ int n=nums1.size(),m=nums2.size(),x=k,sum=0; int l = max(0,k-m) ,r = min(k,n) ,l2,r2,l1,r1; int cut1 = (l+r)/2,cut2 = x-cut1; while(lr2){ r = cut1-1; } else if(l2>r1){ l = cut1+1; } else{ return max(l1,l2); } } return 0; } int ninjaAndLadoos(vector &nums1, vector &nums2, int n, int m, int k) { int medi; if(n
Bro but what if k=15 and m =10, n= 20 then low comes out low = 5, and high = 15 now if we doing operations on big 20 size array then why we cant choose any 0 to 15 or 1 to 16 ..... May be i am somwhere confused , which array to consider , please clear it
@@gauravshukla5203 all time we are taking total k elements from both array for example if k=5, 2 from 1st and 3 from 2nd array, so every time there will be k elements total from both array, at once, l1,l2,r1,r2 condition may hold true so kth element will be max of last two
A great thanks to you striver, I have learned this problem by heart and have also capable of writing 4-page notes of this by myself. You are such a great teacher. You are changing the way of education from your hard work. Keep doing this.
I guess he meant in Binary search the main thing is to get the search space lower bound and upper bound half of the work is done when you have your search space.
Hi bhaiya,as you have mentioned in the SDE sheet,bits are rarely asked in interviews,so it will be a great help for us,if you can cover that topic at last and continue with Stack and Queues,ie the next topic
First thank you very much! It is an awesome solution. But I have a question regarding Time Complexity, I believe it should be O(log(min(n, m, k))) cause the case of k < m and also k < n. This binary search is on the range of number of elements taken from smaller array.
class Solution { public long kthElement( int arr1[], int arr2[], int n, int m, int k) { if(n>m){ return kthElement(arr2,arr1,m,n,k); } int low=Math.max(0,k-m), high=Math.min(k,n); while(low>1; int cut2=k-cut1; int l1=cut1==0?Integer.MIN_VALUE:arr1[cut1-1]; int l2=cut1==0?Integer.MIN_VALUE:arr1[cut1-1]; int r1=cut1==n?Integer.MAX_VALUE:arr1[cut1]; int r2=cut1==m?Integer.MAX_VALUE:arr1[cut1]; if(l1
you just need to find kth smallest number all in all. It might seem complicated but it basically is to ensure that th elements are smaller than leftover not chosen elements and we dont compare it with its own array because that particular array is sorted so just need to keep a check of the array for a particular element.
Had this question come up on an interview today. Nailed the pointer approach but fumbled on the binary search approach... Jeeze that required some out of the box thinking
can anyone find out the mistake, my code (in c++) seems to be the same as the logic: class Solution{ public: int kthElement(int arr1[], int arr2[], int n, int m, int k) { // if(m < n) // return kthElement(arr2, arr1, m, n, k); int lo = 0, hi = n; if(k > n - 1) lo = k - m; else if(k < n / 2) hi = k; while(lo
Hi Striver and Everyone in the Comment Section ! I attempted the problem with this same method but in the function after finding l1,l2,r1 and r2. I added below given conditions if(l1==INT_MIN) // If not selecting any element from the first array, then return answer from the second array return arr2[k-1]; if(l2==INT_MIN) // Similarly, if we are not selecting any element from the second array we return the answer from 1st array return arr1[k-1]; if(r1==INT_MAX || r2==INT_MAX) // If one of the array is completely considered in the answer we have reached the solution thus return max(l1,l2) return max(l1,l2); But due to some reason, the code is missing on one of the TC on GFG. Can anyone please explain to me where I am getting wrong. Thanks in Advance.
code given in TUF website is little wrong, the the line int low = max(0,k-m), high = min(k,n); given in website has m,n interchanged just do it int low = max(0,k-n), high = min(k,m); and remove all of your edge caes and it will work like charm Thank me later
@Monil Charola, the conditions which you have introduced are wrong and that is why it is giving the wrong answer. Let us take an example test case:- arr1-> [6] arr2-> [1,2,3,4,5,7,8,9,10,11] k=8 Your code will give the asnwer=arr2[7] which is 9 but the correct answer is 8. The reason which I can deduce from your conditions is that: -> If we are not selecting any element from the first or second array, then you are neglecting that whole array and only considering the other array but that is not the case. Even if we are not selecting any element from an array, then also that array will contribute to our answer in the above case "6" from the first array will come at the 6th position of our final sorted array but as per your condition you will return arr2[k-1] which will be our 7th element of the second array and not the final sorted array because you have neglected the whole "arr1". This is the reason your code is giving the wrong answer. Hope you understood, if you find any difficulty understanding the reason, you can ask me again🙌.
Hi, I was running the below test case arr1 = {1, 5,9} arr2 = {4,7,11,18,19} k = 7 The code fails for this test case. Answer should be 18. Upon trying to understand I think the below logic is causing the test case to fail. int low = max(0,k-m), high = min(k,n); Can anyone explain if I am doing something wrong here ?
Hello Striver! I'm Smeet. This code will fail in test cases where k - m > m. Why? Because the low will be initialized greater than high, resulting in skiping the execution of while loop. Hence, the correct initialization should be : int low = max(0 , min(k - m , m)); This will take care of the test cases. And Thank you so much for this valuable content.
@satvikshrivastava5840 You might be having some bugs, Kindly refer to this code : #include using namespace std; int ninjaAndLadoos(vector &row1, vector &row2, int m, int n, int k) { if(m > n){ return ninjaAndLadoos(row2 , row1 , n , m , k); } int low = max(0 , min(k - m , m)); int high = min(m , k); int cut1; while(low
if somebody's solution is failing for some test cases on gfg use this code intuition is same public long kthElement( int arr1[], int arr2[], int n, int m, int k) { if(arr2.length
@@yadneshkhode3091 From the conditions, we can conclude that "low" cannot be "less than 0" and "high" cannot be "greater than k". So, our cur1 will be at max "k/2" in the starting and as we move further, we are updating our low and high to "cur1+1" and "cur1-1" which implies our low and high will always lie "between 0 and k". Since cur1 is calculated as (low+high)/2, we can say it will never become "greater than k". Hope you understood🙌.
It is not working when k=10 for your two arrays. Actually here mid value is greater than size of smaller array. That gives run time error so to avoid that we will work on larger array rather than working on smaller array
i have understood the code. but there is one thing: this code gives wrong ans when submitted for all test cases on gfg. Also i dont know why but it also gives TLE in some cases. I thought may be i would have done something wrong but then i went to the take youforward site and pasted the code for this question from there but it passes only 1 test case. pllzz relply if someone has the solution............
same for java class Solution { public long kthElement( int arr1[], int arr2[], int n, int m, int k) { if(n>m){ return kthElement(arr2,arr1,m,n,k); } int low=Math.max(0,k-m), high=Math.min(k,n); while(low>1; int cut2=k-cut1; int l1=cut1==0?Integer.MIN_VALUE:arr1[cut1-1]; int l2=cut1==0?Integer.MIN_VALUE:arr1[cut1-1]; int r1=cut1==n?Integer.MAX_VALUE:arr1[cut1]; int r2=cut1==m?Integer.MAX_VALUE:arr1[cut1]; if(l1
Is it okay to go for a optimise solution for any question even if you're not sure about it's brute force approach? I mean is it necessary to know? And the other thing I'm stuck with is implementing the approach/solution into code. Also, whenever I read a question I know what to implement at this condition but I cannot write the solution in order or you can say in structurzied manner
if you will not say the brute force , the problem will be finished soon and interviewer will be ready with another extra problem for you ,so time management with brute force is a important step
DOUBT!!!! Isnt the binary search done on the smaller array so that not more than needed elements are taken (in the median problem half the total elements, and here k elements) but if we make sure the high is not more than k, it shouldnt matter what array we do binary search on, right? i tried accordingly, and my solution got accepted(GFG). Is there any other reason why binary search must be done on the smaller array? please reply if know the answer or maybe atleast have the same doubt guys..
c++ code: class Solution{ public: int kthElement(int arr1[], int arr2[], int n, int m, int k) { int p1 = 0, p2 = 0, i = 0, r = 0; while (i < k) { if (p1 >= n) { return arr2[p2 + k - i - 1]; } if (p2 >= m) { return arr1[p1 + k - i - 1]; } if (arr1[p1] < arr2[p2]) { r = arr1[p1]; p1++; } else { r = arr2[p2]; p2++; } i++; } return r; } };
Please watch our new video on the same topic: ruclips.net/video/D1oDwWCq50g/видео.html
Those who didn't understood this part -----> low = max(0,k-m), high = min(k,n);
Let's understand with the help of the example used in 22:30 . Here n = 4 and m=6 and k=7. Since k>m , so we can't take 0 elements as the lowest no. of elements picked from array1 . It should be (k-m) i.e. 7-6=1 and the high is obvious min(k,n) i.e min(7,4) i.e 4 (4 elements can be taken at max from array 1)
My Code:
#include
int median(vector& nums1, vector& nums2,int k){
int n=nums1.size(),m=nums2.size(),x=k,sum=0;
int l = max(0,k-m) ,r = min(k,n) ,l2,r2,l1,r1;
int cut1 = (l+r)/2,cut2 = x-cut1;
while(lr2){
r = cut1-1;
}
else if(l2>r1){
l = cut1+1;
}
else{
return max(l1,l2);
}
}
return 0;
}
int ninjaAndLadoos(vector &nums1, vector &nums2, int n, int m, int k) {
int medi;
if(n
Thanks for saving time 🙏🏻
Really Thank you from bottom of my heart.
Bro but what if k=15 and m =10, n= 20 then low comes out low = 5, and high = 15 now if we doing operations on big 20 size array then why we cant choose any 0 to 15 or 1 to 16 .....
May be i am somwhere confused , which array to consider , please clear it
Thanks dear for explaining this 🙏
Thank you very much
There can't be any more simplified explanation video on RUclips other than this! Thank you for making this video!
I was seriously struggling to understand this from GFG's editorial thanks for this.
how do we determine that our last element will always be kth element?
@@gauravshukla5203 all time we are taking total k elements from both array for example if k=5, 2 from 1st and 3 from 2nd array, so every time there will be k elements total from both array, at once, l1,l2,r1,r2 condition may hold true so kth element will be max of last two
A great thanks to you striver, I have learned this problem by heart and have also capable of writing 4-page notes of this by myself.
You are such a great teacher.
You are changing the way of education from your hard work.
Keep doing this.
Before your explanation I made my logic..bcoz this was same as previous. Thanks for such a great explanation ..
were you able to write the code of edge case?
@@Rajat_maurya obviously it's clear once test case starts breaking.
Other than the edge cases, I was able to code this one on my own. Most optimised approach, maza agya
Did it by Own from using Concept of (Median of two sorted ) ... Thanxx Bhaiya for this Explanation
settting the right range of low and high initially is one of the most important steps
forgot to write 'Understood" 😊😊😊
I didn't understand that part, can you plz explain it to me?
I guess he meant in Binary search the main thing is to get the search space lower bound and upper bound half of the work is done when you have your search space.
@@exodus5948 Are or unki values vo kyu li..ye puchra tha
@@yushdecides Sorry I misunderstood
After median of sorted arrays this was really easy to understand!
Hi bhaiya,as you have mentioned in the SDE sheet,bits are rarely asked in interviews,so it will be a great help for us,if you can cover that topic at last and continue with Stack and Queues,ie the next topic
First thank you very much! It is an awesome solution. But I have a question regarding Time Complexity, I believe it should be O(log(min(n, m, k))) cause the case of k < m and also k < n.
This binary search is on the range of number of elements taken from smaller array.
Yes, you are correct. It is O(log(min(n, m, k))).
Usually (never) I don't comment on any YT videos but this time I want to say THANK YOU STRIVER 🥺
Understood 👍 The way you explained edge cases exemplifies your proficiency. Great work as always..
Clearly explained all the boundary cases. Keep up the good work!
class Solution {
public long kthElement( int arr1[], int arr2[], int n, int m, int k) {
if(n>m){
return kthElement(arr2,arr1,m,n,k);
}
int low=Math.max(0,k-m), high=Math.min(k,n);
while(low>1;
int cut2=k-cut1;
int l1=cut1==0?Integer.MIN_VALUE:arr1[cut1-1];
int l2=cut1==0?Integer.MIN_VALUE:arr1[cut1-1];
int r1=cut1==n?Integer.MAX_VALUE:arr1[cut1];
int r2=cut1==m?Integer.MAX_VALUE:arr1[cut1];
if(l1
You already explaining all the things in crystal clear manner so why people waste money and join other courses
Thank you sir for giving your precious time from your busy schedule....♥️♥️
It's my pleasure
you just need to find kth smallest number all in all. It might seem complicated but it basically is to ensure that th elements are smaller than leftover not chosen elements and we dont compare it with its own array because that particular array is sorted so just need to keep a check of the array for a particular element.
understood, thanks for the perfect explanation
Had this question come up on an interview today. Nailed the pointer approach but fumbled on the binary search approach... Jeeze that required some out of the box thinking
Great explanation btw!
@@geck1204 Hey, Which company's interview was this asked in?
@@ayeshaqaisar1651 Cruise
@@geck1204 Thanks
Thanks for the clear explanation brother. Understood well. Daily I'm waiting for ur videos.
I appreciate your observation of second edge case 👌👌
clearly explained !!
You are gem of ther person for students
Can't thank enough for this beautiful solution
can't be a more noble deed than to clear a student's concepts❤❤
Understood....Awesome Explanation......Especially handling edge cases was so fun
thanks a lot i have been stuck on this for way too long
Great explanation understood very well this complex binary search problem😅 thank you very much bhaiyaa
can anyone find out the mistake, my code (in c++) seems to be the same as the logic:
class Solution{
public:
int kthElement(int arr1[], int arr2[], int n, int m, int k)
{
// if(m < n)
// return kthElement(arr2, arr1, m, n, k);
int lo = 0, hi = n;
if(k > n - 1) lo = k - m;
else if(k < n / 2)
hi = k;
while(lo
Do write "understood" if you understood, motivates me :)
Insta: instagram.com/striver_79/
Telegram: bit.ly/tuftelegram
Yepp!
Clearly Understood Anna
understood.
Did you come up with this approach yourself ?
Understood
i think we can do these when validating the array. max(l1,l2) < min(r1,r2) then it is our desired array
I finally understood!!!! Thanks a lot!!💛
23:10 commenting to remember edge case....
bdw nice work bro
great explanation bhaiya
understood
Thanks sir! This is a beautiful explanation...the method itself is ingenious. Because of geniuses like you plebs like me will hopefully get a job :D
jai jinendra sir
so well explained!!!!!
Hi Striver and Everyone in the Comment Section !
I attempted the problem with this same method but in the function after finding l1,l2,r1 and r2. I added below given conditions
if(l1==INT_MIN) // If not selecting any element from the first array, then return answer from the second array
return arr2[k-1];
if(l2==INT_MIN) // Similarly, if we are not selecting any element from the second array we return the answer from 1st array
return arr1[k-1];
if(r1==INT_MAX || r2==INT_MAX) // If one of the array is completely considered in the answer we have reached the solution thus return max(l1,l2)
return max(l1,l2);
But due to some reason, the code is missing on one of the TC on GFG.
Can anyone please explain to me where I am getting wrong. Thanks in Advance.
code given in TUF website is little wrong, the
the line int low = max(0,k-m), high = min(k,n); given in website has m,n interchanged
just do it int low = max(0,k-n), high = min(k,m);
and remove all of your edge caes and it will work like charm
Thank me later
@@PhoenixRisingFromAshes471 I tried that but still get error on
7 11 15
1 10 10 25 40 54 79
15 24 27 32 33 39 48 68 82 88 90
this
@@indrajitdas9553, Can you share your complete code here, so that I can figure out where the problem lies if possible from my side?
@Monil Charola, the conditions which you have introduced are wrong and that is why it is giving the wrong answer. Let us take an example test case:-
arr1-> [6]
arr2-> [1,2,3,4,5,7,8,9,10,11]
k=8
Your code will give the asnwer=arr2[7] which is 9 but the correct answer is 8. The reason which I can deduce from your conditions is that:
-> If we are not selecting any element from the first or second array, then you are neglecting that whole array and only considering the other array but that is not the case.
Even if we are not selecting any element from an array, then also that array will contribute to our answer in the above case "6" from the first array will come at the 6th position of our final sorted array but as per your condition you will return arr2[k-1] which will be our 7th element of the second array and not the final sorted array because you have neglected the whole "arr1".
This is the reason your code is giving the wrong answer. Hope you understood, if you find any difficulty understanding the reason, you can ask me again🙌.
Thank you Stryver
Great explanation. Thank You!
thanks for this authentic explaination .
20:36 Leonardo DiCaprio -> holding bear -> pointing on screen.
Great explanation great mind
Edge cases: 21:41
Understood! Super wonderful explanation as always, thank you very much!!
How can k be max(l1,l2) what if he gives k=9 for n1+n2=11
Thank you bhaiya for the amazing ,totally understood the concept :D
Did you miss a case where K equals number of elements in both the arrays combined?
arr1 = {12, 14}
arr2 = {1,2,3,4,5}
k = 7
Nah, it works on all, you can try with code in description.
understood. very well explained
++CFBR. Great work bhai !
just excellent explanation
Love the amazing content...Do keep it up! It's helping us out in ways you couldn't imagine!!
Thank you! Will do!
Superb Solution !!
Hi, I was running the below test case
arr1 = {1, 5,9}
arr2 = {4,7,11,18,19}
k = 7
The code fails for this test case. Answer should be 18.
Upon trying to understand I think the below logic is causing the test case to fail.
int low = max(0,k-m), high = min(k,n);
Can anyone explain if I am doing something wrong here ?
I had the similar question. My test case was failing at a similar test case.
use this code
public long kthElement( int arr1[], int arr2[], int n, int m, int k) {
if(arr2.length
@@vaishali1843 Can anyone of you share the complete code so that I can figure out exactly where the problem lies?
great video, i finally understand it!
Best explanation!!
great explanation as always !!!
Hello Striver! I'm Smeet. This code will fail in test cases where k - m > m. Why? Because the low will be initialized greater than high, resulting in skiping the execution of while loop.
Hence, the correct initialization should be :
int low = max(0 , min(k - m , m));
This will take care of the test cases.
And Thank you so much for this valuable content.
@satvikshrivastava5840 You might be having some bugs, Kindly refer to this code :
#include
using namespace std;
int ninjaAndLadoos(vector &row1, vector &row2, int m, int n, int k) {
if(m > n){
return ninjaAndLadoos(row2 , row1 , n , m , k);
}
int low = max(0 , min(k - m , m));
int high = min(m , k);
int cut1;
while(low
if somebody's solution is failing for some test cases on gfg use this code
intuition is same
public long kthElement( int arr1[], int arr2[], int n, int m, int k) {
if(arr2.length
int mid2 = k - mid1;
how can we be sure k > mid1 ??
@@yadneshkhode3091 From the conditions, we can conclude that "low" cannot be "less than 0" and "high" cannot be "greater than k". So, our cur1 will be at max "k/2" in the starting and as we move further, we are updating our low and high to "cur1+1" and "cur1-1" which implies our low and high will always lie "between 0 and k". Since cur1 is calculated as (low+high)/2, we can say it will never become "greater than k". Hope you understood🙌.
Understood bro!
Understood completely 👍
wonderful explanation! thanks
It is not working when k=10 for your two arrays. Actually here mid value is greater than size of smaller array. That gives run time error so to avoid that we will work on larger array rather than working on smaller array
Hare Krishna! understood
very well explained !!
Understood💯💯
can someone explain the reason of taking low = max(0, k-m) and high = min(n, k)??
Understood. Great video🔥🔥
Understood 💯💯💯
great approach
i have understood the code.
but there is one thing: this code gives wrong ans when submitted for all test cases on gfg.
Also i dont know why but it also gives TLE in some cases.
I thought may be i would have done something wrong but then i went to the take youforward site and pasted the code for this question from there but it passes only 1 test case.
pllzz relply if someone has the solution............
same for java
class Solution {
public long kthElement( int arr1[], int arr2[], int n, int m, int k) {
if(n>m){
return kthElement(arr2,arr1,m,n,k);
}
int low=Math.max(0,k-m), high=Math.min(k,n);
while(low>1;
int cut2=k-cut1;
int l1=cut1==0?Integer.MIN_VALUE:arr1[cut1-1];
int l2=cut1==0?Integer.MIN_VALUE:arr1[cut1-1];
int r1=cut1==n?Integer.MAX_VALUE:arr1[cut1];
int r2=cut1==m?Integer.MAX_VALUE:arr1[cut1];
if(l1
Greatly helpful
Just wow!
Is it okay to go for a optimise solution for any question even if you're not sure about it's brute force approach? I mean is it necessary to know?
And the other thing I'm stuck with is implementing the approach/solution into code. Also, whenever I read a question I know what to implement at this condition but I cannot write the solution in order or you can say in structurzied manner
if you will not say the brute force , the problem will be finished soon and interviewer will be ready with another extra problem for you ,so time management with brute force is a important step
@@mickyman753 lol your way of approaching the situation is quite intresting... anyway, thanks I'll keep that in mind
Love the explanation ❤️
Thanks my friend really help !!!
U r doing a great job .but my bad 😔.I dint understand
Thanks bro!
understood, Thankyou
DOUBT!!!!
Isnt the binary search done on the smaller array so that not more than needed elements are taken (in the median problem half the total elements, and here k elements) but if we make sure the high is not more than k, it shouldnt matter what array we do binary search on, right? i tried accordingly, and my solution got accepted(GFG). Is there any other reason why binary search must be done on the smaller array? please reply if know the answer or maybe atleast have the same doubt guys..
Understood 👌
Hi! How do we solve for 4th element of m sorted arrays>?
c++ code:
class Solution{
public:
int kthElement(int arr1[], int arr2[], int n, int m, int k)
{
int p1 = 0, p2 = 0, i = 0, r = 0;
while (i < k) {
if (p1 >= n) {
return arr2[p2 + k - i - 1];
}
if (p2 >= m) {
return arr1[p1 + k - i - 1];
}
if (arr1[p1] < arr2[p2]) {
r = arr1[p1];
p1++;
} else {
r = arr2[p2];
p2++;
}
i++;
}
return r;
}
};
Thanks a lot!
Thanks
I haven't understood the point made at 23:00. How is the low 1?
Why it's not working for some cases if we set high=n only?
Really Amazing
Good bro,continue this
Bruh how do I know that the last element in the left half is k?
Understood♥️♥️♥️💯💯💯
damn ! this is dope !
Why we call function on smaller array ?
if (counter != k) {
if (p1 != m - 1)
answer = array1[k - counter];
else
answer = array2[k - counter];
}
can anyone please explain this block for naive sol.?
Can anyone pl explain me how we have chosen low and high initially? Like low,high = max(0,k-m),min(k,n)
Go to 21:42 for the expalination of this edge case
how do we determine that our last element will always be kth element
Thanks man
can't understand the logic behind k-m 25:10
Understood ❤️