i love the why how sorts on you tube help me with some idea when i can do all problems by my self, Thank you!! keep posting more .. also if you can do on system design
In theory that is not the best solution since it would be O(n) while this video's is O(log(n)). In reality there's a decent chance it'd actually be faster (at least without massive array sizes) because library functions are magical sometimes
The solution is pretty simple actually. Lets say in the array 4,5,6,1,2,3 you have to search 2. Now, you find the middle value which is 6. Now 6 is greater than 3,however, 2 is less than 3. So, you search in the right side only, ie from 1 to 3. And the next pivot is 2. Now what happens if the array is something like 3,4,5,6,1,2 and you have to find 3? Here, 5 is the initial pivot. Now, we see that 2 is less than 5, and 3 is less than 5, however, 3 is greater than 2 as well. So, we check in the left interval.
You know leetcode would have some gigantic input at the end and it would timeout. Gotta get that bigO down, but conceptually yeah you can just iterate through linearly.
If it’s just rotated at one point, why can’t we do this: First, check if nums[0] < nums[-1] then return nums[0] as solution and end, else; keep checking until nums[i] > nums[i+1] n whenever this condition is met the solution is nums[i+1].
@@Niceguy54444as a programmer for 10+ years, I have never needed to do anything like this in real world programming. I think many people in the business would say the same. This sort of problem is only really relevant in these sorts of predefined puzzle questions.
Am i dumb, you have to find the minimum right? If i find the starting point where the array got rotated i don't need to do binary search then. And Binary search is only possible in a sorted array, so i can't improve finding the pivot point 😂🤔
Master Data Structures & Algorithms For FREE at AlgoMap.io!
i love the why how sorts on you tube help me with some idea when i can do all problems by my self, Thank you!! keep posting more .. also if you can do on system design
Will do
Python programmers be like min()
Real
In theory that is not the best solution since it would be O(n) while this video's is O(log(n)). In reality there's a decent chance it'd actually be faster (at least without massive array sizes) because library functions are magical sometimes
*std::min_element(nums.begin(), nums.end());
@@CoolExcite exactly
Wouldn't the answer always be arr[n/ 2 + 1] ?
pivot isnt always in the middle
Not always depends on how it's rotated
what if it rotates fully and starts the same, then the smallest is arr[0]. Never guaranteed to rotate half way.
hmm this solution seems a lot more simple than Neetcode’s 🤔
The solution is pretty simple actually. Lets say in the array 4,5,6,1,2,3 you have to search 2. Now, you find the middle value which is 6. Now 6 is greater than 3,however, 2 is less than 3. So, you search in the right side only, ie from 1 to 3. And the next pivot is 2.
Now what happens if the array is something like
3,4,5,6,1,2 and you have to find 3?
Here, 5 is the initial pivot. Now, we see that 2 is less than 5, and 3 is less than 5, however, 3 is greater than 2 as well. So, we check in the left interval.
Glad you've got it figured out! :)
Why not just iterate till n>n+1? And if halfs rotated, we can start iterating from (n/2)-1. Will it work?
It doesn't have to be half rotated.
We also need to take time complexity in account
That will work, but the time complexity of that is O(n). When this question is asked, it generally requires the solution to be in O(log(n)) time.
You know leetcode would have some gigantic input at the end and it would timeout. Gotta get that bigO down, but conceptually yeah you can just iterate through linearly.
What if elemnets in array have duplicates. How the approach will change
well if that was the case, the exercise would tell you. In this time all the arrays in the 67 test don't have any duplicate
If not mentioned in the question that it doesn't have any duplicates then use set data structure
If it’s just rotated at one point, why can’t we do this:
First, check if nums[0] < nums[-1] then return nums[0] as solution and end, else;
keep checking until nums[i] > nums[i+1] n whenever this condition is met the solution is nums[i+1].
Yes I think that's right :)
Is this guy the programmer from Ex Machina?
He is not lol
You took a sorted array in which both the sides of mid are sorted .what if they aren't?
They will be, because the original array was sorted and shifted :)
I don’t understand why wouldn’t you just iterate thru the array and return lowest value?
Binary search has better time complexity O(log n) as compared to iterating the array and returning the minimum O(n).
@@lakshyakwatra3430 interesting, thanks!
It is okay if we have a small array, But binary search solution really helps if we have millions of values in array
I can't think of any real world applications for this?
No? Job interview, i have been asked for that every time
@@Niceguy54444as a programmer for 10+ years, I have never needed to do anything like this in real world programming. I think many people in the business would say the same. This sort of problem is only really relevant in these sorts of predefined puzzle questions.
Binary search be like i am coming
Hey greg sir i m first year btech undergrade plz can u tell me what to skills to learn except the dsa and web dev plzz🎉
In my experience, Cloud Computing was the one skill that wasn't part of the curriculum that would've been really useful to have while job hunting
English (not joking even)
Systems Design, API Design, Object Oriented design, DB modeling
Am i dumb, you have to find the minimum right? If i find the starting point where the array got rotated i don't need to do binary search then. And Binary search is only possible in a sorted array, so i can't improve finding the pivot point 😂🤔
Damn
🤣
sort((a,b)=>a-b)[0]