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

[@sujalgupta6100]

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]

very true brother the whole confidence goes off

[@Satyendra_Prakash17]

glad someone said

[@soumiyamuthuraj3516]

Soo true

[@priyanshshukla450]

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

[@RAHUL-gl3ye]

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]

which one ?

[@MR._NEEN]

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

[@bruvhellnah]

what the actual f lmao

[@FusionArcs]

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]

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

[@JIGARSINGTHAKOR-yy6qp]

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

[@anandpandey918]

//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]

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

[@parthrastogi572]

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

[@nandhinik04]

For those who didn't understand consider the example: n1=4, n2=6, k=8 if we assume low=0 and high=n1 it means there is a possibility of taking 0 elements from n1 arr and remaining elements from n2 arr (which has only 6 elements but we need 8 elements at left so its mandatory to consider atleast 2 elements from left arr) so low = max(0, k-n2) and for high consider the scenario n1=4, n2=6, k=2 where need to have only 2 elements at left so should consider atmost 2 elements from n1 arr so high = min(k, n1)

[@aamir4684]

brother you are from which year?

[@nandhinik04]

@aamir4684 why are u asking for?

[@sayantanmanna1360]

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) ; `

[@cinime]

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

[@sumitbhardwaz]

Amazing. I came up picking high as K but picking up low as max of k - n2, 0 is amazing. Well I thought I needed a whole lot more of dry run.. that's shows we need to do dry run on every value we pick. In every scenario only when we would able to come up on such thing

[@ArpanChakraborty-do6yz]

Awesome 😎👍🏻 11:41

[@stith_pragya]

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

[@sidharthsharma341]

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

[@guttulavybhav1030]

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.

[@lokeshnegi5051]

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

[@redBaron_80]

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

[@Pw_Unfiltered]

start 05:01

[@taneyasoni]

please post the link to the prerequisite video.

[@soumy_jain]

Let n1 and n2 be the sizes of the smaller and bigger arrays, respectively, and let count1 be the number of elements taken from the smaller array, with count2 being the number of elements taken from the bigger array. In the median problem, the condition count2 = k - count1 will never result in a negative value because k = (n1 + n2) / 2. Since count1 is taken from the smaller array, it can be at most (n1 + n2) / 2. Therefore, count2 = k - count1 (where count1

[@SiddhiLandage]

hello for low we take min( 0 , k -n1 ) where n1 is the smaller array size i.e in above example which you have given { array1 size is 6 and array 2 size = 5 } you said low = 2 means we will defintely take 2 elments from array which has size 6 but we apply binary search on the smaller array so it means that we must take 2 elments from the smaller array is it right?

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

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]

@@FusionArcs understood, thanks😀

[@anandpandey918]

//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]

[@akilsabir1088]

what's the use of int n in BS approach.

[@urstrulyjatin]

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

[@SYCOA12CHAITANYAASOLE]

Understood !! 😍😍

[@YourCodeVerse]

Understood✅🔥🔥

[@mehedihasansabbir7886]

Great explanation

[@joelpires1342]

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

[@NazeerBashaShaik]

Understood, thank you.

[@sambhavraghav7360]

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

[@kurma.4932]

In the median problem, when we merge two sorted arrays, we are splitting the elements of the array into two halves Now, if we split the merged array in half, the left half will always contain n/2 elements, right? For example, suppose there are 10 elements in total, and n/2 equals 5. So, the left half would have 5 elements. Now, the purpose of the low and high pointers is to help you figure out how many elements you can take from each array. If high is n1 (where n1 is the size of the first array), it means the maximum number of elements you can take from the first array is n1-which simply means you can take all the elements from the first array. Since n/2 is 5 elements (last video), it means the two halves of the merged array should have an equal number of elements ( 5 elements each). Now we have a left variable( n / 2) as well, which goes as mid2 = left - mid1, so = left basically makes sure that if 2 elements are taken from arr1, remaining 3 will be taken from arr2 So left simply handles everything Now, let's discuss why we check low and high here: In the case of finding the median, the left side is not necessarily the exact middle of the total number of elements (n1 + n2), because of the introduction of k. as here left = k, This means that the left side won't always have an equal number of elements from both arrays. There are cases where we must take at least one or two elements from the first array. So, starting with low = 0 may not always work.(suppose we must need minimum 1 element from one array but low 0 fails here) Similarly, if we take high = n1 (for instance, if n1 = 5) but we only need 2 elements because k = 2, there’s no point in taking all n1 elements from the first array. This is why adjusting low and high is necessary.

[@Slayer-070]

read solution in the sheet for clear explanation.

[@kunal5077]

showing TLE on code 360 please tell how to evaluate.

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

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.

[@anandpandey918]

//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]

[@devarapallivamsi7064]

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]

it's the same

[@surbhirathore._]

Where are the notes?

[@Ungan_Tamilan]

Forever strivers

[@shamanthhegde2820]

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: n1 = len(nums1) n2 = len(nums2) if(n2 < n1): return self.findMedianSortedArrays(nums2, nums1) n = n1 + n2 if(n%2 != 0): isEven = False left = (n)//2 + n%2 low = 0 high = n1 l1 = -1 l2 = -1 r1 = -1 r2 = -1 while(low

[@saikumargatla4706]

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

[@allaboinadivakar1976]

we always consider n2 as larger array bro

[@prikshit_sharma4071]

Thank you 😊❤

[@shubha_jagadeesh]

understood😍

[@devarapallivamsi7064]

Understood!

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

//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]

[@per.seus._]

UNDERSTOOD

[@anshsaxena7297]

UnderStood

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

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]

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

[@Learnprogramming-q7f]

Thank you Bhaiya

[@BOSS55]

thansks

[@oyeshxrme]

understood bhaiya

[@DhananjayKumar-bd2jg]

8:25

[@dogwoofwoof8154]

easy 120 points :)

[@arpitbhavsar6020]

Understood

[@tusharsingh1257]

Completed 29th May 2024

[@arihantjammar8888]

understood

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

🎉🎉❤

[@allaboinadivakar1976]

❤

[@girikgarg8]

Done

[@apoorva5961]

😇

[@raghavsapra2792]

3rd comment love u striver...

[@cenacr007]

us

[@codderrrr606]

kachwa bhai har jagah aa jata h

[@codderrrr606]

striver bhai kachwa bhai ko rok lo

[@dewanandkumar8589]

Understood!

[@nihalsingh6233]

Understood

[@KAMLESHSINGH-vr3bl]

understood

[@shruti-m4e]

us

[@rajatshukla2605]

Understood!

[@PrinceTripathi-j7u]

Understood

[@culeforever5408]

understood

[@rakeshbasak6842]

Understood!

[@salendraraviteja8472]

Understood

[@abhinanda7049]

understood

[@NARUTOUZUMAKI-bk4nx]

Understood

[@udatyadeb101]

understood

[@LearnerForever123]

Understood

[@chiragbansod8252]

understood

[@aryankumar3018]

Understood

[@Rohan_K_Das_22BCE164]

Brother can you explain why the changes for low and high stuffs were used here and not in the median qn, am a bit confused in that ...

[@hardikpatel352]

understood

[@krishkumar491]

Understood

[@ashishpradhan6250]

understood

[@SitaRam-m1i]

Understood

[@Harsh-jc2bz]

understood

[@KrishMewari-y3k]

Understood

[@anmolsaini2783]

understood

[@himasreedadam7670]

understood

[@divyakumardivyanshu4279]

understood