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.

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

[@babulbhanu8935]

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

[@jinny5025]

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

[@techdose4u]

Welcome :)

[@ayushjain6604]

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

[@techdose4u]

Thanks

[@xacademia9646]

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

[@vikramreddy7586]

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

[@Ice-2706]

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

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

[@DavidCastro-sn3iy]

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

[@techdose4u]

Thanks :)

[@mj-sv7ep]

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

[@abhishekmore5856]

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

[@tbcfrankee]

Straightforward and clear! Thanks!

[@davidpham6330]

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

[@denniskang6768]

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

[@techdose4u]

Welcome 😀

[@saurabhchauhan232]

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

[@sexyeur]

Awesome! Thank you!

[@UCA12jryuRctKIGCxDkbub0Q]

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

[@akhiltyagi460]

really appreciate your explanation skills.

[@ranjith880]

Great visual presentation loved it

[@samridhshubham8109]

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

[@roushansingh9936]

One of the finest explaination, Thank You!

[@luxfortis4377]

amazing explanation, thank you!

[@priyankapardesiramachander871]

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

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

[@nishadhshah3267]

Finally understood this problem!! Thanks much!!

[@lasophistique3513]

Very clear explanation, thank you!

[@techdose4u]

Welcome :)

[@anime__ash]

Very Helpful!

[@aditgulia]

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

[@shivaakrish]

Amazing explanation!

[@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 :)

[@sarthakbhatia7888]

absolutely brilliant..

[@techdose4u]

Thanks :)

[@samrat4141]

Thanks for the explanation. It really helps.

[@shaswatpandey2991]

just amazing ! A huge appreciation for you.

[@techdose4u]

Thanks :)

[@mayankkumarprajapati2337]

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

[@techdose4u]

Thanks :)

[@haosmark]

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

[@WowPlusWow]

thanks for the video. Helped me out a lot.

[@techdose4u]

Nice :)

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

[@shobhitranjan3957]

Brilliant Explaination!

[@techdose4u]

Thanks :)

[@nitinshukla4960]

Really thanks buddy, Doing a great job :)

[@taocheng247]

This explantation is greater than any others.

[@techdose4u]

❤️ Thanks

[@omphemetsemafoko830]

Best explanation ever. Thanks a lot.

[@divanshuagarwal8236]

Great Explaination!!

[@techdose4u]

Thanks :)

[@kashifbilalali7609]

amazing explanation bro 👌🏽

[@pankajrathi]

such an amazing experience

[@techdose4u]

Thanks :)

[@ayushisaini5311]

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

[@techdose4u]

Thanks ❤️

[@sushantmahajan5289]

amazing explanation. Subscribed and liked :)

[@techdose4u]

Thanks

[@sushilmall254]

Great Explanation!!

[@techdose4u]

Thanks :)

[@ramnathan4236]

superb solution thank you sir :)

[@techdose4u]

Welcome :)

[@saubhagyadeep5488]

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

[@gayatri263]

Awsome keep explaining this way..

[@techdose4u]

Thanks :)

[@vipingautam1257]

Excellent!!

[@techdose4u]

Thanks

[@evgeni-nabokov]

You deserve subscription.

[@techdose4u]

Thanks :)

[@projectsdb4034]

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

[@sehejwahla5437]

Great help bro. Thanks from punjab !!

[@techdose4u]

Thanks paji

[@TeddyDeanShorts]

Nice one. Subscribed.

[@techdose4u]

Thanks :)

[@sujandvss2612]

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

[@shashanksharma7747]

Good explanation

[@rishabhkumar8115]

amazing explanation beautifully explained

[@techdose4u]

Thanks :)

[@seanmcelroy4074]

Thanks!

[@yy-gf7ze]

the literal excellent explanation.

[@techdose4u]

Thanks

[@princeanthony8525]

Simply brilliant

[@techdose4u]

Thanks 😊

[@shubhamsingh-gb5zh]

great explanation sir. Thank you

[@techdose4u]

Welcome :)

[@fullysimplified7139]

too awesome :)

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

[@4maxlol]

way better than leetcode thanks

[@rajatgupta-ld1wg]

Nice explaination :)

[@techdose4u]

Thanks

[@meghanaballa4966]

Thank u!!

[@techdose4u]

Welcome :)

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

[@mahipalsingh-yo4jt]

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

[@techdose4u]

👍

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

[@sharvyahmed]

Thanks :)

[@gokullohiya2602]

Got it. ThankYou

[@gokullohiya2602]

Liked + Subscribe + shared

[@techdose4u]

Thanks

[@rohandeshmukh3989]

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

[@techdose4u]

Thanks

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

[@apeirl5940]

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

[@techdose4u]

Thanks

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

[@immortal7167]

great!

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

[@fullysimplified7139]

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?

[@pathanshanawajkhan2638]

yes sir ,you deserve subscription + like + bell

[@techdose4u]

Thanks ❤️

[@gauravruhela007]

very nice!

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

[@priyanshjha6952]

Very helpful

[@techdose4u]

Thanks

[@shashankkumar1974]

Hello Sir which app you use for writing purpose.

[@khanmashequr]

What about for arrays with duplicates??

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

[@DucNguyen-bm2pl]

Indians are GREATTT at programming!!

[@asitkr7]

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

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

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

[@apuravsharma7034]

why are checking for = ????

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

[@keerthi442]

Bro,I have campus interview after 2 month Can you plz suggest what to study I'm flowing all your videos I like your videos a lot

[@techdose4u]

I have made a video on preperation in just 2 months. If you different help or you are already good in certain fields then contact me on LinkedIn.

[@anubhavraj2072]

Don't worry ,it will be postponed because of the pandemic. You can go through GFG

[@hrithiksytle5058]

@@techdose4u can you give your LinkedIn ID And can you mention in what Company do you work ??

[@shubhamsonal5871]

What if the element was present on the non increasing sub half , then we would never visit that half, so maybe this wont work for that case

[@techdose4u]

I said you need to find the increasing partition. Then compare the target with the range of increasing half. If target falls in the range then search in that increasing half otherwise search in the other half.

[@f3-faithfitnessfinance]

This will work for all cases ! It checks the increasing sub half as well . That's in the 'else' condition

[@techdose4u]

Yes you are correct :)