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.

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

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

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

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

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

[@legspinismylife]

array problems make me feel like i have IQ below 80

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

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

[@krypton7792]

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

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

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

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

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

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

[@positive.stories]

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

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

[@shashikantdivekar7839]

Thank you Sir. Very nicely explained and useful.

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

[@jameszhou20850]

Thanks. Your explanation is very clean

[@gregp83]

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

[@ShivangiSingh-wc3gk]

Amazing explanation, will donate when I get the job.

[@ritikajagtiani2984]

Thanks - this is crystal clear!

[@ahmedzedan1772]

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

[@tanaykamath1415]

Man idk how you manage to explain so elegantly!

[@finleyy]

you have the best explanation! thank you

[@hackytech7494]

Fantastic as always ❤️

[@sidazhong2019]

if nums[l]

[@leeroymlg4692]

Nice one. I like this solution better

[@youngsuko8910]

This make so much sense to me! Thank you

[@azamatik3]

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

[@bismeetsingh352]

This is a dope explanation.

[@amardeepsingh7528]

The explanation with graph is really helpful

[@gokulnaathb2627]

Very nicely explained

[@maneeshreddy3825]

Best explanation!!!

[@akhma102]

Great Explanation. Thank you!

[@marinbeslo7841]

Great explanation, thanks! :D

[@sergeychepurnov1328]

Awesome explanation, thanks.

[@NeetCode]

Happy it was helpful!

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

[@SankalpPrakashECE--]

Beautifully explained

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

[@karthikr7956]

Thanks. A very good explanation.

[@今天比昨天厲害]

You are amazing!!

[@mohamedantar1249]

thanks, you always have the best explanation

[@james3742]

Great vid, thank you!

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

[@yinglll7411]

Thank you so much!

[@trungthucnguyen7540]

great solution! Thank you

[@OluwatosinOseni260]

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

[@jjayguy23]

God bless you man, you are incredible.

[@kafychannel]

great work thanks so much!

[@ThomasCrosbie-Walsh]

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

[@seungminlee4971]

thank you finally understood

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

[@mahbubulhaque3137]

Really awesome

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

[@thecuriousprogrammer5857]

This was awesome

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

[@andreytamelo1183]

Thanks!

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

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

[@zr60]

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

[@khemrajghalley3206]

well explained

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

[@janvidalal476]

That Visualization Supremacy. 💯

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

[@therelaxinggamer3448]

what is that software you used to explain the algorithm ?

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

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

[@PankajKumar-mz6mp]

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

[@aumrudhlalkumartj1948]

Thanks

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

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

[@Aditya-ne4lk]

may i suggest tactile switches

[@erassylzh5658]

awesome!

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

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

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

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

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

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

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

[@wilson4987]

could you explain why mid + 1 or mid -1?

[@wilson4987]

ah I got it. it's cuz you already took care of the if target == nums[mid] case

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

[@kaungkyaw5632]

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

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

[@skyjoe3655]

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

[@mostinho7]

Good explanation from 6:30 Todo:- take notes

[@arekceg]

I'm wondering - why can't we just use a regular Binary Search over the whole array? Would that also not be O(log n)?

[@NeetCode]

Since the entire array is not actually sorted

[@arekceg]

@@NeetCode ahh, silly me, of course! thanks : )

[@abhicasm9237]

can this problem solved using merge sort??

[@nikhil_a01]

No, the problem asks for an O(log N) solution. General merge sort is O(N log N) time. Even if you take advantage of the fact that the two sides are already sorted, it's still O(N) time to do a merge, and you have to find the boundary between the two sides as well. Besides, if you were going to do an O(N) solution, you would just do a linear search on the array. In Python that's a one-liner: `return target in nums`.

[@malakggh]

but when we use len(nums) isn't that already O(n)??

[@praneethnellutla]

can i write code for this problem like this if target in nums: return nums.index(target) else: return -1 what is the time complexity of this code

[@SIAMEInekeidijdnen]

O(n)

[@SIAMEInekeidijdnen]

Yes you can, but that wont be the post optimal solution the problem is actually after. The problem want a solution that runs in O(log(n))

[@indhumathi5846]

understood

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

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

[@VAIBHAVKAPILBCE]

How can you just Search Left and right Portions when the Array is Not even Sorted Anymore.

[@juanmoscoso0]

because each section is still sorted

[@armand6994]

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