Search in rotated sorted array - Leetcode 33 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Solve it yourself: neetcode.io/problems/find-tar...
0:00 - Conceptual
8:55 - Coding solution
#Coding #Programming #CodingInterview
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

🚀 neetcode.io/ - A better way to prepare for Coding Interviews Search in Rotated Sorted Array II - kzbin.info/www/bejne/pYbRd2qlbZ2SjsU

[@target90plus69]

[@expansivegymnast1020]

This is lowkey one of the hardest problems I've done so far. Great video!

[@feitan8651]

I watched this video for 3 times to understand the solution, so yeah ur right.

[@symbol767]

This problem was difficult as hell because of how we need to setup so many conditions and move the pointers correctly depending on where we are currently with mid pointer, jeez. I hate this problem honestly. Thank you for your solution, liked and commented for support.

[@averychen4633]

yes. Seriously, what is the point of this kind of problem?

[@sebastianramirez5781]

I feel like you've watched every single one of these videos and left a comment as to why it was hard, been doing neetcode 150 and you're always there

[@wonderfulsnow]

You can use binary search to find the pivot index, and then another binary search in the appropriate part of the array.

[@erikm9768]

This is a really good idea, less confusing

[@aadil4236]

How?

[@wonderfulsnow]

@@aadil4236 your array looks something like 7 8 9 1 2 3 4 5 6 Save the first element for reference: a0 = 7. Take the middle element of the array (2). If it’s smaller than a0, then your pivot element is to the left. Else, it’s to the right. Repeat, and you will find the index of your pivot element in O(log n) time. Then, if the value you’re searching for is larger than a0, use binary search in the left part of the list (from 0 to pivot index). Otherwise, the right side (from pivot index to end).

[@import_numpy_as_pd2330]

@@wonderfulsnow you responded to a year old comment, damn!

[@dk20can86]

@@wonderfulsnow Thank you, this is so much easier to grasp mentally than the other solution. This was my first thought but then i dismissed it because i couldn't figure out how to know if the pivot was greater or less than my current element.

[@ThePacemaker45]

First leetcode medium I was able to solve by myself without looking at the solution cause of your solution vid for Problem 153. I know it's just baby steps but it's sooo encouraging. Thank you so much man 😅

[@legspinismylife]

array problems make me feel like i have IQ below 80

[@kevindebruyne17]

One of the most annoying questions of Leetcode explained so easily! I hope I could develop the skill to implement this without getting confused again and again! Amazing work!

[@tanaykamath1415]

so me!

[@pinakadhara7650]

Can't relate more

[@fays_bn4321]

Same, you should have that KDB vision !

[@LeakCentral]

So amazing, Kevin DeBruyne doing Leetcode just for fun when he makes millions playing soccer

[@dhawalc4975]

I like how you can talk now!

[@danielgareev8877]

For me this solution was a bit more intuitive: l = 0 r = len(nums) - 1 while l = nums[l]: if nums[l]

[@Arthurgarzajr]

I agree. This one reads better.

[@crosswalker45]

Hey.. Even I came up wid same solution

[@djsosofresh]

Agreed, able to reason this solution much more easily

[@jeffinkachappilly9708]

Thanks for sharing this.(really easy to understand)

[@pinakadhara7650]

This is much easier to read

[@iamsmitthakkar]

thanks for the solution. For those who gets confuse in the if conditions (just like me) in this solution, you can refer to below solution. It works class Solution: def search(self, nums: List[int], target: int) -> int: l, r = 0, len(nums)-1 while l nums[mid] and target

[@allnewdevelopers]

thanks this way makes way more sense to me did it myself just following your comments guide! The OR in his solution threw me off lol

[@shonoma]

I found your explanation very helpful. As @allnewdevelopers mentioned, I was also confused about the OR. Thank you for your contribution!

[@xaviermeimei]

good ol' demorgan's law. thanks!

[@legendarygaming7790]

very clearly explained. Thank you for this. I was also considering the right rotated array and was trying to find a generalised soln. guess that the question only demanded for the left roated array.

[@tanvirahmed7993]

I struggled with this problem for 3+ years and tried to memorize the solution as I was always got confused when thinking many different options. This is the best explanation.

[@user-wf3bp5zu3u]

That "or" is what got me. I figured out you could check for either condition, but not that you had to check both. I got confused and assumed that knowing whether you were in the right/left sorted portion gave you some bounds guarantees, and you only had to check one of the conditionals. Going to spend some time drawing this out to make sure it sunk. Thank you so much NeetCode!

[@iamsmitthakkar]

I got confused with those condition as well. You can try my solution (commented above) with different if/else conditions. class Solution: def search(self, nums: List[int], target: int) -> int: l, r = 0, len(nums)-1 while l nums[mid] and target

[@vuminhnhat4061]

To reduce the if else condition in left and right sorted portion. I think, for each sorted portion, we can apply binary search directly. If you find target value, then return. If not find, we move left and right index respectively.

[@yoonsw12]

Excellent solution with great visualization of the graph. Really helped me understand why we need to "pivot" and decide whether to stay put on the portion we chose or pivot entirely to the other side and conitnue.

[@krypton7792]

Amazing Explanation! thank you, the handwritten stuff really helped me understand this easier.

[@priyavardhanpatel6155]

I have spent more than 2 hours on this problem but couldnt solve it. You made it very clean and simple, thank you so much!!!

[@kryddan]

I think of it like this: if mid > than R, everything left of mid is sorted if mid < than R, everything right of mid is sorted Check if target would fall into the range of the sorted part, and if so move the L or R pointer to binary search that segment. Otherwise move to the unsorted segment and repeat: def search(nums: List[int], target: int) -> int: l, r = 0, len(nums) - 1 while l

[@victoriatfarrell]

Thanks for sharing! I found your presentation of it helpful.

[@free-palestine000]

this has been one of the most solutions to wrap my head around for some reason

[@TheKapei22]

I started watching your videos for Blind 75. This was the first one I made without watching any video. Your video optimizes what I did, though. Great job!

[@algorithmimplementer415]

Extremely good explanation. LC solutions were confusing at their website, so if I had not found your post, I may not have understood the bunch of if else statements. So, thank you very much!

[@ShivangiSingh-wc3gk]

Amazing explanation, will donate when I get the job.

[@sidazhong2019]

if nums[l]

[@leeroymlg4692]

Nice one. I like this solution better

[@youngsuko8910]

This make so much sense to me! Thank you

[@tanaykamath1415]

Man idk how you manage to explain so elegantly!

[@rextlfung]

Great explanation! The visuals really helped. Somehow when I tried this problem I got stuck with "and" conditions but now it makes complete sense why it's "or"

[@JackWutang]

It's not wrong to use "and" instead of "or". Depending on what your condition is, "and" could work as well.

[@carloscarrillo201]

You can also use 'and': if target >= nums[start] and target < nums[mid]: end = mid - 1 else: start = mid + 1

[@gregp83]

nice explanation - kind of figured out myself general idea but its so easy to get confused when use "

[@shashikantdivekar7839]

Thank you Sir. Very nicely explained and useful.

[@positive.stories]

Thank you very much!! I learned a lot from this video.

[@azamatik3]

I won't stop talking, you explain so well. Thank you so much

[@jameszhou20850]

Thanks. Your explanation is very clean

[@ritikajagtiani2984]

Thanks - this is crystal clear!

[@ahmedzedan1772]

Hello, your videos are awesome! it takes me to the next level. Thank you!

[@Andrew-dd2vf]

The visualization did wonders to help me tackle this problem. I didn't even have to look at the actual implementation to solve it after looking at it!

[@hackytech7494]

Fantastic as always ❤️

[@bismeetsingh352]

This is a dope explanation.

[@finleyy]

you have the best explanation! thank you

[@amardeepsingh7528]

The explanation with graph is really helpful

[@zenyujin_]

I think using the inequality signs like this makes it a lot more intuitive: def search(self, nums, target): L, R = 0, len(nums) - 1 while L

[@maneeshreddy3825]

Best explanation!!!

[@gokulnaathb2627]

Very nicely explained

[@akhma102]

Great Explanation. Thank you!

[@mohamedantar1249]

thanks, you always have the best explanation

[@SankalpPrakashECE--]

Beautifully explained

[@marinbeslo7841]

Great explanation, thanks! :D

[@karthikr7956]

Thanks. A very good explanation.

[@ronifintech9434]

Dinner on me if I pass my Google super day with your 150 question list :-) beautiful explanations!!

[@itachid]

Did you??

[@Mulla_killer]

Did you??

[@saugatkarki3169]

Did you??

[@arno.claude]

Did you??

[@kartiksoni825]

Don't leave us hanging man!

[@OluwatosinOseni260]

i knew the methods but so many things we were testing and it tripped me off

[@zr60]

target < nums[l] and target > nums[r] make it hard to visualize. target >= nums[pivot] and target

[@james3742]

Great vid, thank you!

[@trungthucnguyen7540]

great solution! Thank you

[@ThomasCrosbie-Walsh]

I feel like this solution makes slightly more sense: left = 0 right = len(nums) - 1 while left = nums[left] and target

[@yinglll7411]

Thank you so much!

[@sergeychepurnov1328]

Awesome explanation, thanks.

[@NeetCode]

Happy it was helpful!

[@今天比昨天厲害]

You are amazing!!

[@jjayguy23]

God bless you man, you are incredible.

[@danielsun716]

What I need to say is one thing easily missing, that is nums[l] may be equal to nums[m]. for instance, [3, 1] find the target 1. then you will see what is going on. I think that is the hard edge case to find out. So just for the more clear to see the conditions, I like to write elif condition as a beginner just in case for avoiding missing any other conditions. class Solution: def search(self, nums: List[int], target: int) -> int: l, r = 0, len(nums) - 1 while l

[@mahbubulhaque3137]

Really awesome

[@seungminlee4971]

thank you finally understood

[@kafychannel]

great work thanks so much!

[@amitupadhyay6511]

Even simple explaination : If A[mid] >= A[l] , then A[l:mid+1] is increasing subarray, so explore this array only if target between A[l] and A[mid] , the other part is like dumb yard, throw all other conditions in dump IF A[mid] < A[l], then everything to left of mid is a dump yard. Use the right side of mid only if A[mid] < target

[@janvidalal476]

That Visualization Supremacy. 💯

[@ebrahimaliabadifarahani7755]

Could also find the pivot in log(n) and then have two sorted array which could be used to do simple binary search which is still log(n)

[@thecuriousprogrammer5857]

This was awesome

[@TechnoSan09]

finding pivot using binary search in O(log n) then performing another binary search O(log n) to find the key will be little easier but little time intensive but still better than O(n)

[@andreytamelo1183]

Thanks!

[@khemrajghalley3206]

well explained

[@ivanwen8335]

when you check with the leftmost value, why used "target < nums[l]", not "target < nums[0]"?

[@abhicasm9237]

because the left may not be always 0

[@ivanwen8335]

@@abhicasm9237 I tried to change it to 0, it still passed all the tests

[@nikhil_a01]

Overall a pretty good explanation but IMO there is one flaw at 8:08. Our target is 0 and we narrow our search range from [4,5,6,7,0,1,2] down to [0,1,2]. But then we say [0,1] is the 'left side' because [0,1,2] is sorted? Clearly what we care about is not left or right side, but whether our subarray is a sorted subarray or a rotated sorted subarray. The key observation is that *_when you take the mid of a rotated sorted subarray, one side will be sorted, and the other will be rotated sorted._* For example, with [4,5,6,7,0,1,2], if the mid value is 6, then we get a split of [4,5] and [7,0,1,2]. If the mid value is 1 then the split is [4,5,6,7,0] and [2]. Which of the left or right side is sorted and which is rotated sorted varies. And as a special case we can also have both sides sorted, like if the mid value is 0. I think it'll also be helpful to summarize all the cases: If we're in the sorted portion ('left side'): • If target > mid val then search right • Else target = left val then search left Else we're in the rotated sorted portion ('right side'): • If target < mid val then search left • Else target >= mid val: • If target > right val then search left (i.e. rotate around) • If target

[@BG-lj6fw]

insightful!

[@moncefabboud2839]

I found the left/right sorted portions explanation a bit hard to digest. One other of seeing things that convinced me better is as follows: if nums[l] the sub array from l to mid is sorted. else => the other sub array from mid to r is sorted. Indeed, we can only have one unsorted subarray which includes the pivot. Once we think of subarrays as sorted or unsorted, the idea is to check if target is within the sorted subarray if it is, move the left/right to mid to seach within the sorted portion. If target is outside the sorted portion. Keep searching in the unsorted portion by splitting it into a sorted and unsorted parts and repeating the process.

[@therelaxinggamer3448]

what is that software you used to explain the algorithm ?

[@user-de4lk6pk8k]

@Neetcode it must and condition and not or . Here is the correct solution : class Solution: def search(self, nums: List[int], target: int) -> int: # we can run a single loop to locate the target but that is not needed here, # we need something in O(log N) leftPt = 0 rightPt = len(nums) - 1 while leftPt nums[middlePt] and target

[@erassylzh5658]

awesome!

[@PankajKumar-mz6mp]

this was asked to me in the first round of an interview

[@whitest_kyle]

Very clear and helpful! I got a time limit exceeded warning when trying to submit though :(

[@Gerald-iz7mv]

i think there is a bug.

[@emilyhuang2759]

Python is not my strongest language. Is //2 is dividing by 2 and truncating the decimal part? TY

[@NeetCode]

Yeah that's exactly correct.

[@aumrudhlalkumartj1948]

Thanks

[@eugbyte1822]

When comparing whether the target element or mid element is in the left half or right half, why must we compare against the left element instead of comparing against the first element>, e.g . `nums[mid] > nums[left]`, but not `nums[mid[ > nums[0]`;

[@nguyentuan1990]

i found this solution to be more intuitive. This problem is exact same as the Min Rotated Sorted Array pronlem. so for the Min Rotated Sorted Array problem, the solution is like this def findMinRotatingElement(nums): left = 0 right = len(nums) - 1 ''' logic is this: do the binary search, compare the mid value with the most right value if mid is larger, meaning the min value is on the top half, update left = mid + 1 else the min value is on the bottom half, update right = mid once l = r we found the solution ''' while left < right: mid = (left + right) // 2 midValue = nums[mid] if midValue > nums[right]: left = mid + 1 elif midValue

[@maamounhajnajeeb209]

thanks

[@ax5344]

why do we need to use "while left

[@mastermind5421]

says it at 9:20

[@fishoil5310]

you use left < right when you want "eager termination", that means after while loop exited, left==right.

[@monicawang8447]

Hey! Ty for the nice solution!! When I did the Bineary search, I usually use "left = 0, right = len(nums)", and "while left < right" this template. I wonder if it's possible to modify it this way in this case? I tried myself but got index out of bound (problem with nums[right]). Does anyone know if it's possible to use [left, right) way to do it?

[@SuperOnlyP]

In python, nums = [4,2,5,1] len(nums) // output: 4 to count how many item in the list start with 1 as: 1,2,3,4 items or length is: 4 Howerver, index count from 0 not from 1 nums[0] = 1 nums[1] =2 nums[2] =5 nums[3] =2 or nums[ len(nums) -1 ] =2 first index =0 , last index= len(nums) -1 Therefore, right =len(nums) // will cause out of range

[@mostinho7]

Good explanation from 6:30 Todo:- take notes

[@longtruong3059]

I wonder why in the coding sol: if nums[m] >= nums[l] then nums[m] is in the the left sorted portion. From my finding, it should be nums[m] >= nums[0]

[@kaungkyaw5632]

Hoping that one day I can visualize problems by drawing pictures like this

[@deepakg9220]

class Solution: def search(self, nums: List[int], target: int) -> int: if target in nums: return nums.index(target) else: return -1 #sometimes my genius is almost frightening

[@vishwaskotegar5248]

who is this genius??? it works ! ... NEET!!!!!!!!!!! you need some explaining to do for spoiling us with lot of code

[@SOMESHKHANDELIA]

I was able to solve this problem without looking at the solution, only by updating my code seeing which test cases were failing. If test cases weren't visible, would not have been able to solve it. It was tricky as anything.

[@freyappari]

Faster solution, no need for a min: l, r = 0, len(nums) - 1 while l < r: m = (l + r) // 2 if nums[m] < nums[r]: r = m else: l = m + 1 return nums[l]

[@zainio]

Line 12 of your solution: Why is it

[@Terracraft321]

I think he explained it in the video, that the pointer can be the same or smaller than the middle pointer. I could be wrong though.

[@Extremesarova]

Much easier to understand solution (updated conditions): class Solution: def search(self, nums: List[int], target: int) -> int: l, r = 0, len(nums) - 1 while l

[@skyjoe3655]

this is easy to understand but hard to write running code without bugs

[@noextrasugar]

My head hurts🤯How this seemingly easy problem becomes so complex, I hate leet code mannnnnnn. TY for making it easier, I kept failing test cases because I didn't identify I needed to be looking at whether I was at left sorted or right sorted portion ugggghhhhhh

[@footballking5993]

try: return nums.index(target) except: return -1

[@cesaralcantara1341]

thats not O(log(n) like the problem states, but good easy solution if you want O(n)

[@motivewave001]

follow up would be if the array contains duplicate

[@niteshmanem1997]

This problem makes sense once I see the solution but if I had never encountered this problem before, I do not know how I would have arrived at the solution Is it expected in interviews to have new problems we haven't seen before and come up with the solution on the spot? That sounds very difficult

[@nikhil_a01]

Yes, it's completely expected to get problems you haven't seen before in interviews. Rarely you might be lucky and get a problem you've seen before, but you shouldn't expect it. A large part of why this style of interviews was introduced was to test your problem solving. This problem is on the hard side in my opinion though. It took me 45 minutes.

[@bossgd100]

@@nikhil_a01 did you practice something similar before ?

[@nikhil_a01]

​@@bossgd100 Not that similar. I'd done about a dozen binary search problems before, but not anything with rotated arrays.

[@bossgd100]

@@nikhil_a01 thank you for your answer 👍

[@kanhashukla6067]

Solution works. Explained well. But this is a very complicated solution. Below is a slightly more readable solution. Note : This is not my solution. Its borrowed. I just added a few comments. def search(self, nums, target): l = 0 r = len(nums) - 1 while l = nums[l]: # Checks if the left part is sortted or not. if nums[l]

[@rishabhsharma9719]

Can we not do this from linear search? For i in range(len(arr)): if arr[i]==target: return i return -1

[@NeetCode]

Yeah linear search works but Binary search is more efficient for large inputs.

[@vishwaskotegar5248]

kelakkaadhru naachke aagalva?? nkn

[@indhumathi5846]

understood

[@lbvenkatesh]

I had changed the if conditions this way for better understanding: if (nums[s] = nums[s] && target < nums[m]) { e = m -1; } else { s = m +1; } } else { if (target > nums[m] && target

[@user-if8oo6nm3k]

I have a question that I can't figure out, why for the left portion, nums[mid] >= nums[left], and it can't pass all the tests if I say nums[mid] > nums[left]

[@garry9702]

Coz for cases like [2,1] nums[mid] will be 2 i.e. num[left] but in your condition (nums[mid] > nums[left]) that's why it can never enter the left portion condition

[@armand6994]

this one is more eazy to understand if nums[left]

[@Aditya-ne4lk]

may i suggest tactile switches

[@fullmetalsmash001]

This is a deceptively complex problem. Normally, they say if you're writing a lot of complex nested logic, it means you're doing too much or something wrong. Turns out in this case, this problem is the exception. The solution isn't as intuitive or elegant as one would expect, but it's necessary and not too difficult. Goes to show you, any correct soluton you can achieve at first is your best answer, then you can work your way to reduce the complexity later if it's possible.