O(log(min(n,m))) approach | Bs-22. K-th element of two sorted arrays | Binary Search Approach

[@takeUforward]

Please watch our new video on the same topic: kzbin.info/www/bejne/emLSdaqNeNZoZsk

[@sonalidutta825]

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

[@kingmaker9082]

Thanks for saving time 🙏🏻

[@shubhampatel_2745]

Really Thank you from bottom of my heart.

[@crictYaari]

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

[@anuradha7861]

Thanks dear for explaining this 🙏

[@vijaykaran3848]

Thank you very much

[@jaineelmamtora6760]

There can't be any more simplified explanation video on KZbin other than this! Thank you for making this video!

[@rishabhkumar8115]

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.

[@lokeshdulani6035]

I was seriously struggling to understand this from GFG's editorial thanks for this.

[@gauravshukla5203]

how do we determine that our last element will always be kth element?

[@princemakadiya9443]

@@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

[@devprakash5320]

settting the right range of low and high initially is one of the most important steps

[@devprakash5320]

forgot to write 'Understood" 😊😊😊

[@yushdecides]

I didn't understand that part, can you plz explain it to me?

[@exodus5948]

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.

[@yushdecides]

@@exodus5948 Are or unki values vo kyu li..ye puchra tha

[@exodus5948]

@@yushdecides Sorry I misunderstood

[@willturner3440]

Before your explanation I made my logic..bcoz this was same as previous. Thanks for such a great explanation ..

[@Rajat_maurya]

were you able to write the code of edge case?

[@inclinedscorpio]

@@Rajat_maurya obviously it's clear once test case starts breaking.

[@ankitranjan88]

Did it by Own from using Concept of (Median of two sorted ) ... Thanxx Bhaiya for this Explanation

[@Sakshi-yq4jm]

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.

[@lavishgarg5090]

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

[@superheroherohero]

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.

[@MOHDSALMAN-sj2zu]

Yes, you are correct. It is O(log(min(n, m, k))).

[@_-6912]

After median of sorted arrays this was really easy to understand!

[@sauravchandra10]

Other than the edge cases, I was able to code this one on my own. Most optimised approach, maza agya

[@kaichang8186]

understood, thanks for the perfect explanation

[@nagame859]

Understood 👍 The way you explained edge cases exemplifies your proficiency. Great work as always..

[@VenuGopal-hg1hm]

You already explaining all the things in crystal clear manner so why people waste money and join other courses

[@geck1204]

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

[@geck1204]

Great explanation btw!

[@ayeshaqaisar1651]

@@geck1204 Hey, Which company's interview was this asked in?

[@geck1204]

@@ayeshaqaisar1651 Cruise

[@ayeshaqaisar1651]

@@geck1204 Thanks

[@akshatsrivastava9015]

Clearly explained all the boundary cases. Keep up the good work!

[@ranaaditya7960]

Usually (never) I don't comment on any YT videos but this time I want to say THANK YOU STRIVER 🥺

[@Sakshi01188]

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

[@jacksparrow1316]

Thank you sir for giving your precious time from your busy schedule....♥️♥️

[@takeUforward]

It's my pleasure

[@yourGuy675]

i think we can do these when validating the array. max(l1,l2) < min(r1,r2) then it is our desired array

[@ITKOUSIKV]

You are gem of ther person for students

[@INC627]

How can k be max(l1,l2) what if he gives k=9 for n1+n2=11

[@rahulpothula1902]

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

[@GauravJain-zo8gt]

jai jinendra sir

[@monilcharola6873]

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.

[@PhoenixRisingFromAshes471]

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

[@indrajitdas9553]

@@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

[@Steve-kv5we]

@@indrajitdas9553, Can you share your complete code here, so that I can figure out where the problem lies if possible from my side?

[@Steve-kv5we]

@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🙌.

[@PremKumar-rd1uv]

Thanks for the clear explanation brother. Understood well. Daily I'm waiting for ur videos.

[@suryanshm000]

I appreciate your observation of second edge case 👌👌 clearly explained !!

[@cse-b-132ashishupadhyaya5]

23:10 commenting to remember edge case.... bdw nice work bro

[@abhijeetpatnaik5494]

Can't thank enough for this beautiful solution

[@tanishqmehta8272]

can't be a more noble deed than to clear a student's concepts❤❤

[@LegitGamer2345]

thanks a lot i have been stuck on this for way too long

[@vaishnavi9755]

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 ?

[@vaishali1843]

I had the similar question. My test case was failing at a similar test case.

[@amitchaudhary7745]

use this code public long kthElement( int arr1[], int arr2[], int n, int m, int k) { if(arr2.length

[@Steve-kv5we]

@@vaishali1843 Can anyone of you share the complete code so that I can figure out exactly where the problem lies?

[@shivam9201]

can someone explain the reason of taking low = max(0, k-m) and high = min(n, k)??

[@varunsharma8350]

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

[@takeUforward]

Nah, it works on all, you can try with code in description.

[@jayadubey_22]

Great explanation understood very well this complex binary search problem😅 thank you very much bhaiyaa

[@arijit9862]

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.

[@arijit9862]

​@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

[@hemantranjan2297]

20:36 Leonardo DiCaprio -> holding bear -> pointing on screen.

[@팜팜팜-g6p]

I finally understood!!!! Thanks a lot!!💛

[@ritikjalal117]

great explanation bhaiya understood

[@biswajitmahalik9979]

so well explained!!!!!

[@samarthjain5295]

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

[@sujayshanbhag2055]

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..

[@aasifali9139]

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............

[@Sakshi01188]

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

[@youngshahrukhkhan8179]

Understood....Awesome Explanation......Especially handling edge cases was so fun

[@ayushkaushik9637]

Great explanation great mind

[@amitchaudhary7745]

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]

int mid2 = k - mid1; how can we be sure k > mid1 ??

[@Steve-kv5we]

@@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🙌.

[@anushkamishra6411]

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

[@mickyman753]

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

[@anushkamishra6411]

@@mickyman753 lol your way of approaching the situation is quite intresting... anyway, thanks I'll keep that in mind

[@debaratighatak2211]

Thank you bhaiya for the amazing ,totally understood the concept :D

[@balajiarumugam1876]

++CFBR. Great work bhai !

[@arfat2597]

Great explanation. Thank You!

[@SuperWhatusername]

Thank you Stryver

[@ashwinshetgaonkar6329]

thanks for this authentic explaination .

[@sahajpareek6352]

Bruh how do I know that the last element in the left half is k?

[@koelsinha3800]

Hi! How do we solve for 4th element of m sorted arrays>?

[@iamsks7]

understood. very well explained

[@gauravbhardwaj380]

Can anyone pl explain me how we have chosen low and high initially? Like low,high = max(0,k-m),min(k,n)

[@meghadandapat213]

Go to 21:42 for the expalination of this edge case

[@sherryfan161]

great video, i finally understand it!

[@arnabpersonal6729]

just excellent explanation

[@cinime]

Understood! Super wonderful explanation as always, thank you very much!!

[@littlecuties3384]

U r doing a great job .but my bad 😔.I dint understand

[@manavmalhotra8513]

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.?

[@mukuldaftary9230]

Superb Solution !!

[@385_ayushagarwal8]

great explanation as always !!!

[@gauravshukla5203]

how do we determine that our last element will always be kth element

[@vrushin1053]

wonderful explanation! thanks

[@resetengineering]

I haven't understood the point made at 23:00. How is the low 1?

[@amitpurohit8816]

Best explanation!!

[@rohitbajaj7733]

Why it's not working for some cases if we set high=n only?

[@himanshubarak4944]

very well explained !!

[@growwithriu]

Edge cases: 21:41

[@quanta8382]

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

[@kunalpatidar2849]

Understood completely 👍

[@Steve-kv5we]

Understood💯💯

[@vasujain1970]

Love the amazing content...Do keep it up! It's helping us out in ways you couldn't imagine!!

[@takeUforward]

Thank you! Will do!

[@sreeharia2356]

Can somebody explain why low = max(0,k-m) ?

[@preethikadambala2595]

in the video he has said 2 edge cases, watch it, for that edge cases to be handled, minimum elements from array1 cannot be zero if array2 does not have k elements . So, low cannot be always zero

[@akshaybhadange2492]

Thanks my friend really help !!!

[@ishanmay8]

great approach

[@geekySRM]

Understood bro!

[@lakshmiprasanna7058]

Understood 💯💯💯

[@niketgupta3884]

hii striver @take U forward i think maybe your end cases will fail in that condition if arr1=[1,2,3,4,5] and arr2=[6,7,8,9]... plzz check this

[@niketgupta3884]

@takeUforward your condition low=max(0,k-m) high=min(k,n)

[@rohitraina5059]

Understood. Great video🔥🔥

[@rkalyankumar]

Just wow!

[@SatyamKumar-bw4vi]

Hare Krishna! understood

[@AkashKumar-lr6hc]

Why we call function on smaller array ?

[@DIVYANSHMISHRA08]

hello sir, in SDE sheet there are no questions like book allocation problem, painters partition which are solved using binary search in answers. Are they not asked much in interviews? (sorry if you have already answered this question somewhere and I missed that)

[@takeUforward]

I have covered tougher problems on the same topics, so that when these problems are asked, it becomes easier. However the painter’s partition is a good one, will add it.

[@mukulrana1616]

Greatly helpful

[@jsuryakt]

Love the explanation ❤️

[@hit1599]

Thanks bro!

[@sakshamsrivastava6280]

understood, Thankyou

[@AmitKumar-je9qo]

Bhaiya aptitude bhi padhna hoga kya ya sheet me jitna hai utna se ho jayega??

[@mrb7931]

too tough, I am afraid i could crack interview or not

[@maruthiteja2586]

Understood 👌

[@aritraganguly3957]

can't understand the logic behind k-m 25:10

[@azraazra8273]

Good bro,continue this

[@nuamaaniqbal6373]

Thanks a lot!

[@decostarkumar2562]

I am getting ArrayIndexOutOfBoundException 😞🤔 Can anyone help 😭

[@TSMJonathan-po3hj]

broo please change java code on your Website .the solution in u r site was wrong please update

[@shrirangdeshmukh8525]

Really Amazing