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

[@arunraju9705]

Dude, I appreciate the detailed presentation, you should know that you are doing a great service !

[@techdose4u]

Thanks:)

[@justinspired4188]

Totally agreed bro!! he is doing really good job, thanks !!

[@klausdupont6335]

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!

[@amansarma417]

last moment rap was awesome :D

[@SHAHARPIT92]

Even I liked it :P

[@techdose4u]

😅

[@HanifCarroll]

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.

[@babulbhanu8935]

got an offer from Microsoft after learning from this channel. Thanks :)

[@chloe3337]

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!

[@vikramreddy7586]

From the 7th Minute onwards, this video is GOLD !!!!! Jaha Pana Tussi Great Ho !!!!!!

[@davidpham6330]

BEST explanation I've seen on CZcams for this problem. Thank you!

[@omerbayram9533]

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!!!!

[@xacademia9646]

thanks I was gettin TLE in the first approach which I had thought by myself. Ur one pass solution really helped me :)

[@abhishekmore5856]

This is best explanation from all other explanations I have seen/read for this problem.

[@ayushjain6604]

A really good explanation. Could not imagine that this problem could be solved in this way as well! Appreciate the work.

[@techdose4u]

Thanks

[@jinny5025]

For dummies, your explaintion is always clear than ever. You deserve more subcribers. Thank you Tech Dose :)

[@techdose4u]

Welcome :)

[@mj-sv7ep]

Very clear and precise explaination. Got it in the first go. Thanks

[@saurabhchauhan232]

Excellent Explanation , haven't found better explanation of any problems than yours 🙏🏻

[@denniskang6768]

Looked at several other videos but still not clear. this one explains with great overall picture and logic ! thanks a lot !

[@techdose4u]

Welcome 😀

[@Chandrakumar-ub1uh]

one of the best application of binary search, you explained it very well, the approach without finding pivot element is best approach

[@techdose4u]

Thanks :) Actually using this approach, many harder problems are also solved.

[@vamsiKrishna96]

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?

[@tbcfrankee]

Straightforward and clear! Thanks!

[@samridhshubham8109]

Very detailed and clear explanation, very thanks for all your effort

[@priyankapardesiramachander871]

Sir, your channel deserves so much more attention and subs. Thank you.

[@techdose4u]

Thanks ❤️

[@DavidCastro-sn3iy]

Great explanation! subscribed to the channel!... Keep up the good work

[@techdose4u]

Thanks :)

[@Jason-ze8jv]

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?

[@ayushprakash8343]

great ! i loved your explanation ... keep up the good work !

[@roushansingh9936]

One of the finest explaination, Thank You!

[@ranjith880]

Great visual presentation loved it

[@nishadhshah3267]

Finally understood this problem!!
Thanks much!!

[@aditgulia]

At 12:06 , line 23 can also we written without checking target equal to mid elements. .ie
line 23 : if(target

[@akhiltyagi460]

really appreciate your explanation skills.

[@anshikagovil3774]

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]

Welcome :)

[@haosmark]

Best explanation to the problem. Thanks for taking the time to make the video.

[@shaswatpandey2991]

just amazing ! A huge appreciation for you.

[@techdose4u]

Thanks :)

[@taocheng247]

This explantation is greater than any others.

[@techdose4u]

❤️ Thanks

[@saubhagyadeep5488]

gud work bro... the explanation was simple and examples were ample to be able to understand this easily :)

[@samrat4141]

Thanks for the explanation. It really helps.

[@luxfortis4377]

amazing explanation, thank you!

[@nitinshukla4960]

Really thanks buddy, Doing a great job :)

[@omphemetsemafoko830]

Best explanation ever. Thanks a lot.

[@ayushisaini5311]

Best content i have ever seen in youtube thankyou so much .we just need to know more nd more from you😊😊😊 ...

[@techdose4u]

Thanks ❤️

[@lasophistique3513]

Very clear explanation, thank you!

[@techdose4u]

Welcome :)

[@0anant0]

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]

same ques

[@sexyeur]

Awesome! Thank you!

[@shivaakrish]

Amazing explanation!

[@priyadarshanr9950]

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 ?

[@mayankkumarprajapati2337]

Thankyou for such a great explanation really great video!!!!!

[@techdose4u]

Thanks :)

[@anime__ash]

Very Helpful!

[@sujandvss2612]

i have one doubt. what if the target is in non-increasing subarray

[@NIKHITAGARGBCE]

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

[@sarthakbhatia7888]

absolutely brilliant..

[@techdose4u]

Thanks :)

[@kashifbilalali7609]

amazing explanation bro 👌🏽

[@WowPlusWow]

thanks for the video. Helped me out a lot.

[@techdose4u]

Nice :)

[@sushantmahajan5289]

amazing explanation. Subscribed and liked :)

[@techdose4u]

Thanks

[@akshaykumarmalathkar2968]

What if the target element is present in the uneven part of the array? How does this code work then?

[@nishanmurarka3137]

same doubt

[@gyanendrasingh2003]

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]

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]

[@projectsdb4034]

Thanks for the great tutorial amazing, can you add some modification how to handle duplicate values because its not working for duplicate values.

[@shashanksharma7747]

Good explanation

[@gayatri263]

Awsome keep explaining this way..

[@techdose4u]

Thanks :)

[@shashankkumar1974]

Hello Sir which app you use for writing purpose.

[@shobhitranjan3957]

Brilliant Explaination!

[@techdose4u]

Thanks :)

[@evgeni-nabokov]

You deserve subscription.

[@techdose4u]

Thanks :)

[@sehejwahla5437]

Great help bro. Thanks from punjab !!

[@techdose4u]

Thanks paji

[@ramnathan4236]

superb solution thank you sir :)

[@techdose4u]

Welcome :)

[@rishabhkumar8115]

amazing explanation
beautifully explained

[@techdose4u]

Thanks :)

[@divanshuagarwal8236]

Great Explaination!!

[@techdose4u]

Thanks :)

[@VishalPatel_imvishal]

Can't we just check whether the target number is lies between left index and mid index. If not then search in right part?

[@4maxlol]

way better than leetcode thanks

[@programmingstuff5741]

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]

Okay I will....but I am stuck with leetcode for this month bro 😅

[@programmingstuff5741]

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

Please send me the question link in which you are stuck. I will see.

[@shubhamsingh-gb5zh]

great explanation sir. Thank you

[@techdose4u]

Welcome :)

[@ayushganguli1359]

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

[@DucNguyen-bm2pl]

Indians are GREATTT at programming!!

[@pankajrathi]

such an amazing experience

[@techdose4u]

Thanks :)

[@vishalmishra1937]

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]

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.

[@fullysimplified7139]

too awesome :)

[@sushilmall254]

Great Explanation!!

[@techdose4u]

Thanks :)

[@khanmashequr]

What about for arrays with duplicates??

[@mahipalsingh-yo4jt]

graph helps a lot in this question !!!!!!!!:)

[@techdose4u]

👍

[@seanmcelroy4074]

Thanks!

[@apeirl5940]

great video! other explanations on leetcode and youtube were much more complicated or had poor explanations.

[@techdose4u]

Thanks

[@yy-gf7ze]

the literal excellent explanation.

[@techdose4u]

Thanks

[@vipingautam1257]

Excellent!!

[@techdose4u]

Thanks

[@princeanthony8525]

Simply brilliant

[@techdose4u]

Thanks 😊

[@TeddyDeanShorts]

Nice one. Subscribed.

[@techdose4u]

Thanks :)

[@immortal7167]

great!

[@pathanshanawajkhan2638]

yes sir ,you deserve subscription + like + bell

[@techdose4u]

Thanks ❤️

[@sharvyahmed]

Thanks :)

[@rajatgupta-ld1wg]

Nice explaination :)

[@techdose4u]

Thanks

[@fullysimplified7139]

Thanks

[@rohandeshmukh3989]

very nice explanation sir!!!!!!!!

[@techdose4u]

Thanks

[@gokullohiya2602]

Got it. ThankYou

[@gokullohiya2602]

Liked + Subscribe + shared

[@techdose4u]

Thanks

[@meghanaballa4966]

Thank u!!

[@techdose4u]

Welcome :)

[@gauravruhela007]

very nice!

[@techdose4u]

Thanks :)

[@yashgoswami5374]

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]

(2+3)/2 = 2 in integer. It is always the floor value.

[@yashgoswami5374]

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

Integer wrap around INTMIN to INTMAX. So numbers too will wrap around simply

[@yashgoswami5374]

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

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.

[@shaswatsingh]

what happens if the case is [5,0,1,2,3,4]

[@ayushthakur2896]

What if the target is lying in the non uniform part? I have this doubt .... plz someone help

[@priyanshjha6952]

Very helpful

[@techdose4u]

Thanks

[@mohammedsadiq5729]

Definitely first

[@techdose4u]

:D

[@asitkr7]

its not working for this input for me :
nums[]={1,3,1,1,1};
target= 3;

[@apuravsharma7034]

why are checking for = ????

[@sumanthreddynithiin2109]

what if we want to search an element , which is present in un-informed range

[@techdose4u]

Element can be anything but array should be sorted rotated.

[@prashumatam9816]

Hi do you do personaltraining if yes can i know how to contact. I am looking for full time opportunities now

[@techdose4u]

Yes I do. Please contact on LinkedIn, Instagram, Whatsapp: [phone]

[@vikrantharne9345]

how to do this
input---->[apple,ball,cat,dog] ,2,dog and
output--->1 (cat is at 2 and dog is at 3 so 3-2=1)
now
input----[aaa,bbb,ccc,ddd,eee] ,1,eee
output--->2 (bbb is at 1 and eee is at 4th index)
how to implement this