Search in Rotated Sorted Array II - Leetcode 81 - Python

Solving leetcode 81, Search in Rotated Sorted Array II, today's dailly leetcode problem on august 9.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/search-...
0:00 - Read the problem
2:02 - Calculating halfway
3:12 - Drawing Explanation
13:57 - Coding Explanation
leetcode 81
#neetcode #leetcode #python

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

[@SASA_maxillo]

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

[@metarus208]

glad to having you post regularly again.

[@carsonfreeman6955]

These explanations are amazing!

[@rhugvedbhojane4387]

Good to see you back buddy.

[@michelle_tsai_drums]

Thorough explanation as always!

[@MP-ny3ep]

Great explanation as always . Thank you

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

[@uptwist2260]

Thanks for the daily

[@josepadilla4024]

He sounded so mad at this problem haha

[@uttamkumarreddygaggenapall2070]

Thank You

[@Scarsofevil]

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

[@panmacabre9895]

thank you daddy

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

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

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

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

[@aaditya_87]

2:08 which day? which problem

[@SASA_maxillo]

why not just doing: return target in nums EASYYYYYYYYY

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

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

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

[@ashokbabug40]

Worst explanation