Median of Two sorted arrays | O(log(max(m,n))) Time complexity |
Vložit
- čas přidán 28. 10. 2020
- This is the video under the series of DATA STRUCTURE & ALGORITHM. We are going to solve Questions from GeeksforGeeks or leetcode Median of Two sorted arrays in O(log(max(m,n))) Time complexity and O(1) Space Complexity.
Given two sorted arrays arr[] and brr[] of sizes N and M respectively. The task is to find the median of the two arrays when they get merged.
Which is a very famous and Routine question asked in Interview. The question is from the Topics Data structure. A full easy concept in Hindi. This is Question is asked in Many companies like Google, Amazon, Oyo Rooms, Paytm, Samsung, Adobe, etc..
We also Provide courses on Competitive Programming and Data structure. Please see our Full Playlist on our Channel.
----------------------------------------------------------------------------------------
► Homework Question: leetcode.com/problems/median-...
----------------------------------------------------------------------------------------
► Median of Two sorted arrays: leetcode.com/problems/median-...
► PDF of Median of Two sorted arrays: github.com/Prince-1501/Hello_...
► CODE of Median of Two sorted arrays: github.com/Prince-1501/Hello_...
----------------------------------------------------------------------------------------
*Follow me *
LinkedIn► / iamprince
Facebook► / helloworldofficials
Instagram► / helloworldbyprince
Twitter► / prince_king_
----------------------------------------------------------------------------------------
►Our Playlists on:-
►Competitive Programming : • How to start Competiti...
►C++ Full Course : • L-01 || Introduction a...
►Algorithms : • L-01 || Prefix Sum Arr...
►Data Structure: • Data Structures with C...
------------------------------------------------------------------------
Our Students Contacts Form:-
Form link: docs.google.com/forms/d/e/1FA...
------------------------------------------------------------------------
#interview_preparation #geeksforgeeks #Hindi
Since morning I was trying very hard to understand this problem . Finally I got it. Thanks a lot
Keep sharing buddy
same
Why we take end1 = n1 and not n1 - 1 because we are taking begin1 = 0 as from 0 to n1 there are n + 1 element and in all searching problem we take low as 0 and high as n - 1?
Pls make a video playlist of dsa 450 questions by love Babbar.
You have literally put your everything in the video. Great Content.
Keep sharing with your friends ❤️
@@HelloWorldbyprince Why we take end1 = n1 and not n1 - 1 because we are taking begin1 = 0 as from 0 to n1 there are n + 1 element and in all searching problem we take low as 0 and high as n - 1?
Very good explanation. I would say the best explanation for solving "median of two sorted array" in CZcams. But I tried running the java version of this in leetcode and its showing "99.69 % faster than other Java submission".
You explained just like a friend . Thanks
thanks sir! Really insightful
This is the best explanation I have seen so far Thanks a lot
excellent stuff. best video on this problem. I wanted to understand the intuition behind : i2 = (n + m + 1)/ 2 - i1. Why can't we just do i2 = (m-1) - i1, where m-1 is the index of the last element of the array2? This is assuming i1 = begin1 + (end1 -begin1)/2. At the start, end1 points to the last index of array 1 (n -1 ).
Bhai best of alll the videos i have seen in this question i saw ...
Is video ke liye bahut bahut aabhar! Maza aa gaya jis prakar se aap bilkul zero level se batana shuru karte ho. Thanks a lot.
Thanks a lot your love 💗
This video is the best one I found to solve this question. Keep up the good work.Thankyou!!
Keep sharing my channel with your friends ❤️
Thank You bhaiya....
Bahut badiya samjaya ek aur dekhna padega....
man thanks for this video... you really made it look simple by the end...
Thanks for your moral support ❤️
Keep sharing brother
Thank u sir for it
Plz continue👌
Your welcome 😃
Jo question aap karte hai samagh aata hai but jab apne se karne ke kosis karta hu to nahi hota hai
No problem Just listen the video carefully. Then try to solve the same question. you may or may not be able to solve it. but you will do atleast something. Here comes muscle memory. After seeing the code you should know which line is doing what.
One of the best solutions. Thanks a lot for describing it in such a nice way.
Most welcome!
Great video. I have two question. 1. why move left in case max1 > min2, why not right shift. 2. why left array should be small. would be great if you can help me out.
Great Explanation!
Amazing, and thanks for creating it in Hindi
My pleasure 😊
same code ab nhi chalta gfg pe IDK why unhone testcases change kiya lagta
like {1,2,3,4,5} and {6,7,8,9,10,11} ka o/p 9 ata hai instead of 6
the best explanation for this problem
Why we take end1 = n1 and not n1 - 1 because we are taking begin1 = 0 as from 0 to n1 there are n + 1 element and in all searching problem we take low as 0 and high as n - 1?
I had a doubt that why do you apply binary search on smaller size array??
Is it because for smaller size array time complexity will be O(log(n)) and for larger size array it will be O(log(m) ??
Please rply
good.explanation sir 👍👍
Thank You Sir
Man you made it so easy for me thanks alot
Thanks a ton bro Please, share this channel in your college, groups, or LinkedIn bcoz it's cost nothing to you 😀
One of the best explanation
Glad it was helpful!
Well explained. Thanks!
Thanks for watching!
Divinding i2 we choosed (n+m+1)/2-i1
Can we divide it like n2/2+ 1?
Wo ye answer nahi kar payega, copy paste answer hai
thanks 🙏
best solution so far.
Keep sharing this video or channel in your groups
nahi bhaiyaa... achaa laga
why did u take end1 =n
not (n-1)??
can someone explain;??
Great video and super clear explanation! Can you please tell how is the time complexity O(log(m+n))? and why do we need to find i1 and i2 for the shorter array?
Yes, correct
Sir could u please 🙇🙇🙇explain the code for this input
7 4
-8 2 14 17 61 93 99
-4 -3 -2 1
while calculating manually I'm getting 2 as answer. as (-8,-4,-3,-2,1,2,14,17,61,93,99)median=A[11/2] = A[5] = 2.
While executing the code I'm
Getting -8(if I'm considering mid as (l+h)/2 or lower mid(l+(h-l)/2)
I'm getting correct answer if I'm considering upper mid which is l+(h-l+1)/2.
Could u please tell me sir generally in which case we have to use lower mid,mid ,upper mid.
For few other test cases upper bound is not working sir.
Please clarify my doubts sir,plzzzzzzzz.
Why we take end1 = n1 and not n1 - 1 because we are taking begin1 = 0 as from 0 to n1 there are n + 1 element and in all searching problem we take low as 0 and high as n - 1?
great explaination
best solution explanation
beautiful explanation❤️
Keep sharing my channel with your friends ❤️
this problem is next to impossible to think as a beginner ,
thank you so much sir
Your welcome 😃😃
Nice explanation. Thanks
Thanks shalini
Best explanation lots of love bhai
Thank you so much 😀
just op 👍👍👍✔✔✔✔✔✔✔✔✔✔✔✔
Nice bhaiya 😃😃
can you explain the question "find factorial of a large number also?"
Use BIG INTEGER in java
Epic explanation bro🔥🔥🔥 please make videos on cp as well, i'd love to learn from u🙏
Hard one
Why we are taking max of max1,max2 and same for min can anyone explain??
great explanation .......
Keep learning buddy and also keep sharing
can you please mention the reason behind stressing more power on considering N
I also have same doubt,pls explain if you have the ans to it
Because you want to get the time complexity O(log(min(m,n))) otherwise it will be O(log(max(m,n)))
Also you will not be able to divide the elements in two equal.sets if you calculate mid in the larger array
sir" Allocate the minimum no of pages" pe video banado please sir.#gfg
Check adity verma videos... Nice explanation
please make video on matrix median.🙏
See this playlist :
Matrix (Multidimensional Array) Complete guide For Interviews DSA: czcams.com/play/PLzjZaW71kMwRff0CCcrB93srEiQhJoOzg.html
Bhai maza agya.
Thanks buddy ❤️
Well explained!
Yeah 👍
if n=5 m=8 then why i2 = (n+m+1)/2
isme aise nhi krr skte jaise first arrays ke liye median nikaal lo. uske baad second array ke liye median nikaal lo and then uske baad unn dono ko add krke divide krr do 2 se
doosra array bahut bade number of elements ka ho sakta hai, to jo net array banega usme doosre array ka domination hoga naki unke average ka
i done this in few lines but time complexity not good and i use vector function
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
vector v;
v.insert(v.begin(), nums1.begin(), nums1.end());
v.insert(v.end(), nums2.begin(), nums2.end());
sort(v.begin(),v.end());
int n=v.size();
float sum;
if(n%2==0){
sum=(v.at(n/2-1)+v.at(n/2))/2;
return sum;
}else{
sum=(v.at(n/2)+v.at(n/2))/2;
return sum;
}
}
};
Nice 🙂
🤐🤐
i solved this ,but using vector functions
Yeah answer will come
But we have to take care of complexity
Aap samja achha rhe ho per pliz pent me line by line samjhao to or achhe se clear hoga
okay done
aage se dhyaan rakhenge
This code fails for the input case [3,4]
[1,2]
Same here....have you found correction?
nice sir
Thanks and welcome
bhai achha smjha rha hai but ye pdhate pdhate screen ke bhich me apna insta id na dikhao jise follow krna hoga vo kr hi dega , pda rhe hai ki advertisement kr rhe hai !!1
bro agar tum marker use karke bta dete to or achha hota
Yup ...but mere pass marker and white board ka setup nahi hai 🙄
same solution is discuused by sandeep jain gfg
edit:and examples taken are also same
why (m+n+1/2)? i did not understand this?
Also the time complexity according to me should be O(lg (min(m,n)) -- because you are taking min length arr extremes and calculating median
s+(e-s)/2=m isse ni yoga kia
smagh me nahi ara ha "Efficient solution se "
kyu
@@HelloWorldbyprince jaha se optimised approach shuru hui waha se ki dono array kase divide hore ha mid ke liye wo smgh me nahi aya,
I will watch it again once
Please try to use some notepad on your computer and record it while solving problems. You're approach is amazing but it might be more helpful if we could see you solve in front of us rather than us trying to imagine stuff or explicitly solve it parallelly when you explain it, while pausing and playing the video. The zoomed slides and screenshots are kind of irritating and does not let me focus on where you are. Need to actively watch you and see at what point we are. Hope you understand. Thanks for the amazing approaches and solution though! :)
A much more simpler solution.
The approach which I'm following is imagine we are going to merge the array into a completely new array. Then itearate the array in that way checking the value which we should put next. In this way if the array is off break the loop after half cycle and return the element at current position and if the number is even then break the loop after (n+1)/2 and sum nth and nth+1 element and divide by 2 and return.
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
total = nums1.length + nums2.length;
even = (total % 2 == 0);
int left = 0, right = 0;
for (int z = 1; z
nice dude
Aap samjhaye shi ho lekin ek hi word 50 baar bol kr irritate kr diye ho . Aisa lag rha ki
Aap khud hi confuse ho .
Maine sujhav diya hai baki aapki marzi .
Hme lgta hai ye ko aap 10 min me bata dete ager aap ke under confidence hota toh .
Title : English , Video Language: Not English
🤨
👎👎👎👎👎
For those, who are looking for //Base Case. Please find below.
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int n = nums1.size(); int m = nums2.size();
if(n>m) return findMedianSortedArrays(nums2,nums1);
if(n==0) return m%2 ? nums2[m/2] : (nums2[m/2]+nums2[m/2-1])/2.0;
if(m==0) return n%2 ? nums1[n/2] : (nums1[n/2]+nums1[n/2-1])/2.0;
int begin1=0, end1=n;
while(begin1
Why we take end1 = n1 and not n1 - 1 because we are taking begin1 = 0 as from 0 to n1 there are n + 1 element and in all searching problem we take low as 0 and high as n - 1?