15 Minimum Difference Element in a Sorted Array
ฝัง
- เผยแพร่เมื่อ 25 ธ.ค. 2024
- Given a sorted array, find the element in the array which has minimum difference with the given number. .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
almost all of the viewers are able to think that we have to find ceil and floor to solve this problem because he made a solid base of approaching a problem if anyone follow the playlist sincerely such a finest tutor he is
if you know ki ceil value find krni ho to last me arr[high] return krvado or floor value find krni ho to arr[low] return karvado simple....
@@harikrushnasuhagiya3925 its actually opposite... if you want to find ceil then return arr[start] or arr[low], and if you want to find the floor then return arr[end] or arr[high].
Yes me too thinking the same bro ❤
True
True
another way to think about it is, find ceil and floor of the key and select between them
Even I had the same thought :)
Same here :)
This also means that we can apply this approach in finding floor and ceil of an element
Ekdum. Mai bhi yehi socha...tha....but the one taught by Aditya is 🔥is time efficient 💪
Exactly
dont say thanks. i need to say thanks to you. you helped me fall in love with coding. thank you
Happy to hear that! bro ✌️
First me floor and ciel find krke min diff return krne ki Socha tha ... fir vdo dekha toh sir ji ne simple bianry search la concept use krke solve krr diya...
Waaah
Yeh Master nahi Jaadugar hai 🪄🪄✨✨ !!! Crystal Clear Explanation.
I got too much confidence in the concept of Binary Search...thank you so much, sir, for uploading this playlist.
To break it down into the problems we already solved, need to find floor & ceil of the given element and return one of them which has min diff with the given key
Yeah could be a solution, thats really the creative thinking I want everybody to develop.
@@TheAdityaVerma but we can use same algo to find ceil and floor of key.Right??
@@keen_dev at the end low is pointing to ceil and high is pointing to floor . but just make sure the key doesn't exists then only valid
@@sanjayjoshi8807 Even if key exists it's still valid cuz in that case absolute difference will become zero
@@sanjayjoshi8807 Use % n
"Ye Koi Co-incindence nahi hai, ye har baar aisa he hoga.." , :D bahut sahi, is se pehle ki janta ko lage ki ye toh a gaya luckily, bhai ne clear kar diya abe har baar aisa he hoga :)
😂😂😂😂😂😂😂😂😂
This Binary Search playlist is dope and that is all anybody will need to crack interviews. Amazing...
Just make sure that the key to be searched isnt lesser than a[0] and greater than a[n-1]. In such cases the high/low can go out of index(-1 or n) so before checking the abs diff see if they are valid indices.
Oh man, you're legendary programmer, last 3 videos just saw the problem statement. I thought of the approach and coded it. You're OP in programming.
This is my approach ...........
Returns ceil of key (different than aditya sir's logic ) and calculates the min difference
int mindiff(int a[],int low,int high,int key){
while(low
Please upload more DP videos on topics you showed in the introduction to DP video .Your way of teaching is awesome. College placements are near ,need your help desperately 😂😂
where are you working now sir?
Sir, I want to touch your feet, you are a teacher which every student deserves. God Bless!!
Another way is to find floor and ceil..and select between them...thanks a lot ..such a great tutorial on youtube
I was waiting for him to talk about floor and ceil which he taught before😁
But this way is also nice!!
Thank you for a great explanation. Ultimately, we are finding floor & ceil of key. We all had a thought of this approach while watching floor or ceil video (at least I had).One of the comments in ceil video even mentioned the same approach.
Just after listening to the problem statement, the solutions strikes floor and ceil of the key would do the work as well. Thanks, Aditya! If we start thinking in such a manner, gonna ace every interview!!! :D
*But implementing the way showed in the video would save time.
After watching this video, satisfaction automatically brings a smile to my face (Thanks a lot bro)
After you explained problem statement then i paused the video and came up with that, i can find ceil and floor then take min difference between them and return it .......
This all i was able to think because of you all previous beautiful explanations 💯🤩😍😘😘😘
Bhai!! Kya observation hai! Mind blowing! Kya dimag lagaya hai!
Please upload more tutorials on graphs ,hashing ,backtracking....
your videos are really helping a lot.
Thank you so much.
Thanks, will do!
@@TheAdityaVerma Thank you for your initiative.
Please upload lectures on Backtracking
best video of Binary search playlist
What a beautiful problem and you’re a great teacher
I think we should keep a check if low=0 so that we don't access invalid memory.
Try to dry run for an array like 1 3 8 10 or 15 18 20 21 for key equals 12. You will understand.
literally itna easy maine 1 ghanta socha aur using min & ans variable se kiya aur last wala arr[mid] < key and key
Very good approach ...best ques so farr.....just using the concept of while loop breaking..ceil and floor
This method can be also applied to find ceil and floor :)
Ya i had the same thought
You explained very well .Sir ,Please upload lectures on binary trees as many companies also ask about them .
BASE CASE:
if ( key < arr[0] ) return arr[0];
if ( key > arr[n-1] ) return arr[n-1];
if ( key < arr[0] ) return arr[0] - key;
if ( key > arr[n-1] ) return key - arr[n-1];
Also after seeing this video we can conclude that:
floor : end pointer after the whole execution of loop,if mid is not exist.
ceil : start pointer after the whole execution of loop,if mid is not exist.
The corner cases are not handled in the video.....let suppose arr={ 3,4,5 } and key= 6 then after the end of the while loop high=2 and low=3 but while comparing ( arr[ low] - key ) will give segmentation fault as arr[3] is not present in the array above (array out of bound ).
Similarly, if the key=2 then at the end high= -1 and low= 0 and arr[high] will give the same error.
The solution could be:
int a = INT_MAX, b=INT_MAX;
if ( low < N ) { a= abs( arr[low] - key ); }
if ( high >= 0 ) { b= abs( arr[high] - key ); }
return ( min ( a , b ) ) ;
Correct me....if I'm wrong anywhere.
Nice explanation your videos are really good...please keep on making such videos.
My approach was to find the floor and ceil of the given number and then check for min diff
This seems less complicated. Thanks
me did the same.
Yes
Amazing Explanation !! Thanks for making for these videos !
You could encounter an "index out of range" error in your original code in cases where the binary search leads left or right outside the valid indices of the array. Specifically, this can happen when the target is smaller than the smallest element or larger than the largest element in the array.
use this
if(left>=arr.length){
return arr[right];
}
if(right
Thanks Sir... Wonderful explanation
After completing while loop there may be chance that low can point to -1 when key is lesser than all the elements in the array and high can point to length of array of key is greater than than all the elements . We need to check these two conditions.
Just the reverse actually. low can point to the length of the array and high can point to -1.
You can also use the peak element kind of concept here as the absolute difference will make a valley and you just have to find the least element in the valley.
@Aditya Verma
We can also use this technique to find the ceil and floor of an element.
Please let me know if I am wrong.
Boundary check is missing, if low crosses upper bound or high crosses lower bound, we need to put check for that. Right?
will you to going upload playlist on patterns in Greedy Algorithms? Please try to upload videos soon as Placements session is very close.
At first i thought of using ceil and floor concept but the one u showed was much simpler
Nice explanation bro. Thanks!!!
This approach could be applied to find floor/ceil/floor & ceil in one go. We don't really need to store the intermediate results as described in one of your earlier videos. if the arr[mid] == el, return mid. Otherwise, simply compare the start and end after the while loop and return accordingly.
But u have to write two functions for floor and ceil seperately and time complexity will also be greater for the above approach and this video's approach is best because it is exactly same as binary search
@@rishabsinha8749 Not necessary. You can find ceil and floor in one function itself. And time complexity will be the same as normal Binary Search
// Floor and Ceil of an element
const floorAndCeilOfElement = (arr, key) => {
let start = 0;
let end = arr.length - 1;
let ceil = -1;
let floor = -1;
while(start key){
ceil = arr[mid];
end = mid - 1;
}
if(arr[mid] < key){
floor = arr[mid]
start = mid + 1;
}
}
return [floor, ceil];
}
learnt a new concept bro thanks
My code-
int minDiffElement(vector& arr,int key){
int n=arr.size();
int left=0,right=n-1;
int minDiff=INT_MAX;
int ans;
while(left
Such a nice video... thanks for it... pls make videos on system design questions
Love your explaintion
Sir yhn ,par nearly sorted array ka concept bhi laga skte hain na ?? Kuki neighbours hin and hogen if key present nhi rhga toh ????
Thank you very much😘
First I'm thinking to find floor and ceil of the key if jey is nit present then return mim diff😅😅but sir ji aone toh aur zyada jam lines me ans bata diya❤❤❤❤
We need to take care of one more condition what if our key is greater than the largest element or what if our key is less than the smallest element. So in the case when the key is greater than the largest element our start would point at nth index(which is incorrect) and in the second case when our element is less than the smallest element our end would point at -1(which is incorrect)
EX:-
1) arr[1,4,5,8,9] X=10
2) arr[2,4,5,8,9] X=1
We can in this case do an if check twice for if high not less than 0 and low not greater than n+1, then calculate result. To make it work for length 1 and 2 array, just do no return. Do Binary Search for length 3 or greater.
sir does this mean that we can return low or high for the floor and ceil problem respectively as well without storing the result in another variable?
Basically, those 2 neighbours are floor & ceiling.
after one by one, we are doing a postmortem on binary search🤣.... as we are getting a fundamental but new and unknown thing about this.... amazing
please add the links of the platforms on which we can find this question or similar one.
Thank you very much.
WOW !!! what an observation of binary search man !!!
That was amazing!
What is wrong with iterating through array and finding the minimum diff value of key and array element
for(int i=0;iMath.abs(a[i]-k)){
val=Math.abs(a[i]-k); ans=a[i];
}}
return ans;
complexity bro
Time complexity bro
// Floor and Ceil of an element
const floorAndCeilOfElement = (arr, key) => {
let start = 0;
let end = arr.length - 1;
let ceil = -1;
let floor = -1;
while(start key){
ceil = arr[mid];
end = mid - 1;
}
if(arr[mid] < key){
floor = arr[mid]
start = mid + 1;
}
}
return [floor, ceil];
}
//Main Logic
const minimumDifferenceElement = (arr, key) => {
let [floor,ceil] = floorAndCeilOfElement(arr,key);
let diff1 = Math.abs(floor - key);
let diff2 = Math.abs(ceil - key);
return diff1 < diff2 ? floor : ceil;
}
Pen and papper combination is also best 👍👍👍👍
If I am not wrong then we can use this approach to find floor and ceil as well??
yes ofc
@@kirtikhohal3313 never
E.g. 1,2,3,4 key =5
At last end is at 3 and start is at 4 4 that means according to you floor is 3 and ceil is 4 that's not correct for this floor is 4 and ceil not defined 😅
start=0
end=len(arr)-1
mid=-1
diff=sys.maxint
while start
Great video. Just had a doubt. We can use this same technique while finding the ceil and floor for an element right? I mean one of his videos explains it but that solution is too long. This seems to be a smarter way to do it
Ys I m also thinking about this 😅
another way to think about this ques is you just have to find the target element but while doing it keep a variable and change the absolute diff again and again that will give you an answer ;)
We can find floor and ceil as arr[end] and arr[start] respectively.
simply find the floor index and then find the minimum value from floor index and floor+1 index.
Almost Bowdown❤
we can also find lower and upper bound of key and subtract key from it who ever gave minimum return that element
really amazing playlist!!!
The issue with this code is when you have to search for a element which is greater than your Max element of array.. Then list index goes out of range..
Please correct me if I am wrong
@Sourabh Patil
I thought the same ...then what to do u think?
Only one index will be valid at that time and you only need to compare it with that index to get the min difference.
you could check before performing binary search:
if(targetarr[n-1]) return target-arr[n-1]
@@venkateshkulkarni2227 Thanks, there is only a slight mistake .As we have to return the element,
if(targetarr[n-1]) return arr[n-1];
Can I find floor and ceiling by this method as well?
If key is greater than all the elements present in the array then one edge case should be there to check for the low index value (which points to max size of array) i.e., it should be less than max size of array in that case we return ABS( a[high] - key).
Same for the lowest value also high point at index "-1" so ABS( a[low] - key).
Plz Correct me if I am wrong?
Just Brilliant
To all those suggesting floor and ceil method
O(logn) < O(2*logn)
Then using this we can find ceil and floor too right using start and end index/ value respectively?
Have a doubt why we do need to get the absolute difference between high and low both? As it will be always number - arr[low] for what case we are taking number - arr[high] also?
well explaination
i just watched the video till 2 :32 ,and my solution approach is min(diff(k,floor of k),diff(k,ceil of k))
Haha same, and I was so sure that he's also gonna tell this, but he made the solution more easy and less lengthy.
thanks bro
13:00 ye climax toh rohit shetty ki movies se bhi bada tha🤣🤣🤣
Sir plZ backtrack or graph daal dijiye..internships start ho chili h..ab tak thik se prepare nhi hua....aap daaldenge toh next year tak achee se prepare hojega
Find ceil and floor then print minimum between them, is this approach is correct?
there's one thing we need to check .. lets say array is 10,12,14,16,19 and key is 9.. In this case arr[end] at the end of while loop will give segmentation fault as end will be -1.. so before doing key-arr[start] , key-arr[end] after while loop we should check start, end are >=0 &&
yes , we have to check that
explicitly ..
Bhaiya can we apply the same algorithm for ceil and floor??
bhai bhot pyaara samajhaate ho
Can't we use the same approach to find the floor and ceil of an element ??
It's possible only when key is not present
@@NikhilKumar-of5gb But isn't it still possible? Since if the key is present then the floor/ceil of the key is simply the key itself.
But u have to write two functions for floor and ceil seperately and time complexity will also be greater for the above approach and this video's approach is best because it is exactly same as binary search
if the key is greater than the last element of the array we can simply return the last element of the array right ? as that would be the element with minimum difference ?
can i just use simple binary search and compare the difference with middle element?
becos it will automatically include left and right elements..
Hey what if the key is greater than the last element or lower than the first element, then we will not get both bounded numbers to choose from.
I am beginner just wanted to know can we solve it by ceil and floor, I have done this by ceil and floor and code has rum also. I want there no exception in this na?
seems it would fail if the key is outside of range, for ex - arr = [1,3,8,10,15] and key =20. it will fail. instead output should be 5.
no it will not , at the end high will be 4 and low will be 5 . and and will be key-arr[high] => 20 -15 =5.
in this case ,you have to check if key value less than a[0] then return a[0]-key....and if key>a[n-1] then return key-a[n-1].
Can we do it this way:
1. Maintain a variable ```result = INT_MAX``` which is supposed to store the minimum absolute difference
2. At each step, find the **absolute** difference of ```arr[mid] - target```
3. Compare it with the variable ```result``` => ```result = min(result, abs(arr[mid] - target))
4. Let the algorithm converfe using the standard logic of Binary Search (when we eliminate the search space)
5. The final answer should be stored in ```result``` variable
bhaiya your videos are very helpful , but in dynamic programming playlist plzz upload on minimum edit distance also because you skipped that. After studying from your videos I can correlate all the things that's why I am requesting for this.
Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
@@TheAdityaVerma brother its may ............. where r u
@@TheAdityaVerma Your videos are really helpful 👍
Kindly upload backtracking lectures.
This will give an error when the index of low or high goes out of bounds.
Taking the same array , arr = [1,3,8,10,15] and key = 20.
The low index will be at 5 which will give an index error after completing the binary search.
We can avoid this by just checking whether arr[n-1] >= key or not.
Hi Aditya, what if low/high goes out of array bounds? Could be the case if we have x = 16 in your example....low will be equal to n.
Yes....the corner cases are not handled in the video.....let suppose arr={ 3,4,5 } and key= 6 then after the end of the while loop high=2 and low=3 but while comparing ( arr[ low] - key ) will give segmentation fault as arr[3] is not present in the array above.
Similarly, if the key=2 then at the end high= -1 and low= 0 and arr[high] will give the same error.
The solution could be:
int a = INT_MAX, b=INT_MAX;
if ( low < N ) { a= abs( arr[low] - key ); }
if ( high >= 0 ) { b= abs( arr[high] - key ); }
return ( min ( a , b ) ) ;
legend++😍😍
bhai plz try to put some question links related to the questions so that it will be easy for us to hover that question