@@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.
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!
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.
Thank you for your explanation! I believe the most straightforward way to clarify this problem and the previous problem *153. Find Minimum in Rotated Sorted Array* is to recognize that in a rotated array, we always have two portions: two sorted arrays divided by a pivot. For example, consider the array [4, 5, 6, 7, 0, 1, 2]: We have two sorted portions: [4, 5, 6, 7] and [0, 1, 2]. So, whatever index you are at, there is always a sorted part. It’s easy to check if your target belongs to it. Another perspective on the same array [4, 5, 6, 7, 0, 1, 2]: If we split this array at the midpoint (6), we get two parts: [4, 5, 6] (sorted) and [7, 0, 1, 2] (unsorted). By checking the sorted part, we can determine whether the target lies in it. If not, we focus on the other part. One more example: in the array [6, 7, 0, 1, 2, 4, 5]: Splitting at the midpoint (1), we get [6, 7, 0, 1] (unsorted) and [2, 4, 5] (sorted). If the target is, for example, 3, it lies in [2, 4, 5], so we focus there. If not, we search [6, 7, 0, 1]. By following this approach, we can efficiently narrow down the search in both problems. Thanks again for the great explanation!
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.
@@dekumidoriya-qi2is Yeah I thought so too, to be honest once you find the pivot you dont even have to apply it on both sides just apply to the side where the lower bound of the array is less than the target. So this problem can be an extension to the previous problem in the LC 150 list of finding the minimum element as that approach can be used to find the pivot.
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
This solution is more intuitive for me. Its a lot easier to think about the cases where your target is in the range of the current section you are in, rather than thinking about all the cases where it falls out of range (like how neet thinks about it)
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 😅
Thanks a lot for that graph explanation. I'll never forget this fact about array rotation! You're a great teacher for going the extra mile to try and explain the reasoning behind your actions
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
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.
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"
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!
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
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.
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!
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!
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.
I had worked out this solution, but just couldn't break it down into code. The moment I saw the simple comments "left sorted portion" and "right sorted portion" it was cake. Thanks Neet
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
For those struggling with this problem I suggest working on Leetcode 153 or watch his explanation for LC 153. That problem basically gives u an idea how to do BS on rotated arrays and then solving this problem becomes easier. I personally tried solving this problem by my own , failed and then changed if statements to satisfy the test cases which were failing and finally got it to pass all cases. I then watched this vid and the approach was the same. Below is my solution - class Solution: def search(self, nums: List[int], target: int) -> int: l = 0 r = len(nums) - 1 while l
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
So, a bit late to the party, but just repeating one of the top comments. I basically found the pivot, and then based on how large the target is, search in one of the two sorted subarrays. I felt that this solution is much more intuitive than the one here. Though understanding how to find the minimum was a pain.
This is one of the easiest problems using python, this is the solution that I used: class Solution: def search(self, nums: List[int], target: int) -> int: try: return nums.index(target) except: return -1
Bruh the soln you used doesn't come under Binary Search algorithm. You're just using the index method 💀 Your interviewer might need you to solve the question using Binary Search
@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
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
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)
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.
class Solution: def search(self, nums: List[int], target: int) -> int: l, r = 0, len(nums) - 1
while l = nums[r], then that means the diverging point is in the second half if ( (target = nums[mid]) or (nums[mid] >= nums[r] and (target = nums[mid] )) ): l = mid + 1 else: r = mid - 1
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
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.
You can find the pivot using a binary search, then do another usual binary search except this time with transformed index based on the rotation. It's a O(2 * log n) solution which should be evaluate to O(log n). class Solution { public int search(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l < r) { int m = (l + r) / 2; if (nums[m] > nums[r]) { l = m + 1; } else { r = m; } } int k = l; // l, r, m are all equals l = 0; r = nums.length - 1; while (l target) { r = m - 1; } else { l = m + 1; } } return -1; } }
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
Much easier to understand solution (updated conditions): class Solution: def search(self, nums: List[int], target: int) -> int: l, r = 0, len(nums) - 1 while l
is it possible L is already in the right sorted portion? Then in this case nums[L] < nums[mid] can't be used to judge if mid is in the left sorted portion, right?
Solution works. Explained well. But this is a very complicated solution. Below is a slightly more readable solution. Note : This is not my solution. Its borrowed. I just added a few comments. def search(self, nums, target): l = 0 r = len(nums) - 1 while l = nums[l]: # Checks if the left part is sortted or not. if nums[l]
TO find the target belows what I did. First I found if list is rotated or not, If last element < first element. List is rotated an no matter what permutation you choose it will remain this way [4,5,6,7,0,1,2] If its rotated We divide the array into 2 logical sorted arrays, How. Take a pointer at last element and start finding minimum element from last pointer. IN above case 0 is minimum at index 4. So 2 lists are 0: 4 < 0 element is not included here and 4:6(len of array - 1). Now we first do Binary search on first, if not found second and then return -1 or answer. If array is not rotated at all we just apply binary search directly.
Personally, I find it more intuitive to find the index of the min value and then search the two sections of the array with ranges [0, minIdx -1] and [minIdx, end of array] var search = function(nums, target) { const minIdx = findMinIdx(nums); const bst = (lb, ub) => { let l = lb, r = ub; while(l < r) { const midIdx = l + Math.floor((r - l) / 2); if (nums[midIdx] >= target) { r = midIdx; } else { l = midIdx + 1; } } const v = nums[l] === target ? l : undefined; return v; } const left = bst(0, minIdx - 1) ; if (left !== undefined) { return left; } const right = bst(minIdx, nums.length - 1); return right !== undefined ? right : -1; }; const findMinIdx = nums => { let l = 0, r = nums.length - 1; while(l < r) { const midIdx = l + Math.floor((r - l) / 2); if (nums[midIdx] > nums[r]) { l = midIdx + 1; } else { r = midIdx; } } return l; }
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.
This is a deceptively complex problem. Normally, they say if you're writing a lot of complex nested logic, it means you're doing too much or something wrong. Turns out in this case, this problem is the exception. The solution isn't as intuitive or elegant as one would expect, but it's necessary and not too difficult. Goes to show you, any correct soluton you can achieve at first is your best answer, then you can work your way to reduce the complexity later if it's possible.
To anyone who is still confused, here's a solution which is easier to understand with comments: class Solution: def search(self, nums: List[int], target: int) -> int: l, r = 0, len(nums) - 1 while l
By his bizarre logic and relatively convoluted explanation here, he would find that your middle is NOT in the "left sorted portion" because M < L. Only if your middle is greater than your leftmost first value do you know you're "in a" contiguous portion, where "in a" is just a bad way of saying "the values from L until middle are contiguous/unsplit/don't contain the pivot". If this isn't the case you're in the "right sorted portion". Wtf is "right" about being a number in the middle? No freaking idea, it's upsetting at how illogical it is. Anyways, since that first case isn't the case in your example, we "know we're in the 'right sorted portion of the array'". Perhaps just terrible naming on his part??? Then..... by his fantastic logic at 5:03 he says "What if we know our target is less than the mid, well then we know we have to [binary] search the left portion of this array". So in short, you figure out if you're in the left or right portion. If you're in the left you check if your target is in the range. If you're in the right (again, wtf does this mean!?), you check if your target is less than the middle FIRST 😑 to make sure what you're about do isn't all fudged up (check the right). If it is... then you go "ooops" and go back to checking/using the left you were just about to throw away. Hope this helps, although it sorta doesn't since it's so stupid feeling even when you grok it.
What he's trying (and failing) to say, is that if when you're in the middle the leftmost value is not less than you, then you know that a split/pivot has occurred. If you detect that the left of middle is in split, he says that you're in "the right sorted portion", where by "right" he means ... fudge if I know honestly, it sounds stupid. He explains at 1:57 "Lets say the left side is exclusively greater than the right side, because that's what it means by rotating the array" So he's just defining left and right in what is I think mostly WRONG and arbitrary logic to where "in the left side" means THE PART AFTER THE SPLIT POINT (OF LARGER NUMBERS) (which was actually the freaking right side of the number line before the split). Left and right to him don't even have anything to do with left and right of center even though this whole thing revolves around a center number. He even erroneously says at exactly 1:49 "We took some pivot and then swap these halves around". *THEY ARE NOT HALVES*. WE'RE LITERALLY IN A PROBLEM ABOUT HALVES AND MIDDLES AND HE'S MISUSING THE WORD HALF TO NOT MEAN LITERALLY HALF. They're just parts because the split isn't always in the middle!!! This flawed and erroneous description is the entire basis of him calling everything left and right side; the entire explanation to everything and grokking his solution. At 2:42 he erroneously misuses the term halves again! 🤦♂ So in your example he defines your middle number as "not being in the left side" because it's a part of the numbers that were to the left of the split/pivot position and to him the arbitrary so-called "LEFT FREAKING SIDE" just means the side on the left that begins at a split (and higher), even if left of the middle contains numbers from the other side of the split (like the 0, and 1 in your example). So for reasons that make little sense to me the number 2 is not "in the left side" (because he's not talking left of middle) and he becomes inclined to use (binary search) the right side... unless oops your target is less than the middle. It just feels like a bizarre and broken way of thinking about it all... I'll have to consider it further.
class Solution { public: int search(vector& nums, int target) { int size = nums.size(); if (size == 0) { return -1; } // Handle the case where size == 1 if (size == 1) { return (nums[0] == target) ? 0 : -1; } int res = -1; int l = 0; int r = size - 1; while (l nums[l] && nums[mid] > nums[r]) { if (target >= nums[l] && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } else { // Prevent r from becoming negative if (r > 0) { r = r - 1; } else { break; // Exit if r is already 0 } } } return res; } };
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Search in Rotated Sorted Array II - ruclips.net/video/oUnF7o88_Xc/видео.html
This is lowkey one of the hardest problems I've done so far. Great video!
I watched this video for 3 times to understand the solution, so yeah ur right.
You can use binary search to find the pivot index, and then another binary search in the appropriate part of the array.
This is a really good idea, less confusing
How?
@@wonderfulsnow you responded to a year old comment, damn!
@@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.
@@wonderfulsnow good explanation!!
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!
so me!
Can't relate more
Same, you should have that KDB vision !
So amazing, Kevin DeBruyne doing Leetcode just for fun when he makes millions playing soccer
I like how you can talk now!
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.
Thank you for your explanation! I believe the most straightforward way to clarify this problem and the previous problem *153. Find Minimum in Rotated Sorted Array* is to recognize that in a rotated array, we always have two portions: two sorted arrays divided by a pivot.
For example, consider the array [4, 5, 6, 7, 0, 1, 2]:
We have two sorted portions: [4, 5, 6, 7] and [0, 1, 2].
So, whatever index you are at, there is always a sorted part. It’s easy to check if your target belongs to it.
Another perspective on the same array [4, 5, 6, 7, 0, 1, 2]:
If we split this array at the midpoint (6), we get two parts: [4, 5, 6] (sorted) and [7, 0, 1, 2] (unsorted).
By checking the sorted part, we can determine whether the target lies in it. If not, we focus on the other part.
One more example: in the array [6, 7, 0, 1, 2, 4, 5]:
Splitting at the midpoint (1), we get [6, 7, 0, 1] (unsorted) and [2, 4, 5] (sorted).
If the target is, for example, 3, it lies in [2, 4, 5], so we focus there. If not, we search [6, 7, 0, 1].
By following this approach, we can efficiently narrow down the search in both problems. Thanks again for the great explanation!
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.
yes. Seriously, what is the point of this kind of problem?
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
a simple or rather more intuitive approach is to find the pivot and then apply binary search on (0, pivot-1) and (pivot, n)
@@dekumidoriya-qi2is Yeah I thought so too, to be honest once you find the pivot you dont even have to apply it on both sides just apply to the side where the lower bound of the array is less than the target.
So this problem can be an extension to the previous problem in the LC 150 list of finding the minimum element as that approach can be used to find the pivot.
@@AsliArtist Yep i missed that nice catch once we know the pivot we can actually check only one side which is relevant !!
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
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
I found your explanation very helpful.
As @allnewdevelopers mentioned, I was also confused about the OR.
Thank you for your contribution!
good ol' demorgan's law. thanks!
This is the easiest version, Glad I saw your comment 🙂
This solution is more intuitive for me. Its a lot easier to think about the cases where your target is in the range of the current section you are in, rather than thinking about all the cases where it falls out of range (like how neet thinks about it)
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 😅
For me this solution was a bit more intuitive:
l = 0
r = len(nums) - 1
while l = nums[l]:
if nums[l]
I agree. This one reads better.
Hey.. Even I came up wid same solution
Agreed, able to reason this solution much more easily
Thanks for sharing this.(really easy to understand)
This is much easier to read
Thanks a lot for that graph explanation. I'll never forget this fact about array rotation!
You're a great teacher for going the extra mile to try and explain the reasoning behind your actions
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
Thanks for sharing! I found your presentation of it helpful.
if nums[l]
Nice one. I like this solution better
This make so much sense to me! Thank you
Thank you bro...made more sense to me now
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.
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
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"
It's not wrong to use "and" instead of "or". Depending on what your condition is, "and" could work as well.
You can also use 'and':
if target >= nums[start] and target < nums[mid]:
end = mid - 1
else:
start = mid + 1
Amazing explanation, will donate when I get the job.
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!!!
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!
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
this has been one of the most solutions to wrap my head around for some reason
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.
for the comparison i did this
if (M > L and L
i had something similar, makes the if statement a bit convoluted but is overall a much more cleaner solution to my eyes
@@johnyha9236 Great minds think alike brother if the solution is clear on paper then the code is clear
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!
nice explanation - kind of figured out myself general idea but its so easy to get confused when use "
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!
Man idk how you manage to explain so elegantly!
I won't stop talking, you explain so well. Thank you so much
Amazing Explanation! thank you, the handwritten stuff really helped me understand this easier.
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.
This was a great explanation, the best of several that I watched. Thank you!
array problems make me feel like i have IQ below 80
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!
I had worked out this solution, but just couldn't break it down into code. The moment I saw the simple comments "left sorted portion" and "right sorted portion" it was cake. Thanks Neet
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
insightful!
Dinner on me if I pass my Google super day with your 150 question list :-)
beautiful explanations!!
Did you??
Did you??
Did you??
Did you??
Don't leave us hanging man!
thanks, you always have the best explanation
The explanation with graph is really helpful
I feel like this solution makes slightly more sense:
left = 0
right = len(nums) - 1
while left = nums[left] and target
For those struggling with this problem I suggest working on Leetcode 153 or watch his explanation for LC 153.
That problem basically gives u an idea how to do BS on rotated arrays and then solving this problem becomes easier.
I personally tried solving this problem by my own , failed and then changed if statements to satisfy the test cases which were failing and finally got it to pass all cases. I then watched this vid and the approach was the same. Below is my solution -
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums) - 1
while l
Thanks. Your explanation is very clean
Thanks!
class Solution:
def search(self, nums: List[int], target: int) -> int:
if target in nums:
return nums.index(target)
else:
return -1
#sometimes my genius is almost frightening
who is this genius??? it works ! ... NEET!!!!!!!!!!! you need some explaining to do for spoiling us with lot of code
Thanks for such an easy explanation 👏🏻
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
Thank you very much!! I learned a lot from this video.
So, a bit late to the party, but just repeating one of the top comments. I basically found the pivot, and then based on how large the target is, search in one of the two sorted subarrays.
I felt that this solution is much more intuitive than the one here. Though understanding how to find the minimum was a pain.
Thank you Sir. Very nicely explained and useful.
i knew the methods but so many things we were testing and it tripped me off
This is one of the easiest problems using python, this is the solution that I used:
class Solution:
def search(self, nums: List[int], target: int) -> int:
try:
return nums.index(target)
except:
return -1
Bruh the soln you used doesn't come under Binary Search algorithm. You're just using the index method 💀
Your interviewer might need you to solve the question using Binary Search
lmao
Best explanation!!!
@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
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
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)
Thanks - this is crystal clear!
Hello, your videos are awesome! it takes me to the next level. Thank you!
God bless you man, you are incredible.
This is a dope explanation.
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.
Fantastic as always ❤️
Good explanation from 6:30
Todo:- take notes
Beautifully explained
Great Explanation. Thank you!
when you check with the leftmost value, why used "target < nums[l]", not "target < nums[0]"?
because the left may not be always 0
@@abhicasm9237 I tried to change it to 0, it still passed all the tests
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)
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l = nums[r], then that means the diverging point is in the second half
if ( (target = nums[mid]) or (nums[mid] >= nums[r] and (target = nums[mid] )) ):
l = mid + 1
else:
r = mid - 1
return -1
Thanks. A very good explanation.
That Visualization Supremacy. 💯
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
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.
@@nikhil_a01 did you practice something similar before ?
@@bossgd100 Not that similar. I'd done about a dozen binary search problems before, but not anything with rotated arrays.
@@nikhil_a01 thank you for your answer 👍
You can find the pivot using a binary search, then do another usual binary search except this time with transformed index based on the rotation. It's a O(2 * log n) solution which should be evaluate to O(log n).
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int m = (l + r) / 2;
if (nums[m] > nums[r]) {
l = m + 1;
} else {
r = m;
}
}
int k = l; // l, r, m are all equals
l = 0;
r = nums.length - 1;
while (l target) {
r = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
}
you have the best explanation! thank you
it's such a motivating problem for a newbie in algorithms 😅
for me if target in nums:
return nums.index(target)
else:
return -1 this is what i understand
Awesome explanation, thanks.
Happy it was helpful!
This statement being true doesn't mean you are on the left part: "nums[L]
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
try:
return nums.index(target)
except:
return -1
thats not O(log(n) like the problem states, but good easy solution if you want O(n)
follow up would be if the array contains duplicate
Much easier to understand solution (updated conditions):
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l
You are amazing!!
great work thanks so much!
great solution! Thank you
I have a 5 word one line , 100% beat solution:
return Array.IndexOf(nums, target);
EASY.
Very nicely explained
is it possible L is already in the right sorted portion? Then in this case nums[L] < nums[mid] can't be used to judge if mid is in the left sorted portion, right?
Faster solution, no need for a min:
l, r = 0, len(nums) - 1
while l < r:
m = (l + r) // 2
if nums[m] < nums[r]:
r = m
else:
l = m + 1
return nums[l]
Solution works. Explained well. But this is a very complicated solution. Below is a slightly more readable solution.
Note : This is not my solution. Its borrowed. I just added a few comments.
def search(self, nums, target):
l = 0
r = len(nums) - 1
while l = nums[l]: # Checks if the left part is sortted or not.
if nums[l]
Line 12 of your solution: Why is it
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.
this one is more eazy to understand
if nums[left]
Very clear and helpful!
I got a time limit exceeded warning when trying to submit though :(
i think there is a bug.
Thank you so much!
TO find the target belows what I did.
First I found if list is rotated or not, If last element < first element. List is rotated an no matter what permutation you choose it will remain this way
[4,5,6,7,0,1,2]
If its rotated We divide the array into 2 logical sorted arrays, How.
Take a pointer at last element and start finding minimum element from last pointer. IN above case 0 is minimum at index 4.
So 2 lists are 0: 4 < 0 element is not included here and 4:6(len of array - 1).
Now we first do Binary search on first, if not found second and then return -1 or answer.
If array is not rotated at all we just apply binary search directly.
Personally, I find it more intuitive to find the index of the min value and then search the two sections of the array with ranges [0, minIdx -1] and [minIdx, end of array]
var search = function(nums, target) {
const minIdx = findMinIdx(nums);
const bst = (lb, ub) => {
let l = lb, r = ub;
while(l < r) {
const midIdx = l + Math.floor((r - l) / 2);
if (nums[midIdx] >= target) {
r = midIdx;
} else {
l = midIdx + 1;
}
}
const v = nums[l] === target ? l : undefined;
return v;
}
const left = bst(0, minIdx - 1) ;
if (left !== undefined) {
return left;
}
const right = bst(minIdx, nums.length - 1);
return right !== undefined ? right : -1;
};
const findMinIdx = nums => {
let l = 0, r = nums.length - 1;
while(l < r) {
const midIdx = l + Math.floor((r - l) / 2);
if (nums[midIdx] > nums[r]) {
l = midIdx + 1;
} else {
r = midIdx;
}
}
return l;
}
Thank you very much
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.
Great vid, thank you!
This is a deceptively complex problem. Normally, they say if you're writing a lot of complex nested logic, it means you're doing too much or something wrong.
Turns out in this case, this problem is the exception. The solution isn't as intuitive or elegant as one would expect, but it's necessary and not too difficult.
Goes to show you, any correct soluton you can achieve at first is your best answer, then you can work your way to reduce the complexity later if it's possible.
To anyone who is still confused, here's a solution which is easier to understand with comments:
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l
for this case, how do you know which way to go?
[8,9,0,1,|2|,3,4,5,6,7], target = 1
This is a great question and captures the confusion of the problem
By his bizarre logic and relatively convoluted explanation here, he would find that your middle is NOT in the "left sorted portion" because M < L. Only if your middle is greater than your leftmost first value do you know you're "in a" contiguous portion, where "in a" is just a bad way of saying "the values from L until middle are contiguous/unsplit/don't contain the pivot". If this isn't the case you're in the "right sorted portion". Wtf is "right" about being a number in the middle? No freaking idea, it's upsetting at how illogical it is.
Anyways, since that first case isn't the case in your example, we "know we're in the 'right sorted portion of the array'". Perhaps just terrible naming on his part??? Then..... by his fantastic logic at 5:03 he says "What if we know our target is less than the mid, well then we know we have to [binary] search the left portion of this array".
So in short, you figure out if you're in the left or right portion. If you're in the left you check if your target is in the range. If you're in the right (again, wtf does this mean!?), you check if your target is less than the middle FIRST 😑 to make sure what you're about do isn't all fudged up (check the right). If it is... then you go "ooops" and go back to checking/using the left you were just about to throw away.
Hope this helps, although it sorta doesn't since it's so stupid feeling even when you grok it.
What he's trying (and failing) to say, is that if when you're in the middle the leftmost value is not less than you, then you know that a split/pivot has occurred. If you detect that the left of middle is in split, he says that you're in "the right sorted portion", where by "right" he means ... fudge if I know honestly, it sounds stupid.
He explains at 1:57 "Lets say the left side is exclusively greater than the right side, because that's what it means by rotating the array"
So he's just defining left and right in what is I think mostly WRONG and arbitrary logic to where "in the left side" means THE PART AFTER THE SPLIT POINT (OF LARGER NUMBERS) (which was actually the freaking right side of the number line before the split).
Left and right to him don't even have anything to do with left and right of center even though this whole thing revolves around a center number.
He even erroneously says at exactly 1:49 "We took some pivot and then swap these halves around". *THEY ARE NOT HALVES*. WE'RE LITERALLY IN A PROBLEM ABOUT HALVES AND MIDDLES AND HE'S MISUSING THE WORD HALF TO NOT MEAN LITERALLY HALF. They're just parts because the split isn't always in the middle!!! This flawed and erroneous description is the entire basis of him calling everything left and right side; the entire explanation to everything and grokking his solution. At 2:42 he erroneously misuses the term halves again! 🤦♂
So in your example he defines your middle number as "not being in the left side" because it's a part of the numbers that were to the left of the split/pivot position and to him the arbitrary so-called "LEFT FREAKING SIDE" just means the side on the left that begins at a split (and higher), even if left of the middle contains numbers from the other side of the split (like the 0, and 1 in your example). So for reasons that make little sense to me the number 2 is not "in the left side" (because he's not talking left of middle) and he becomes inclined to use (binary search) the right side... unless oops your target is less than the middle. It just feels like a bizarre and broken way of thinking about it all... I'll have to consider it further.
thank you finally understood
class Solution {
public:
int search(vector& nums, int target) {
int size = nums.size();
if (size == 0) {
return -1;
}
// Handle the case where size == 1
if (size == 1) {
return (nums[0] == target) ? 0 : -1;
}
int res = -1;
int l = 0;
int r = size - 1;
while (l nums[l] && nums[mid] > nums[r]) {
if (target >= nums[l] && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
// Prevent r from becoming negative
if (r > 0) {
r = r - 1;
} else {
break; // Exit if r is already 0
}
}
}
return res;
}
};
well explained