LeetCode 33. Search in Rotated Sorted Array
Vložit
- čas přidán 13. 09. 2019
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering - Věda a technologie
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.
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.
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
8:54 the "YEA BOIIIIIIIIEEEE" moment ;)
Thanks bro, It became better to understand as you divided the problem in two parts.
That was "freakin" amazing explanation...Thank you very much!
Simple and clear explanation! Thank you!
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
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
Thank you! Good explanation!
this question was so fucking hard almost made me quit coding.
Honestly, you changed the way I think about problem-solving.
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.
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 ?
finding pivot technique .. awesome
I loved the forced clap in the beginning 😆
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
ur explanation is really good,All ur videos are amazing,Please keep doing more leetcode questions.
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.
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
You explain every question in a splandid manner which is easily understandable. So thank you so much for the videos.
this guy even make jokes he was like creating history 😂😂
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 ?
Nice approach.
thanks dude
Thank you! This is really helpful
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?
thanks man! that's great!
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!
made my life easier, thank you.. best explanation
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.
What a explanation thanks a lot !!
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?
Thank you so much!
Still a bit confused by setting the indexes after the check, like the +1 and -1 for left and right
Will this work with these inputs array --> [4, 5, 6, 1, 2, 3], search for element 3
Well explained. Leetcode's own solutions are so hard to understand.
Can anyone tell me why this condition cannot suffice?
if(nums[midpoint] < nums[start]){
end = midpoint -1;
} else{
start = midpoint;
}
When it came up in your interview, did you do well on this problem? Or did you not know how to do it then?
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
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 🙏
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?
Lol got this in a CoderPad interview. Like bruh...how am I supposed to figure this out without looking it up?
thank you sooooo much
Good explanation
thanks man !!!!!!!
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;
?
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
Your solution is great also because you used int midpoint=left + (right - left)/2; instead of int midpoint=(left+right)/2; to avoid overflow.
How can we get the written code ?
@Nick White this code doesnt work for all the test cases
@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;
}
If u don't write
Right = n.length -1; on line no 19 again then code will crash for
{1,3} target 3
Will you make a blind 75 series?
thank you !
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 suppose your code doesn't work for nums=[3,1], target=1 - incorrect pivot found
I have still not been able to understand what is happening in the first while loops else condition
Thanks
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
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.
Please do leetcode number of island 2
You are amazing sir.
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.
how come runtime is 0ms?
U a God
good sir
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
cool de bro
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.
I got time limit exceeded with this code
[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;
Showing time limit exceed , i wrote the same code twice and checked
For the test case : [ 4,5,6,7,0,1,2] 3
Thank us for what???? I guess we'll never know.....
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!
why we cant do this by two pointers??
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! :)
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)
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).
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
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