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.

0:00 - Read the problem
2:02 - Calculating halfway
3:12 - Drawing Explanation
13:57 - Coding Explanation

leetcode 81

#neetcode #leetcode #python

[SASA_maxillo]

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

[aadil]

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.

[metarus]

glad to having you post regularly again.

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

[josepadilla]

He sounded so mad at this problem haha

[Scarsofevil]

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

[bitlandsaga]

Thanks for such a lovely explanation ❤

[floatingpoint]

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

[MP-nyep]

Great explanation as always . Thank you

[anuragnandan]

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?

[flp]

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

[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 <= rp:
mp = (lp + rp) // 2
if nums[mp] == target:
return True
elif nums[mp] > nums[rp] or nums[mp] > nums[lp]: # left sorted portion
if nums[lp] <= target < nums[mp]:
rp = mp - 1
else:
lp = mp + 1
elif nums[mp] < nums[lp] or nums[mp] < nums[rp]: # right sorted portion
if nums[mp] < target <= nums[rp]:
lp = mp + 1
else:
rp = mp - 1
else: # equal
rp -= 1
return False
```

[lesterdelacruz]

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.

[flamendless]

Would "target in numbers" in Python work?

[ievgen]

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?

[SASA_maxillo]

why not just doing:

return target in nums

[aniruddhachaki]

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.

[sumitsharma]

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