More simpler code - public static int findMin(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if(nums[mid] < nums[right]) { right = mid; } else { left = mid+1; } } return nums[left]; }
OMG!!!!!!!!!!!!!! Bro, you are too brilliant, I spent a full day and tried with so many types. how you did it. I am a new coder but I loved your approach man thankssssss!
@@NickWhite I did haha! I made sure to before the video ended. I noticed that there were zero likes and it would be wrong for me to comment and not hit that thumbs up
This is how we need to really think about when solving the question on leetcode by specific solution on specific questions, not just using the general solving method to submit all of similar questions.
As you keep dividing the array in half, you eventually get an array with a single element which would be nums[0] and left is originally set to that value.
@@dp4kallday Just wanted to point that what you stated is wrong. The array after getting divided by two and becoming smaller doesn't end at nums[0], but actually at any nums[i], where 0
Hey Nick thanks for the vid. The logic of binary search is pretty straightforward but it is the small details that sometimes throw things off, like why nums[left]
There are too many unnecessary conditions here... It is understood that if the left part of the array is sorted, that will mean that right part of the array is unsorted and vice versa. And rather than checking the adjacent variable, we can just keep moving the left index towards unsorted array and return the low at the end. Check the code below: var findMin = function(arr) { let low=0; let high=arr.length-1; while(lowarr[high]){ low=mid+1 } else{ high=mid } } return arr[low] };
A simper version. --------------------------------------------------- public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = left + (right-left) / 2; if (nums[mid] < nums[right]) { right = mid; } else { left = mid + 1; } } return nums[left]; }
Need a little help. I have a similar solution based on binary search. Until the commented line (Main program starts here), I have taken care of all the edge cases. After that, it's just a normal binary search program modified for this problem. But in the test case [3, 4, 5, 1, 2] it says that the function does not return any value. But if I dry run it, it does. What am I doing wrong? int findMin(vector& nums) { int n = nums.size(), left, right, mid; if(nums.size()==1){ return nums[0]; } if(nums[0]
Personally, if I got down to 2 or 3 elements in an array, I would just find the min in that array. This would solve having some complex code to determine the middle on a 2 element array. A couple of important assumptions with this question, 0 is the lowest int allowed, and the original array is sorted low to high before rotation. I would love to know what the point of this is in real life?
Hi, first of all thanks for this video, it really made me understand the concept well. However, when I executed this on Leetcode, I am getting an error that the time limit exceeded. Could you explain why?
Why not use HashSet ? I am new to programming import java.util.*; class Solution { public int findMin(int[] nums) { HashSet h = new HashSet(); for(int x : nums){ h.add(x); } System.out.println(h); return (Integer)Collections.min(h); } }
HashSet will have O(N) worst case time complexity {where N = number of elements in the array} whereas Binary search will do it in O(LogN). Hope that helps.
More simpler code -
public static int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] < nums[right]) {
right = mid;
} else {
left = mid+1;
}
}
return nums[left];
}
OMG!!!!!!!!!!!!!! Bro, you are too brilliant, I spent a full day and tried with so many types. how you did it. I am a new coder but I loved your approach man thankssssss!
It is great. But Nick's solution has slightly better time complexity.
The problem requires you to solve it in O(log n) time not O(n) time.
@likhith chinnam My bad, I thought he wasn't using binary search. This solution is still O(logn).
you are og
The explanation was pretty good, just don't worry and keep going to make videos. Normally, I don't write comments but thank you man, really!
Nice work!!
More staright forward code (c++)
class Solution {
public:
int findMin(vector& nums) {
int n = nums.size();
if(n == 0) return -1;
int mid;
int low = 0;
int high = n -1 ;
while(low < high)
{
mid = low + (high - low)/2;
if(nums[mid] > nums[high])
low = mid+1;
else
high = mid;
}
return nums[high];
}
};
Can you please explain why you returned nums[high]??
@@anuradhapandey2173 because if you see in the else part, we assign high as mid. Also, if you dry run this algo you will get to know why high.
Hi Nick, I liked this one, it's clean and 100 percent faster
Aaron Brown hell yeah man make sure to throw me a like so the algorithm promotes me
@@NickWhite I did haha! I made sure to before the video ended. I noticed that there were zero likes and it would be wrong for me to comment and not hit that thumbs up
You’re a good man
@@NickWhite and you are a great man
The loop condition (left < right) isn’t explained as different than a regular binary search.
anyone can explain?
@@eugbyte1822 the whole point is to make l=r because when l=r then while loop break and the single element left and that is your minimum number
This is how we need to really think about when solving the question on leetcode by specific solution on specific questions, not just using the general solving method to submit all of similar questions.
How do you know the value will be at index "left"?
As you keep dividing the array in half, you eventually get an array with a single element which would be nums[0] and left is originally set to that value.
@@dp4kallday Just wanted to point that what you stated is wrong. The array after getting divided by two and becoming smaller doesn't end at nums[0], but actually at any nums[i], where 0
Hey Nick thanks for the vid. The logic of binary search is pretty straightforward but it is the small details that sometimes throw things off, like why nums[left]
ig its for the case where midpoint can be same as the left index .
Nick, you are a star!!! I have my interview with Microsoft next week. Pray for me.
how'd it go
@@saldanaswiz1291 I just finished my internship at Microsoft today and got a return offer. I still come to this site just for fun.
@@jaitehkaba8753 What TC did they offer you?
Thank you for keeping it short in the intro we appreciate it!
There are too many unnecessary conditions here... It is understood that if the left part of the array is sorted, that will mean that right part of the array is unsorted and vice versa. And rather than checking the adjacent variable, we can just keep moving the left index towards unsorted array and return the low at the end.
Check the code below:
var findMin = function(arr) {
let low=0;
let high=arr.length-1;
while(lowarr[high]){
low=mid+1
}
else{
high=mid
}
}
return arr[low]
};
but if the array is not rotated at all then we will need the conditions
@@bhavyasharma4863 yes makes sense !
Hi Nick!
Probably got unnoticed, but your LinkedIn URL is incomplete. (from video description)
Code doesn't work for input [3,3,1,3]
A simper version.
---------------------------------------------------
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right-left) / 2;
if (nums[mid] < nums[right]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}
Hey Nick, Great explanation, Thank you for making these videos, they are really helpful, please keep making more videos.
def binary(A,st,en):
while(True):
mid=(st+en)//2
if(A[mid]
Need a little help. I have a similar solution based on binary search. Until the commented line (Main program starts here), I have taken care of all the edge cases. After that, it's just a normal binary search program modified for this problem. But in the test case [3, 4, 5, 1, 2] it says that the function does not return any value. But if I dry run it, it does. What am I doing wrong?
int findMin(vector& nums) {
int n = nums.size(), left, right, mid;
if(nums.size()==1){
return nums[0];
}
if(nums[0]
Thanks for the algo, but does it work when our input is [2,1] ???
No it does not
This is a not a pivoted array, it's just a descending ordered array so it's not in the scope of this exercise ;)
No need for line 3 to check `if (nums.length == 0) return -1` as the problem specifies 1
Personally, if I got down to 2 or 3 elements in an array, I would just find the min in that array. This would solve having some complex code to determine the middle on a 2 element array. A couple of important assumptions with this question, 0 is the lowest int allowed, and the original array is sorted low to high before rotation. I would love to know what the point of this is in real life?
Why can't it be just Arrays.sort(nums); return nums[0]?
it will be in O(nlogn), question asked to do in O(logn)
pretty good explanation nick !!!
last 10 seconds was the best :)
Hey that's a great explanation
very good explanation
9:35 same thought here 😂
Getting index -1 out of bounds for length 2
Hey can't I use arrays.sort in it and print the element at 0 index???
It’s time complexity is O(nlogn), this problem requires O(logn)
if it weren't for O(log(N)), then ideal solution should have been linear search, sorting and then searching is very slow and inefficient.
Why don't you just identify the pivot and return the number at the pivot. Finding pivot is just like how you did it for leetcode 33.
thank you!
Best explanation of this problem
No BS and so crisp 👍🏻
Believe me, it was a very good explanation!
Hi, first of all thanks for this video, it really made me understand the concept well. However, when I executed this on Leetcode, I am getting an error that the time limit exceeded. Could you explain why?
You need sleep man
hey good explanation by the way you look like shown murfy from the good doctor
i feel binary search is too hard to simulate and write the edge cases did u see that he returned nums[left] why? i am figuring it out right now
left and right becomes the same thing, which is the last element left
If the array is not rotated simply then nums[left] should be min.
thnx bro for this
so who as the thought of just doing
min(nums)
that was my brute force😂.. its more efficient than this
hmm, nice one
not successfull in leetcode now . idk why !
Why not use HashSet ? I am new to programming
import java.util.*;
class Solution {
public int findMin(int[] nums) {
HashSet h = new HashSet();
for(int x : nums){
h.add(x);
}
System.out.println(h);
return (Integer)Collections.min(h);
}
}
Try to analyze space and time of your algorithm and you will know the reason :)
HashSet will have O(N) worst case time complexity {where N = number of elements in the array} whereas Binary search will do it in O(LogN). Hope that helps.