Search in rotated sorted array - Leetcode 33 - Python
Vložit
- čas přidán 9. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Solve it yourself: neetcode.io/problems/find-tar...
0:00 - Conceptual
8:55 - Coding solution
#Coding #Programming #CodingInterview
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Search in Rotated Sorted Array II - czcams.com/video/oUnF7o88_Xc/video.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?
@@aadil4236 your array looks something like
7 8 9 1 2 3 4 5 6
Save the first element for reference: a0 = 7.
Take the middle element of the array (2). If it’s smaller than a0, then your pivot element is to the left. Else, it’s to the right. Repeat, and you will find the index of your pivot element in O(log n) time.
Then, if the value you’re searching for is larger than a0, use binary search in the left part of the list (from 0 to pivot index). Otherwise, the right side (from pivot index to end).
@@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.
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?
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!
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
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 😅
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 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.
Amazing Explanation! thank you, the handwritten stuff really helped me understand this easier.
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
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!
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.
this has been one of the most solutions to wrap my head around for some reason
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.
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!
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.
Man idk how you manage to explain so elegantly!
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!!!
Thank you very much!! I learned a lot from this video.
if nums[l]
Nice one. I like this solution better
This make so much sense to me! Thank you
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!
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.
Thanks. Your explanation is very clean
Thanks - this is crystal clear!
Thank you Sir. Very nicely explained and useful.
nice explanation - kind of figured out myself general idea but its so easy to get confused when use "
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 won't stop talking, you explain so well. Thank you so much
Hello, your videos are awesome! it takes me to the next level. Thank you!
you have the best explanation! thank you
Fantastic as always ❤️
Great Explanation. Thank you!
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
This is a dope explanation.
array problems make me feel like i have IQ below 80
The explanation with graph is really helpful
Great explanation, thanks! :D
Very nicely explained
Best explanation!!!
Great vid, thank you!
Beautifully explained
Thanks. A very good explanation.
thanks, you always have the best explanation
You are amazing!!
great solution! Thank you
Thank you so much!
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!
I feel like this solution makes slightly more sense:
left = 0
right = len(nums) - 1
while left = nums[left] and target
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)
great work thanks so much!
i knew the methods but so many things we were testing and it tripped me off
target < nums[l] and target > nums[r] make it hard to visualize. target >= nums[pivot] and target
Awesome explanation, thanks.
Happy it was helpful!
God bless you man, you are incredible.
thank you finally understood
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
Really awesome
This was awesome
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)
That Visualization Supremacy. 💯
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!
Thanks!
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.
@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 is that software you used to explain the algorithm ?
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
well explained
awesome!
Very clear and helpful!
I got a time limit exceeded warning when trying to submit though :(
i think there is a bug.
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
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
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 was asked to me in the first round of an interview
thanks
Thanks
why do we need to use "while left
says it at 9:20
you use left < right when you want "eager termination", that means after while loop exited, left==right.
Hoping that one day I can visualize problems by drawing pictures like this
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
This statement being true doesn't mean you are on the left part: "nums[L]
Python is not my strongest language. Is //2 is dividing by 2 and truncating the decimal part? TY
Yeah that's exactly correct.
My head hurts🤯How this seemingly easy problem becomes so complex, I hate leet code mannnnnnn. TY for making it easier, I kept failing test cases because I didn't identify I needed to be looking at whether I was at left sorted or right sorted portion ugggghhhhhh
When comparing whether the target element or mid element is in the left half or right half, why must we compare against the left element instead of comparing against the first element>, e.g . `nums[mid] > nums[left]`, but not `nums[mid[ > nums[0]`;
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
Good explanation from 6:30
Todo:- take notes
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.
I had changed the if conditions this way for better understanding:
if (nums[s] = nums[s] && target < nums[m]) {
e = m -1;
} else {
s = m +1;
}
} else {
if (target > nums[m] && target
I wonder why in the coding sol: if nums[m] >= nums[l] then nums[m] is in the the left sorted portion. From my finding, it should be nums[m] >= nums[0]
this is easy to understand but hard to write running code without bugs
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]
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.
I have a very curious question for anybody who works at a large scale competitive FAANG type company -- what is the expectation here for an interview process with a question like this? I am not asking this as in i am upset or disagree, but moreso to gauge my level of focus and help develop a better gameplan The interview process (to my understanding) is to test your level of understanding on algorithm and design, data structures and implementation. So when you see a problem like this, You can understand every function of an array data structure and the time and space complexity of every function of an array. You can know when to use it over other data structures that can solve the same question and can even come to the conclusion that an array (since we are talking about contiguous memory) is in fact the best data structure to use here. So you spend your time focusing on that data structure. However, that doesn't help you understand the actual methodology and pattern recognition. To me, that seems like something a mathematician can easily come up with that as a result, I would look to hire a strong mathematician with some software design background over someone with a strong computer science background and a good mathematical background. So for the people with much more experience, have gone through FAANG level interviews or even have been part of an interview committee, what is the expectation of a candidate when presented a problem like this during an interview and also what tools helps you gain that understanding of pattern recognition and more or less mathematical proofing and what is the expectation in terms of a FAANG interview as a entry level SWE? Again, let me say I am committed to studying and getting my skill set to where it needs to be. Me asking this question is more or less to put things in perspective and help revamp my study habits.
This is a good question so I'll do my best to answer it. Coding interviews _aren't_ just to test algorithms and data structures. They're designed to test your communication skills, problem-solving, ability to quickly write clear and bug-free code, _and_ your knowledge of algorithms and data structures.
The reason you get problems like this is because they have a twist to them, so you have to problem solve rather than just apply a basic algorithm. They want to see that you can break down the problem and find a way to approach it.
There are a number of techniques you can use. You can draw diagrams, walk through examples, simplify the problem by ignoring some constraints, break the problem into sub-problems etc. Polya's book "How to Solve It" was written for mathematicians but you can adapt some of the techniques listed in the first 20-30 pages to use here. There's a short summary at math.berkeley.edu/~gmelvin/polya.pdf. The book "Cracking the Coding Interview" (pg 60 to pg 81) also has a section on technical problem solving that I like. That's more focused on coding interviews obviously.
In this problem for example, you can make a number of observations. A rotated sorted array has two sorted parts. For example, [4,5,6,7 | 0,1,2] If we could use binary search to find where the boundary is between the two parts, then we could do a basic binary search on each of those sorted parts. We also note that the boundary is just the smallest element in the array. Or we could note that the boundary is the only place where we have a larger element before a smaller element, like [...,7, 0,...]. These observations are like puzzle pieces that you can put together into a complete solution. You could also make other observations which lead you towards the solution that NeetCode did.
You're going to have to sit down with pen and paper and really think about the problem. Initially you'll be slow but you'll get better with practice. Many people give up if they can't solve a problem in 15-20 minutes so they don't develop their problem solving skills. That's one reason why you see people grinding 500 or 800 LeetCode problems, trying to learn all the "patterns", but still not doing well at interviews. It's far more efficient to learn a small number of patterns and apply them in creative ways, than to grind hundreds of problems. There isn't really a pattern in NeetCode's solution other than knowing binary search well.
@@nikhil_a01 ok i will try pen and paper next time thx
this one is more eazy to understand
if nums[left]
understood
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
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 👍
This question should be marked Double Hard
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.
This doesnt seem to be working for non-distinct values