Guys don't freak out, questions like this you have to look up the solution, would someone be able to guess this approach without ever seen a problem similar to this one? Probably not, it doesn't mean you're not smart or that you suck at this. Most people saw the solution if the problem was somewhat hard at least.
I came to this video thinking that I am dumb for not knowing the solution even though I know how to search in a regular sorted list... Thanks for boosting my spirits!!!
@@alexcuenca yes m8 it is lmao don't take my comment seriously, to all the beginners leetcode is tough for the first few months for everyone, even the pros have to go through the grind
Why not set right to start -1 instead of start? It seems weird says you array is [3, 4, 0, 1, 2] and target is 4. For the binary search left = 0 index and right = 2, but ideally right should be 1 I think. Does this make sense? :)
We can also use the fact that either (Left -> MID) or (MID -> Right) will always be sorted. If the target is not present in the sorted half, limit your search to the other half. static int shiftedArrSearch(int[] A, int num) { int l = 0, r = A.length -1; while(l
Right on for explaining it, I knew I had to use the technique from LC 153, but I kept messing up on determining the search space before performing regular binary search.
Hi Gilberto. were you not able to solve the question at all? or just not optimally, using binary search?. I had the same question today. I was able to solve it O(n). But interviewer asked if I could do better, and I mentioned binary search but didnt know how to implement it. thank you
@@thugsmf Did you pass the interview? I could implement it in O(N), and design an O(logN) solution with 2 modified binary searches, but it's hard to implement it the first time without errors.
@@EE12345 nah. I didnt pass the interview. I just implemented it in O(n). Didnt bother designing the O(logn) solution. just basically told interviewer I didnt want to risk not getting the solution so just did it linear time. guess it was way too easy and too naive! but it was my first interview. so learned a lot. always give most optimal solution. hows job search for you? still struggling here
Is the Pivot Element always going to be the smallest value element? I don't see that in the question, why can we assume the smallest number is always on the side that has the pivot?
Yes in a sorted then rotated array, Pivot element has a unique property in which elements towards its left and right will always be greater. The index of this pivot ele(Smallest element) gives the number of times the array which was sorted has been rotated. Hope I cleared you're doubt!
Great tutorial Nick, but... there's an edge corner case here where if the smallest number in the array is == target and at the same time is the value at the midpoint index, the search will return -1 even thou the target value exists in the array. To solve that little problem you should check in the first while loop after finding the midpoint if the array[midpoint] == target and return midpoint from there. Hope that helps , let me know
Correct me please. In line 21, the condition is target >= nums[start]... which will always be TRUE since our nums[start] is the minimum number in the array, right? so the if statement could be only the second part: target
Well another point is that when left is, for example, 5 and right is 10 where is the middle point? Sure on 7. And what happens if you do "right/2"? Your midpoint would become equals to left
HI! Thanks for sharing your knowledge every time, it's really help me, can you also teach us how to look at the time complexity when we finished the program ?
I wonder if it's necessary to find the midpoint? I was trying to solve this without the first step. It seems doable, but every time I try my solution, it finds some edge cases where it does not work.
@Nick White: Proposed modification: =============================== You can already check if you found the looked up value, skip binary tree redundant processing =============================== if (target == array[start]) { return start; } else if (target == array[right]) { return right; } =============================== else if (target > array[start] && target < array[right]) { left = start; } else { right = start; }
1st while loop will just find smallest element. So in 1st while loop, when left == right (i.e., loop breaks) left will be same as right which will be same as smallest (or pivot) element. 2nd one is a good old simple binary search hence left
Hey nick I keep trying to find your leetcode solutions on GITHUB but I don't really know where the are . Could you let me know which repo do they belong to ?
I'm a beginner programmer, but in python couldnt you do "nums.sort()" which would sort the array, then run a binary search on it? I understand that you're doing java and that I may be completely wrong
@@richardliu5297 Thanks Richard, I don't know how time complexities work at all atm. I'm trying to do the problems without taking time complexities in mind (as stupid as that sounds). I'm also practicing on hackerrank and edabit, to make it easier 😅
What if the array is rotated n (length of array) times such that the rotated array is same as initial array then the smallest element would be the first element?I think this approach would fail....It would be better to check for rotation such that first element is always greater than the last element in the rotated array.... Am i making sense?
I don't know if I am stupid or.... lol nice one. Wish I could have come up with this on my own rather than trying some weird lengthy bunch of if statements
[4,5,6,7,0,1,2] 3 This code does an infinite loop for the above input. Just adding the following two lines will resolve the issue: if(nums[0]==target) return 0; if(nums[n-1]==target) return n-1;
Hey Nick, great video. On line 35, you set right = mid - 1; Given that right may in fact be the target, shouldn't it be right = mid? You even say yourself , "Target is less than nums of midpoint or equal to..." , actually as I typed this I answered my own question. This could not be the case since you proactively check if nums[midpoint] == target. In the previous binary search, this would not work since we do not know the target.
I was asked this question in Snapdeal interview. But your solution have too many loops. I think we can just modify the basic binary search to eliminate a part of the array without caring for where min element is or then further dividing by that min element.
While your solution is obviously ok. In the real world, I would say this function is too big. I would split it into smaller functions. Is this taken into consideration during these types of coding tests (during an interview) ?
Because he has practiced this solution like 3-4 times before doing this video(check his submissions) No one is perfect! Don’t give up, and keep practicing! :)
Is this a even a Medium difficulty question ??? I mean you just need to find the value and return it's index. Still not understanding why leetcode has set the difficulty to Medium. class Solution: def search(self, nums: List[int], target: int) -> int: for e in range(len(nums)): if nums[e] == target: return e else: return -1 My solution...
dude you must be kidding? If you come up with this solution in an interview, then the interviewer will not even ask you the next question. And leetcode accepted your solution because all the test cases will run successfully but in the question, it is clearly mentioned that the solution must be in O(log n).
This test case does not meet the requirement of being a sorted array which has been rotated around a pivot. Binary search only works for sorted arrays, so we must have an array that is sorted. In this problem we have an array which has been unsorted about a pivot. Sorted, your array would be [2,3,4,7,8], if we rotate that about a pivot, we might get [7,8,2,3,4] as an example. but we could not just switch the 7 and the 8. I hope this helps
Guys don't freak out, questions like this you have to look up the solution, would someone be able to guess this approach without ever seen a problem similar to this one? Probably not, it doesn't mean you're not smart or that you suck at this. Most people saw the solution if the problem was somewhat hard at least.
I came to this video thinking that I am dumb for not knowing the solution even though I know how to search in a regular sorted list... Thanks for boosting my spirits!!!
exactly, it just boils down to lots of practice
whatever helps you sleep at night
@@aryankumar87771 is this a joke? Lol
@@alexcuenca yes m8 it is lmao don't take my comment seriously, to all the beginners leetcode is tough for the first few months for everyone, even the pros have to go through the grind
You are such a legend at young age. Your explanation is much more clearer than leetcode. I hope to see your name on some big thing in the future.
That didn't age well😢
Why not set right to start -1 instead of start?
It seems weird says you array is [3, 4, 0, 1, 2] and target is 4. For the binary search left = 0 index and right = 2, but ideally right should be 1 I think.
Does this make sense? :)
i thought the same thing right should be start-1 and it actually runs faster in leetcode compared to right=start.
@@SangharshSeth yes, and when it is right = start, shouldnt it give an error since we are doing binary search on an unsorted array
You're right, I noticed that too.
I was about to comment this.
How did you decide the first loop condition is (left < right), and the second loop condition is (left
because you will always find the smallest element in the list, you may not always find the point they are looking for
@@duniecool Thank you so much for this explanation. So simple but I was wondering this too.
We can also use the fact that either (Left -> MID) or (MID -> Right) will always be sorted.
If the target is not present in the sorted half, limit your search to the other half.
static int shiftedArrSearch(int[] A, int num) {
int l = 0, r = A.length -1;
while(l
this question was so fucking hard almost made me quit coding.
Right on for explaining it, I knew I had to use the technique from LC 153, but I kept messing up on determining the search space before performing regular binary search.
Bro, you're next level cool guy. Any leetcode question I'm stuck on I hope there'll be a youtube video from your end. Sometimes, hard luck :(
Try being less dumb, maybe this helps
@@dj_b1627 Bob the Builder
You've got some of the best content out there bro; thank you for all the work you put into these!!
he is just not good at explaining... may be because he sneaked the answerss from somewhere.. over confidence is not good when you're teaching man
Oracle asked me this question in an interview and i failed badly lol. With this explanation i look back and can't believe how stupid i was..
You are not stupid. This question is not THAT easy to solve, if you are not really into Leetcoding.
Hi Gilberto. were you not able to solve the question at all? or just not optimally, using binary search?. I had the same question today. I was able to solve it O(n). But interviewer asked if I could do better, and I mentioned binary search but didnt know how to implement it. thank you
@@thugsmf Did you pass the interview? I could implement it in O(N), and design an O(logN) solution with 2 modified binary searches, but it's hard to implement it the first time without errors.
@@EE12345 nah. I didnt pass the interview. I just implemented it in O(n). Didnt bother designing the O(logn) solution. just basically told interviewer I didnt want to risk not getting the solution so just did it linear time. guess it was way too easy and too naive! but it was my first interview. so learned a lot. always give most optimal solution. hows job search for you? still struggling here
@@thugsmf I'm trying to get good at leetcode before I mass apply, but its taking so long... maybe I should just apply now?
8:54 the "YEA BOIIIIIIIIEEEE" moment ;)
Thanks bro, It became better to understand as you divided the problem in two parts.
This condition "target >= nums[start]" is not needed since nums[start] is already the smallest value in your array
good catch
@Duy Ngo thank you 🙏
That was "freakin" amazing explanation...Thank you very much!
Honestly, you changed the way I think about problem-solving.
Is the Pivot Element always going to be the smallest value element? I don't see that in the question, why can we assume the smallest number is always on the side that has the pivot?
Yes in a sorted then rotated array, Pivot element has a unique property in which elements towards its left and right will always be greater. The index of this pivot ele(Smallest element) gives the number of times the array which was sorted has been rotated.
Hope I cleared you're doubt!
ur explanation is really good,All ur videos are amazing,Please keep doing more leetcode questions.
finding pivot technique .. awesome
You are a legend! Never stop making vids!!
Great tutorial Nick, but... there's an edge corner case here where if the smallest number in the array is == target and at the same time is the value at the midpoint index, the search will return -1 even thou the target value exists in the array. To solve that little problem you should check in the first while loop after finding the midpoint if the array[midpoint] == target and return midpoint from there. Hope that helps , let me know
Correct me please. In line 21, the condition is target >= nums[start]... which will always be TRUE since our nums[start] is the minimum number in the array, right? so the if statement could be only the second part: target
Hi Nick! I loved your solution but it is failing for a particular test case
[1,3] target =3
Answer = -1
Expected Output = 1
Can you please explain?
why do you do midpoint = left + (right-left) /2, doesn't the left cancel out, so you can just do right/2?
priavtechannel2 the way I did it is the right way because in some languages and situations there is integer overflow error
Look up “binary search midpoint integer overflow”
Well another point is that when left is, for example, 5 and right is 10 where is the middle point? Sure on 7. And what happens if you do "right/2"? Your midpoint would become equals to left
Still a bit confused by setting the indexes after the check, like the +1 and -1 for left and right
this guy even make jokes he was like creating history 😂😂
HI! Thanks for sharing your knowledge every time, it's really help me, can you also teach us how to look at the time complexity when we finished the program ?
When it came up in your interview, did you do well on this problem? Or did you not know how to do it then?
made my life easier, thank you.. best explanation
5:45 can anyone tell me how this loop will ever break? left is always smaller than right?
first loop is for finding smallest element in that array ,as soon as left will be equal to right our loop will break
I loved the forced clap in the beginning 😆
I wonder if it's necessary to find the midpoint? I was trying to solve this without the first step. It seems doable, but every time I try my solution, it finds some edge cases where it does not work.
You explain every question in a splandid manner which is easily understandable. So thank you so much for the videos.
@Nick White:
Proposed modification:
===============================
You can already check if you found the looked up value, skip binary tree redundant processing
===============================
if (target == array[start])
{
return start;
}
else if (target == array[right])
{
return right;
}
===============================
else if (target > array[start] && target < array[right])
{
left = start;
}
else
{
right = start;
}
Can anyone tell me why this condition cannot suffice?
if(nums[midpoint] < nums[start]){
end = midpoint -1;
} else{
start = midpoint;
}
Nice approach.
thanks dude
Simple and clear explanation! Thank you!
Your solution is great also because you used int midpoint=left + (right - left)/2; instead of int midpoint=(left+right)/2; to avoid overflow.
Will this work with these inputs array --> [4, 5, 6, 1, 2, 3], search for element 3
Will you make a blind 75 series?
What a explanation thanks a lot !!
Why did you do while(left
I think its because if u have a 1 element array, the second loop will not run since left==right.
1st while loop will just find smallest element. So in 1st while loop, when left == right (i.e., loop breaks) left will be same as right which will be same as smallest (or pivot) element.
2nd one is a good old simple binary search hence left
Lol got this in a CoderPad interview. Like bruh...how am I supposed to figure this out without looking it up?
Hey nick I keep trying to find your leetcode solutions on GITHUB but I don't really know where the are . Could you let me know which repo do they belong to ?
How can we handle if there are duplicates, for search in rotated sorted array ii LC #81
Did u get any answer?
Shouldn't line 24 be right = start - 1; rather than right = start;
?
Well explained. Leetcode's own solutions are so hard to understand.
i understood the logic i just didn't figure out that it was best to find the smallest element first
I'm a beginner programmer, but in python couldnt you do "nums.sort()" which would sort the array, then run a binary search on it? I understand that you're doing java and that I may be completely wrong
If you look at the question on leetcode the problem requires you to solve it in log(n) run time, sorting is nlog(n) so you can't use it
@@richardliu5297 Thanks Richard, I don't know how time complexities work at all atm. I'm trying to do the problems without taking time complexities in mind (as stupid as that sounds). I'm also practicing on hackerrank and edabit, to make it easier 😅
@@theyellowflash100 Np, you have to learn how time complexities work. It's a fundamental part of leetcode and Computer Science.
Thank you! This is really helpful
What if the array is rotated n (length of array) times such that the rotated array is same as initial array then the smallest element would be the first element?I think this approach would fail....It would be better to check for rotation such that first element is always greater than the last element in the rotated array.... Am i making sense?
Thank you! Good explanation!
@Nick White this code doesnt work for all the test cases
How can we get the written code ?
I have still not been able to understand what is happening in the first while loops else condition
If u don't write
Right = n.length -1; on line no 19 again then code will crash for
{1,3} target 3
I suppose your code doesn't work for nums=[3,1], target=1 - incorrect pivot found
I don't know if I am stupid or.... lol nice one. Wish I could have come up with this on my own rather than trying some weird lengthy bunch of if statements
why line no 13 , not mid -1 , instead mid...Can someone help me understand?
[4,5,6,7,0,1,2]
3
This code does an infinite loop for the above input.
Just adding the following two lines will resolve the issue:
if(nums[0]==target) return 0;
if(nums[n-1]==target) return n-1;
Hey Nick, great video.
On line 35, you set right = mid - 1;
Given that right may in fact be the target, shouldn't it be right = mid? You even say yourself , "Target is less than nums of midpoint or equal to..." ,
actually as I typed this I answered my own question. This could not be the case since you proactively check if nums[midpoint] == target. In the previous binary search, this would not work since we do not know the target.
Good explanation
Please do leetcode number of island 2
thanks man! that's great!
Thank you so much!
I was asked this question in Snapdeal interview. But your solution have too many loops. I think we can just modify the basic binary search to eliminate a part of the array without caring for where min element is or then further dividing by that min element.
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left
class Solution {
public int search(int[] nums, int target) {
for(int i=0;i
Solution should have O(log n) instead of O(n) time complexity!
While your solution is obviously ok. In the real world, I would say this function is too big. I would split it into smaller functions. Is this taken into consideration during these types of coding tests (during an interview) ?
Yes, it is absolutely taken into consideration.
thank you sooooo much
thank you !
I got time limit exceeded with this code
Thanks
Showing time limit exceed , i wrote the same code twice and checked
For the test case : [ 4,5,6,7,0,1,2] 3
thanks man !!!!!!!
Why not do a simple linear search to find the target since it's a 1D array?
need to do it in O( log n)
Thank us for what???? I guess we'll never know.....
good sir
U a God
You are amazing sir.
why we cant do this by two pointers??
cool de bro
How could he don't make any mistakes? Do people who've got offers from FAANG companies all be like him? Maybe I should give up.. 😔
Because he has practiced this solution like 3-4 times before doing this video(check his submissions) No one is perfect! Don’t give up, and keep practicing! :)
he is just not good at explaining... may be because he sneaked the answerss from somewhere.. over confidence is not good when you're teaching man
Is this a even a Medium difficulty question ??? I mean you just need to find the value and return it's index. Still not understanding why leetcode has set the difficulty to Medium.
class Solution:
def search(self, nums: List[int], target: int) -> int:
for e in range(len(nums)):
if nums[e] == target:
return e
else:
return -1
My solution...
the solution needs to be in O(log n) time. Yours is O(n)
@@Ownage10297Then leetcode should not accept my solution
dude you must be kidding? If you come up with this solution in an interview, then the interviewer will not even ask you the next question. And leetcode accepted your solution because all the test cases will run successfully but in the question, it is clearly mentioned that the solution must be in O(log n).
A test case, that would fail:
Array: [2,3,4,8,7]
Target: 8
This will return -1 based on your code.
This test case does not meet the requirement of being a sorted array which has been rotated around a pivot. Binary search only works for sorted arrays, so we must have an array that is sorted. In this problem we have an array which has been unsorted about a pivot. Sorted, your array would be [2,3,4,7,8], if we rotate that about a pivot, we might get [7,8,2,3,4] as an example. but we could not just switch the 7 and the 8. I hope this helps
how come runtime is 0ms?