Search in Rotated Sorted Array II - Leetcode 81 - Python

[@SASA_maxillo]

POV: *you are struggling on a leetcode problem* then you found neetcode have solve it the BEST feeling ever

[@aadil4236]

I feel much safer doing daily leetcode challenges by your return. Thank you! Suggestion: We would love to see explanations of weekly contest as well. After it ends of course.

[@polycrylate]

A small improvement: If nums[l] == nums[m] and nums[l] != nums[r] It's guaranteed that the pivot is right of middle i.e. you are on the higher/right part of array Because if the pivot is on the left of middle, it means that middle -> right must all be the same number that loops back to the left, however as middle != right (as left != right and left == middle) this isn't the case So only l += 1 in the case of nums[m] == nums[l] and nums[l] == nums[r], and extend the other case to be

[@sumitraj6878]

in the case of nums[m] == nums[l] and nums[l] == nums[r] why only l++, do e- - as well. more efficient.. eliminate the same start and end elements because they aint our target. this will help shorten up the search space.

[@flp508]

You are a great teacher. I only watched your explanation once and managed to code it all by myself in the first try.

[@metarus208]

glad to having you post regularly again.

[@carsonfreeman6955]

These explanations are amazing!

[@Scarsofevil]

If this problem worstcase senario is o(n). Can't we just integrate through the array and return True in the worstcase scenario?

[@anuragnandan6155]

In your explanation of [2,2,2,2,3,1], if nums[l] == nums[m] wouldn’t that mean everything between l and m is equal and since our target was not at nums[m], instead of l+=1 we can do l=m+1 ? Am I missing something?

[@josepadilla4024]

He sounded so mad at this problem haha

[@lesterdelacruz5088]

Not the best problem. Because eliminating left pointer 1 by 1 in the worst case would still be O(n) so it doesn't improve anything if you simply just linearly search.

[@panmacabre9895]

thank you daddy

[@peskovdev]

sometimes you can understand is that left or right portion not only by left & mid pointers, but also by mid & right pointers, so you will omit some linear operations. Here is the code: ``` class Solution: def search(self, nums: List[int], target: int) -> bool: lp, rp = 0, len(nums) - 1 while lp nums[rp] or nums[mp] > nums[lp]: # left sorted portion if nums[lp]

[@MrLeyt1125]

On #equal you should move both lp and rp

[@rhugvedbhojane4387]

Good to see you back buddy.

[@aaditya_87]

2:08 which day? which problem

[@michelle_tsai_drums]

Thorough explanation as always!

[@uptwist2260]

Thanks for the daily

[@ievgen6209]

imo, a little bit overcomplicated... the only case we need to handle in N time - skip duplicates if nums[0] == nums[-1] otherwise it is original solution: l = 0 while l < (len(nums) - 1) and nums[l] == nums[-1]: l += 1 # Code for Search in Rotated Sorted Array I problem Beats 86.73% of users with Python3 right or I'm missing something?

[@MrLeyt1125]

Why not move both left and right pointers?

[@floatingpoint7629]

the question mentions to decrease the overall operation steps. how does this algo do that?

[@polycrylate]

It doesn't force a linear search, it always tries to do a binary until it's stuck and removes elements 1 by 1 until it can again What they meant by that line I think is even tho worst case is O(n) they wanted a better AVG case

[@floatingpoint7629]

@@polycrylate got it, thanks

[@flamendless]

Would "target in numbers" in Python work?

[@NeetCodeIO]

That is basically a linear scan, it may get accepted but i think it's not the intended solution.

[@MP-ny3ep]

Great explanation as always . Thank you

[@uttamkumarreddygaggenapall2504]

Thank You

[@aniruddhachaki7165]

Wouldn't it be easier if we just sort the input first and then apply traditional Binary Search? in this problem, we don't need the target's index anyway. It works in this case where we just need to enter true or false.

[@panmacabre9895]

sorting would take O(nlogn)

[@aniruddhachaki7165]

@@panmacabre9895 Yeah. That might be the issue. So, the above solution is the best, if we have to return index, we can with just do a small change

[@sumitsharma6738]

the only catch in this problem is when you don't know which part is sorted so you just compare mid value with s and e and if (s and mid) are equal then s++ or if (mid or e) are equal then e--

[@SASA_maxillo]

why not just doing: return target in nums EASYYYYYYYYY

[@ashokbabug40]

Worst explanation