Bs-22. K-th element of two sorted arrays

Bs-22. K-th element of two sorted arrays | Binary Search Approach

Рет қаралды 87,717

Күн бұрын

Пікірлер: 107

@sujalgupta6100 6 ай бұрын

It was all good until the gas stations problem arrived. From that problem, there is always something weird logic everytime in hard problems. I feel a rewatch is required.

@codewithcode2864 5 ай бұрын

very true brother the whole confidence goes off

@Satyendra_Prakash17 4 ай бұрын

glad someone said

@soumiyamuthuraj3516 4 ай бұрын

Soo true

@priyanshshukla450 4 ай бұрын

Facts, everything was going good till that gas station problem 😭

@RAHUL-gl3ye 4 ай бұрын

But the gas station problem requires premium on leetcode right? 👀

@Dontpushyour_luck Жыл бұрын

did it by my own after learning median of two sorted arrays concept from you! thank you

@atharvakj 5 ай бұрын

which one ?

@MR._NEEN 10 ай бұрын

I AM IMPROVING MYSELF IN PROBLEM SOLVING DAY BY DAY BECAUSE OF YOU. I AM SLAVE TO YOUR PLAYLIST

@bruvhellnah 28 күн бұрын

what the actual f lmao

@FusionArcs 10 ай бұрын

finally, the mystery of why low and high needs to be corrected for this solution? Let's take an example, m = 3, n = 10, k = 12 If we keep low = 0, and high = 3 then mid1 = 1; low = 0 means we don't pick any element from the first array, and now the remaining elements need to be picked from the second array. mid2 = (k - mid1) = 12 - 1 = 11 ???? but there are only 10 elements in the second array Hence we can't start our search when we pick no elements from the first array. So our low must be max(k - n, 0) [no of elements at least need to pick for 1st array] Similarly, for high, we have to reduce the search space such that it can handle low K values. Note: this issue doesn't occur in the median problem because we guaranteed to split the search space in half every time.

@aryansoni8819 6 ай бұрын

bro when mid1=1 then you pick one element from first array correction rest are correct

@JIGARSINGTHAKOR-yy6qp 4 ай бұрын

can you furthur explain why it does not happens in median.?

@anandpandey918 4 ай бұрын

//Bruteforce Approach class Solution { public long kthElement(int arr1[], int arr2[], int m, int n, int k) { int[] merged = mergeTwoSortedArrayIntoThirdSortedArray(arr1, m, arr2, n); return merged[k - 1]; } private int[] mergeTwoSortedArrayIntoThirdSortedArray(int[] arr1, int m, int[] arr2, int n) { int[] merged = new int[m + n]; int i = 0, j = 0, k = 0; while (i < m && j < n) { if (arr1[i]

@vamsikrishnagannamaneni912 14 күн бұрын

In median it will work because we never ask to pick more than the largest array have, because of the formula (n1+n2+1)//2

@sayantanmanna1360 11 ай бұрын

Hey @takeUforward , there's a small mistake in the optimal solution posted on the website. It says `int low = max(0,k-m), high = min(k,n) ; ` where `m` and `n` are the length of the first and second array respectively. According to this lecture, it should be `int low = max(0,k-n), high = min(k,m) ; `

@parthrastogi572 Жыл бұрын

Just search for this question's solution and here comes the video just 4 hours ago!! Thanks for your help!

@cinime Жыл бұрын

Understood! Super fantastic explanation as always, thank you very very much for your effort!!

@stith_pragya 6 ай бұрын

UNDERSTOOD......Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

@lokeshnegi5051 3 ай бұрын

I think some questions are made to skip and this is also one of those inlcuding medain of sorted arrays

@ArpanChakraborty-do6yz 9 ай бұрын

Awesome 😎👍🏻 11:41

@sidharthsharma341 Жыл бұрын

Bhaiya which topic will come next ?.....what are upcoming plans

@guttulavybhav1030 4 ай бұрын

bro there is a correction if for suppose m=5 and n=6 and k=7 then if we take up all the 6 elements from arr2 then we need atleast one element to be taken from arr1. so low should be 1. so formula will be max(0,k-n) i.e 7-6=1 so low should be 1 in order to select k elements from left.

@urstrulyjatin 27 күн бұрын

Thanks stiver, love you. See you at google soon.

@saikumargatla4706 Жыл бұрын

To be precise low=max(0, k-sizeoflargerarray)

@allaboinadivakar1976 Жыл бұрын

we always consider n2 as larger array bro

@mehedihasansabbir7886 Жыл бұрын

Great explanation

@devarapallivamsi7064 9 ай бұрын

My code that's a bit different from what is explained in the video: Please do a dry run. you will get it. (Python) def kThElement(arr1, arr2, k): n1 = len(arr1) n2 = len(arr2) if n1 > n2: return kThElement(arr2,arr1,k) low = 0 high = n1 while low k: high = mid1 - 1 continue if mid2 > n2: low = mid1 + 1 continue l1 = float('-inf') r1 = float('inf') l2 = float('-inf') r2 = float('inf') if mid1 >= 1: l1 = arr1[mid1 - 1] if mid1 < n1: r1 = arr1[mid1] if mid2 >= 1: l2 = arr2[(k - mid1) - 1] if mid2 < n2: r2 = arr2[(k - mid1)] if l1

@lohithreddym4 5 ай бұрын

it's the same

@anshsaxena7297 2 ай бұрын

UnderStood

@shubha_jagadeesh 13 күн бұрын

understood😍

@Learnprogramming-q7f 9 ай бұрын

Thank you Bhaiya

@BOSS55 Жыл бұрын

thansks

@Ungan_Tamilan Жыл бұрын

Forever strivers

@oyeesharme 3 ай бұрын

understood bhaiya

@NazeerBashaShaik 7 ай бұрын

Understood, thank you.

@vivekverma4012 Жыл бұрын

But sir, ultimately low will reach max(k-n2,0) and high will reach min(k,n1) during the execution of while loop and will reach the desired answer. Then why not leave low=0 and high=n1 as it is?? May be it takes somewhat more time but as u say it's giving wrong output.

@samirkeshwani9409 Жыл бұрын

if you pick n1 elements from a1 array (suppoes n1>k)then atlast when you find suitable configuration then in ans max(l1,l2) gives wrong answer as you picked an element which is after k so i think this might be the reson for high to be restritcted i am not sure though

@FusionArcs 10 ай бұрын

Let's take an example, m = 3, n = 10, k = 12 If we keep low = 0, and high = 3 then mid1 = 1; low = 0 means we don't pick any element from the first array, and now the remaining elements need to be picked from the second array. mid2 = (k - mid1) = 12 - 1 = 11 ???? but there are only 10 elements in the second array Hence we can't start our search when we pick no elements from the first array. So our low must be max(k - n, 0) [no of elements at least need to pick for 1st array] Similarly, for high, we have to reduce the search space such that it can handle low K values. Note: this issue doesn't occur in the median problem because we guaranteed to split the search space in half every time.

@vivekverma4012 10 ай бұрын

@@FusionArcs understood, thanks😀

@anandpandey918 4 ай бұрын

@AishwaryDandale 5 ай бұрын

read solution in the sheet for clear explanation.

@SYCOA12CHAITANYAASOLE 5 ай бұрын

Understood !! 😍😍

@devarapallivamsi7064 9 ай бұрын

Understood!

@YourCodeVerse 11 ай бұрын

Understood✅🔥🔥

@per.seus._ Жыл бұрын

UNDERSTOOD

@taneyasoni Жыл бұрын

please post the link to the prerequisite video.

@prikshit_sharma4071 Жыл бұрын

Thank you 😊❤

@arihantjammar8888 Жыл бұрын

understood

@arpitbhavsar6020 Жыл бұрын

Understood

@dogwoofwoof8154 10 ай бұрын

easy 120 points :)

@tusharsingh1257 6 ай бұрын

Completed 29th May 2024

@girikgarg8 Жыл бұрын

Done

@sambhavraghav7360 28 күн бұрын

why these low and high conditions were not in median problem?

@redBaron_80 Ай бұрын

why was the low and high check was not needed in the median problem?

@allaboinadivakar1976 Жыл бұрын

❤

@surbhirathore._ 5 ай бұрын

Where are the notes?

@joelpires1342 6 ай бұрын

Why marked as done, if it didn't work?

@DhananjayKumar-bd2jg 10 ай бұрын

8:25

@pratyakshhhhhhhhhhhhhhhhhhhhh Жыл бұрын

🎉🎉❤

@amitranjan6998 Жыл бұрын

@Striver Bhaiya, For K=7 , why we can't peak from arr1 all the 6 element and 1 from array2 . Just confuse with low , why it's max(k-n2,0). If any one also help, will great for me.

@vivekverma4012 Жыл бұрын

since, low=max(k-n2,0) so it indicates we have to select atleast these many elements from arr1.

@amitranjan6998 Жыл бұрын

@@vivekverma4012 that I got it, my question why not to pick from arr1 first rather taking from arr2 first

@tapansonak1431 Жыл бұрын

Watch the previous video, median of two sorted arrays, in that video he explained that we always pick elements from the smaller array, as it will reduce the time complexity. In the given example arr1[] has 6 elements and arr2[] has 5, so picked elements from arr2[].

@FusionArcs 10 ай бұрын

@anandpandey918 4 ай бұрын

@kunal5077 5 ай бұрын

showing TLE on code 360 please tell how to evaluate.

@shashwattopre9672 Жыл бұрын

Why high=max(k,n1)? I am unable to understand.

@nihalsingh6233 Жыл бұрын

High = min(N1, k ) It is because if we want just 2 elements in left hand side and N1 is 5 then why we need increase our search space upto 5, just simply shrink it to 2. Because we will be need only 2 elements in left hand side. Hope it helps !!!

@anandpandey918 4 ай бұрын

@ekanshgupta2930 Жыл бұрын

can anyone tell why does this code not pass on gfg I have been trying to do it for 2hrs now and am unable to find the error

@GeorgianHarshAnand 10 ай бұрын

if(n > m) return this.kthElement(B , A , m , n , k) let i = Math.max( 0 , k-m) , j = Math.min(k , n) while(i = 0) l1 = A[mid1-1] if( mid2 < m) r2 = B[mid2] if(mid2 - 1 >= 0 ) l2 = B[mid2 - 1] if(l1

@jewelchakraborty9717 8 ай бұрын

class Solution { public long kthElement( int a1[], int a2[], int n1, int n2, int k) { if(n1 > n2) return kthElement(a2, a1, n2, n1, k); int low = Math.max(0, k - n2); int high = Math.min(k, n1); while(low 0) l1 = a1[mid1 - 1]; if(mid2 > 0) l2 = a2[mid2 - 1]; if(l2 > r1) low = mid1 + 1; else if(l1