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.
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
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.
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?
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?
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.
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
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]
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.
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--
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.
POV: *you are struggling on a leetcode problem*
then you found neetcode have solve it
the BEST feeling ever
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
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.
glad to having you post regularly again.
These explanations are amazing!
Good to see you back buddy.
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?
He sounded so mad at this problem haha
If this problem worstcase senario is o(n). Can't we just integrate through the array and return True in the worstcase scenario?
You are a great teacher. I only watched your explanation once and managed to code it all by myself in the first try.
Thorough explanation as always!
thank you daddy
Thanks for the daily
Great explanation as always . Thank you
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?
Why not move both left and right pointers?
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.
the question mentions to decrease the overall operation steps. how does this algo do that?
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
@@polycrylate got it, thanks
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]
On #equal you should move both lp and rp
Would "target in numbers" in Python work?
That is basically a linear scan, it may get accepted but i think it's not the intended solution.
Thank You
why not just doing:
return target in nums
EASYYYYYYYYY
2:08 which day? which problem
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.
sorting would take O(nlogn)
@@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
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--
Worst explanation