Search in rotated sorted array | Leetcode #33
This video explains a very important interview coding problem which is to search a target element given a originally sorted array in ascending order which has now been rotated. We are required to find the pivot element in just O(log N) time. I have explained 2 binary search approaches. The first approach finds the target element by first calculating the pivot element and then find the target element which takes 2 traversals of the given array. The second approach is better which solves the problem in just a single traversal of the array using binary search and this is the most optimal approach for this problem. CODE for BOTH approaches are present in the same CODE LINK file. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...
Пікірлер: 207
Dude, I appreciate the detailed presentation, you should know that you are doing a great service !
@techdose4u
4 жыл бұрын
Thanks:)
@justinspired4188
3 жыл бұрын
Totally agreed bro!! he is doing really good job, thanks !!
This video is extremely illuminating. We just need more videos like this one. Leetcode discussion always talks about the final optimized solution where the thought process is invisible. This video demonstrates the thought process -> 2pass solution -> 1pass solution and finally helps everyone understand how the optimization occurs. Good job!
last moment rap was awesome :D
@SHAHARPIT92
3 жыл бұрын
Even I liked it :P
@techdose4u
3 жыл бұрын
😅
i was really confused by the searching in the uniform approach at first but i realized that its easier to set the conditions for the uniform approach than the non uniform approach, thanks!
got an offer from Microsoft after learning from this channel. Thanks :)
This was a great explanation! I've watched a couple of videos and read some explanations on Leetcode for this problem, but I still couldn't quite understand it. There were two things you said that really made it click for me: 1. There is always at least 1 half of the array where the values are increasing. 2. We want to find that half, and then see if the target is inside that subsection.
thanks I was gettin TLE in the first approach which I had thought by myself. Ur one pass solution really helped me :)
BEST explanation I've seen on KZread for this problem. Thank you!
From the 7th Minute onwards, this video is GOLD !!!!! Jaha Pana Tussi Great Ho !!!!!!
For dummies, your explaintion is always clear than ever. You deserve more subcribers. Thank you Tech Dose :)
@techdose4u
3 жыл бұрын
Welcome :)
This is best explanation from all other explanations I have seen/read for this problem.
Wow! I watched a lot of videos but I just could not wrap my head around it.. This explanation was the answer which I was looking for!!!!
One of the finest explaination, Thank You!
Very clear and precise explaination. Got it in the first go. Thanks
A really good explanation. Could not imagine that this problem could be solved in this way as well! Appreciate the work.
@techdose4u
3 жыл бұрын
Thanks
Finally understood this problem!! Thanks much!!
Straightforward and clear! Thanks!
Best explanation to the problem. Thanks for taking the time to make the video.
one of the best application of binary search, you explained it very well, the approach without finding pivot element is best approach
@techdose4u
4 жыл бұрын
Thanks :) Actually using this approach, many harder problems are also solved.
great ! i loved your explanation ... keep up the good work !
Looked at several other videos but still not clear. this one explains with great overall picture and logic ! thanks a lot !
@techdose4u
2 жыл бұрын
Welcome 😀
Excellent Explanation , haven't found better explanation of any problems than yours 🙏🏻
Thanks for the explanation. It really helps.
amazing explanation, thank you!
Great explanation! subscribed to the channel!... Keep up the good work
@techdose4u
4 жыл бұрын
Thanks :)
Very detailed and clear explanation, very thanks for all your effort
Great visual presentation loved it
Amazing explanation!
Sir, your channel deserves so much more attention and subs. Thank you.
@techdose4u
3 жыл бұрын
Thanks ❤️
It becomes so easy to understand the approach to solve problems by watching your videos. Thanks a lot for making it so easy for us to understand the solutions.
@techdose4u
4 жыл бұрын
Welcome :)
just amazing ! A huge appreciation for you.
@techdose4u
2 жыл бұрын
Thanks :)
really appreciate your explanation skills.
This explantation is greater than any others.
@techdose4u
2 жыл бұрын
❤️ Thanks
Very Helpful!
Really thanks buddy, Doing a great job :)
Awesome! Thank you!
Hey, is it a good practise to generalise a pattern after seeing three examples? Is there any other way to prove there'll bs strictly increasing sequence in one half of the array?
At 12:06 , line 23 can also we written without checking target equal to mid elements. .ie line 23 : if(target
amazing explanation bro 👌🏽
Good explanation
Best explanation ever. Thanks a lot.
gud work bro... the explanation was simple and examples were ample to be able to understand this easily :)
Very clear explanation, thank you!
@techdose4u
3 жыл бұрын
Welcome :)
Great video :) I was a little confused about the code for the first approach - why is the right pointer updated to mid rather than mid - 1?
too awesome :)
way better than leetcode thanks
Best content i have ever seen in youtube thankyou so much .we just need to know more nd more from you😊😊😊 ...
@techdose4u
2 жыл бұрын
Thanks ❤️
Thankyou for such a great explanation really great video!!!!!
@techdose4u
3 жыл бұрын
Thanks :)
absolutely brilliant..
@techdose4u
3 жыл бұрын
Thanks :)
i have one doubt. what if the target is in non-increasing subarray
Excellent!!
@techdose4u
3 жыл бұрын
Thanks
amazing explanation. Subscribed and liked :)
@techdose4u
3 жыл бұрын
Thanks
Thanks!
thanks for the video. Helped me out a lot.
@techdose4u
3 жыл бұрын
Nice :)
Hello Sir which app you use for writing purpose.
Awsome keep explaining this way..
@techdose4u
3 жыл бұрын
Thanks :)
Thanks! Very well explained. I have a question about line 21 as explained @ 11:40. You say we are checking for strictly increasing left half, but check a[left]
@pranavsharma7479
2 жыл бұрын
same ques
What if the target element is present in the uneven part of the array? How does this code work then?
@nishanmurarka3137
2 жыл бұрын
same doubt
@gyanendrasingh2003
2 жыл бұрын
See, if its in the part in which array is not sorted we will still apply binary search on it and check again whether its on sorted part or not, and do it till we find it
@shivanshgupta5657
2 жыл бұрын
class Solution { public: int bsearch(vector&nums,int t,int l,int r){ while(lt) r=m-1; else l=m+1; } return -1; } int lsearch(vector&nums,int t,int l,int r){ int m=(l+r)/2; if(nums[l]
Thanks :)
Simply brilliant
@techdose4u
2 жыл бұрын
Thanks 😊
Indians are GREATTT at programming!!
Brilliant Explaination!
@techdose4u
4 жыл бұрын
Thanks :)
great!
superb solution thank you sir :)
@techdose4u
4 жыл бұрын
Welcome :)
Thanks for the great tutorial amazing, can you add some modification how to handle duplicate values because its not working for duplicate values.
You deserve subscription.
@techdose4u
4 жыл бұрын
Thanks :)
how can you find the strictly increasing by just comparing the mid-value with the left and right elements? At 10:35 you said mid element 2 is smaller than left value 7 so it is not strictly increasing but the 2 is also smaller than 6, the rightmost value, so how come second case id strictly increasing... so how can you judge which one strictly increasing and which one's not
Great help bro. Thanks from punjab !!
@techdose4u
3 жыл бұрын
Thanks paji
Great Explaination!!
@techdose4u
4 жыл бұрын
Thanks :)
Great Explanation!!
@techdose4u
4 жыл бұрын
Thanks :)
such an amazing experience
@techdose4u
3 жыл бұрын
Thanks :)
Nice one. Subscribed.
@techdose4u
3 жыл бұрын
Thanks :)
Sir, this code won't work for rotated sorted array (sorted in descending order) right, we should be changing it to (nums[left] >= nums[mid]), am I right sir ?
What about for arrays with duplicates??
amazing explanation beautifully explained
@techdose4u
3 жыл бұрын
Thanks :)
great explanation sir. Thank you
@techdose4u
3 жыл бұрын
Welcome :)
Thanks
very nice explanation sir!!!!!!!!
@techdose4u
3 жыл бұрын
Thanks
the literal excellent explanation.
@techdose4u
3 жыл бұрын
Thanks
yes sir ,you deserve subscription + like + bell
@techdose4u
3 жыл бұрын
Thanks ❤️
Thank u!!
@techdose4u
2 жыл бұрын
Welcome :)
graph helps a lot in this question !!!!!!!!:)
@techdose4u
3 жыл бұрын
👍
Got it. ThankYou
@gokullohiya2602
3 жыл бұрын
Liked + Subscribe + shared
@techdose4u
3 жыл бұрын
Thanks
Nice explaination :)
@techdose4u
3 жыл бұрын
Thanks
Can you post videos on Google Kickstart round A and B Solution I think these are good question to practice and your explanation is quite better than other
@techdose4u
4 жыл бұрын
Okay I will....but I am stuck with leetcode for this month bro 😅
@programmingstuff5741
4 жыл бұрын
@@techdose4u But you can post one video at a day similar to leetcode I am stuck at these problem I think your video will clear all my doubts having. Good explaination
@techdose4u
4 жыл бұрын
Please send me the question link in which you are stuck. I will see.
Can't we just check whether the target number is lies between left index and mid index. If not then search in right part?
sir what if first we find pivot index around which array is sorted and then after comparison we can use binary search with appropriate range .this method will do or not
@techdose4u
4 жыл бұрын
I explained this in Method 1. Please watch the video carefully. I have also provided the code for the same. So, it will definitely work na.
great video! other explanations on leetcode and youtube were much more complicated or had poor explanations.
@techdose4u
3 жыл бұрын
Thanks
What if the target is lying in the non uniform part? I have this doubt .... plz someone help
I believe,Searching through the peak element is a wrong solution even after ignoring need to traverse twice. For eg- 5 4 1 2 3 has peak elements 4 and 3. 3 is peak as 2
Hi do you do personaltraining if yes can i know how to contact. I am looking for full time opportunities now
@techdose4u
2 жыл бұрын
Yes I do. Please contact on LinkedIn, Instagram, Whatsapp: +91 8918633037
very nice!
@techdose4u
3 жыл бұрын
Thanks :)
why are checking for = ????
its not working for this input for me : nums[]={1,3,1,1,1}; target= 3;
what if we want to search an element , which is present in un-informed range
@techdose4u
3 жыл бұрын
Element can be anything but array should be sorted rotated.
Very helpful
@techdose4u
3 жыл бұрын
Thanks
100/100 for explaination
Definitely first
@techdose4u
4 жыл бұрын
:D
here your are using L+R/2 inorder to find mid. my doubt is if L and R both are int values and when you perform L+R then where this result will be stored because let say L and R are containing very big values (L=Integer.Max -2 and R=Integer.Max) then L+R well be overflaw , L+R will out of the range of integer and hence we will get wrong results. so, will L+R will be stored in some integer box(of memory) or somewhere else which can hold such a big value???
@techdose4u
4 жыл бұрын
(2+3)/2 = 2 in integer. It is always the floor value.
@yashgoswami5374
4 жыл бұрын
@@techdose4u but suppose (2+3) is very very big number then it will go out of the range of integer then what will happen?
@techdose4u
4 жыл бұрын
Integer wrap around INTMIN to INTMAX. So numbers too will wrap around simply
@yashgoswami5374
4 жыл бұрын
@@techdose4u yes, exactly but as it will start from INTMIN and that is from -ve range so, if it will give you -ve result Or Even if it will give positive result then also either you will get index out of bound error or you will get wrong mid index, isn't it???
@techdose4u
4 жыл бұрын
You can add 1 GB matrix with another 1GB matrix and still you won't reach INT_MAX. That's how big INT_MAX is. So, don't worry. If you are adding range of matrix then it won't ever wrap around.
what happens if the case is [5,0,1,2,3,4]