Shorter code (don't need to initialize a results variable, since we know that the while loop will break when left pointer is pointing at the minimum): def findMin(self, nums: List[int]) -> int: l, r = 0, len(nums) - 1 while l < r: m = l + (r - l) // 2 if nums[m] > nums[r]: l = m + 1 else: r = m return nums[l]
if you dont know what binary search is, i would recommend to learn that first, the problem becomes more easy to understand if you know about that, and this explanation makes more sense if you try around 40 minutes to solve it by yourself, even if you dont get to the answer, the important thing is to solve it conceptually, even if you dont get to solve it with code
There is a much easier solution that I came up with: class Solution: def findMin(self, nums: List[int]) -> int: p1 = 0 p2 = 1 for i in range(1, len(nums)): if nums[p1] > nums[p2]: return nums[p2] p1 += 1 p2 += 1 return nums[0] You just set two pointers to the first and second elements and then update them through each iteration. If at any point the first pointer is larger than the second, you know the second is the minimum value due to the fact that the list is sorted.
Dear NeetCode, Thank you so much for your videos! The quality and comprehensiveness of your explanations is incredible. For every problem I solved or struggle to solve I will instantly turn to your videos. I won't even consider other TH-camrs because I know that your explanations are the best. Thank you for this quality content!
I really hate Binary Search problems, Binary search by itself is simple, but its implemented in so many different weird ways, which make it really dumb..
You can skip the first if condition by doing this: Instead of comparing mid pointer with left, compare it with right (all other factors remain same). For example: [4,5,6,7,0,1,2] Iteration 1: start pointer (s) = 0 end pointer (e) = 6 mid pointer (m) = (s+e)//2 =3 here, nums[m] >= nums[e]: therefore, s=m+1 Iteration 2 s=4 e=9 m = 5 here, nums[m]
I agree, I was thinking this too. What if they rotated it n times and it is back to its original sorted state where the leftmost element is the smallest. If we compare mid to the right, and see if mid is bigger, then go right, else go left
Although your answer is more concise, I think it's less efficient than NC's answer. For example, in a perfectly sorted array, NC's answer is O(1). Your answer still will be O(log(n)).
@@lxu5148 I tried to add pastebin link here but keeps getting deleted. But this is what my if condition looks like if(nums[lo] == nums[mi] && nums[mi] == nums[lo]) return Math.min(findMin(nums, res, lo, mi-1), findMin(nums, res, mi+1, hi)); else if(nums[mi] >= nums[lo]) // If mid is greater then everything on left, the look on right side lo = mi + 1; else hi = mi - 1;
The way I like to think about it is we're searching for the point where the sorted array 'resets' to the minimum. If the middle is less than the leftmost value, that means the 'reset' point is somewhere on the left side. Otherwise, it's on the right side.
because of how the sorted array and rotation works, if the inflection point is to the left of M, L and R are always larger than M, but if the inflection point is to the right of M, L and R are always smaller than M.
Beautiful Explanation. I used the same code for the 154. Find Minimum in Rotated Sorted Array II with just one change and it was accepted. Since in 154 problem, there are duplicates as well, I added an extra check in case all elements at start, mid and end are the same. In that case, we just decrement the end pointer by 1. Otherwise, the code remains the same. while start = nums[start]: start = mid + 1 # Otherwise, we will find the minimum on the left side else: end = mid - 1
hmmm the condition to determine if arr[mid] is in the first sequence to be arr[mid] > = arr[start] is not enough. Counter example: [4,5,6,7,0,1,2], l = 0, r = 6, mid = 3, after first update, start = mid + 1 which is 0, we are searching in subarray[0, 1, 2]in this case arr[mid] > arr[start] still holds, but it is in the second sequence. The only reason that your solution passed is because you're updating the result all the way.
Thx NeetCode, here is my solution: class Solution: def findMin(self, nums: List[int]) -> int: left, right = 0, len(nums)-1 while left < right: mid = (left+right) // 2 if nums[mid+1] < nums[mid]: return nums[mid+1] # left sorted if nums[mid] > nums[left]: # search on right left = mid + 1 # right sorted else: # search on left right = right - 1 return nums[0]
My solution: def findMin(self, nums: List[int]) -> int: 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]
The most effective I suppose would be: const foo = nums => { // [4,5,6,7,0,1,2,3] let [l, r] = [0, nums.length - 1] while (l < r) { let m = Math.floor((l+r) / 2) if (nums[m] >= nums[r]) l = m + 1; else r = m; } return nums[l]; }
You state the rules: "If our middle pointer happens to be in the right sorted portion, then we want to search to the left; **if our middle is in the left sorted portion we want to search to the right**". And later state: "If we ever got to a portion of the array that's completely sorted we would just **take the leftmost value and see if it's smaller than the current result and stop our binary search.**" This statement completely conflicts with the algorithm of focus, which says **if the leftmost value is smaller we search to the right**. So do we search to the left or "stop our binary search"? So are there two algorithms rules at play here or what? I'm guessing yes, but you said an entirely conflicting rule pretty flippantly without clarifying this is an important rule caveat and consideration.
I was able to come up with one before seeing the solution but I spent a couple hours going through examples and noticing patterns to think of the solution. Wouldn't be able to come up with it on the spot yet, but I guess that's why we practice!
Well, if we weren't so caught up in trying to learn/solve it with binary search we could actually just look for the minimum number with one for loop 🤷♂
I'm not sure this applies on Python, but when we calculate the middle element, I think it would be better to write; middle = left + (right - left) / 2; instead of middle = (left + right) / 2; to prevent arithmetic overflow. en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues
Ha! Solved this on my own, my code worked but was a bit wonky. Good to see this video :) I spotted the pattern of if a part was steadily increasing or not. I didn't use the midpoint to determine any values, I just used it as a pivot and ultimately would return l or r :') Here's my wonky code (it works!) var findMin = function(nums) { let l = 0 let r = nums.length - 1 while (r - l > 1) { let m = Math.trunc( (l+r) / 2) const [isLeftIncreasing, isRightIncreasing] = isSteadilyIncreasing(nums[l], nums[m], nums[r]) if (isLeftIncreasing && isRightIncreasing) return nums[l] else if (isLeftIncreasing) { //pick right l = m } else if (isRightIncreasing) { //pick left r = m } } if (nums[l] >= nums[r]) return nums[r] else if (nums[l]
I have another solution based on his logic where I don't keep track of the min res value: l, r = 0, len(nums)-1 while nums[l] > nums[r]: mid = (l+r)//2 if nums[mid] >= nums[l]: l = mid + 1 else: r = mid return nums[l]
Firstly: you're a genius, thanks for sharing so much on YT. Today LC came up with a use case [3,1,2] for this problem which breaks the `mid + 1` or `mid - 1` logic in this case where the answer is mid but given LEFT > MID we would to to index 0 and miss the correct answer. A little tweak on the original code should suffice tho': def findMin(self, nums: list[int]) -> int: if len(nums) == 1: return nums[0] left, right = 0, len(nums) - 1 while left = nums[left]: left = mid else: right = mid
it still works right? the answer is MID but LEFT > MID, we capture the minimum already by doing min(res, nums[mid]) before comparing LEFT > MID... the minimum will remain as 1 throughout the entire loop. Your answer is a little better as we don't need to store a variable for the mininum value and perform a comparison to get the minumum value per loop. Great job!
Hey GUstavo, thanks for your insight! I would love to talk to you more about problem solving. Is it possible I can contact you in any way like DIscord or Twitter?
I have a simpler alternative that allows you to not keep track of the minimum, here it is: class Solution: def findMin(self, nums: List[int]) -> int: start, end = 0, len(nums) - 1 while start - end > 1: # if middle exists mid = (start + end) // 2 if nums[mid] > nums[end]: start = mid + 1 else: end = mid return min(nums[start], nums[end])
I did this solution quite different by checking if middle is < middle-1 I can itentify the lowest number: def findMin(self, nums: list[int]) -> int: l, r = 0, len(nums) - 1 while l nums[r]: l = middle+1 else: r = middle-1 return nums[l]
mid pointer is always pointing to the potential minimum value in the array. Therefore, you want to keep updating the res variable to be checked against the new mid pointer value each iteration.
Check the case discussed from 9.06. that will answer why we need to update res. If res would not have been updated, we would get min as 3 instead of 1 in this case.
Doesn't initializing right pointer to the end of the array itself take O(n) time? Languages like Python might have under the hood optimizations to do this more efficiently, but from algorithmic perspective, if we have to iterate through the array once to initialize the right pointer, wouldn't it be more efficient to just find the minimum in that iteration itself?
My solution which I think is more intuitive: class Solution: def findMin(self, nums: List[int]) -> int: start , end = 0 ,len(nums) - 1 curr_min = float("inf")
while start < end : mid = (start + end ) // 2 if(nums[mid+1] < nums[mid]): return nums[mid+1]
# right has the min if nums[mid] > nums[end]: start = mid + 1
while(l Think why! else h = mid; } } For anyone who is struggling, I break these type of questions to 2 cases. (mid is in sorted sub_array, mid is not in sorted_subarray). Write cases accordingly!
*'min' use O(N) time to search for the minimum element in an array. * It uses linear search. * The time taken shown in leetcode doesn't provide you the actual time taken.
@@vaishaliagrawal4781 min(array) gives you minimum of array in O(N) but if we write min(x, y) gives minimum in O(2) which is a linear operation. Thus the code still remains O(logn). I hope this helps!!
Is the EQUAL SIGN in "(nums[l] >= nums[m])" ONLY for the case of an input like [2,1] where l=0, m=(0+1)//2 = 0 but we randomly need to check the other index value too "just because" (outside of our actual defined rules we've outlined)... just to make sure?
MORE EASIER WAY! def findMin(self, nums: List[int]) -> int: res = float("inf") l, r = 0, len(nums) - 1 while l nums[r]: l = m + 1 else: r = m - 1 return res
@@ganeshkamath89 I've been practicing it without storing the minimum result for a few months now. I don't think you need to store the minimum. I just return the `nums[m]` value.
def findMin(self, nums: List[int]) -> int: bad = -1 good = len(nums) - 1 while good - bad > 1: candidate = (bad + good) // 2 if nums[candidate] < nums[good]: good = candidate else: bad = candidate return nums[good]
No need to do any storing and comparing. Simple Binary searching here.. def findMin(nums,l,h): mid= (l+h)//2 if(nums[l]nums[h]): return h return findMin(nums,l,mid)
You mention that the left sorted portion is always going to have values > the right sorted portion. In the event that the array has not been rotated or rotated n - 1 times (which would produce the same array) then wouldn't that statement not be true? Ex: [0,1,2,3,4,5,6,7] ... m = array[4] ... array[4] == 3 ... 3 >= 0 ... we are in the left sorted portion ... all values of the right sorted portion are greater than the left. Maybe I am confused but if someone could clarify I would greatly appreciate it.
The funny thing is I test my naive solution which o(n) in Javascript: function min(nums) { return Math.min(...nums); } and it beats 23% of other solutions which used binary search 🤣
C++ solution: class Solution { public: int findMin(vector& nums) { int i = 0 ; int j = nums.size() - 1; int mid = (i+j)/2; if(nums.size()==1) { return nums[0]; }
/* idea: use binary search. If the value to left of mid is smaller than the right pointer, then move right pointer to mid Otherwise, move left pointer to mid */ while(i
Hey, I had quick question. Since the problem statement asks us to solve this in O(logn), don't you think using min() function (which O(m)) make this O(mlogn) ?
I hope you can make a video about Binary Search Templates and help us understand it better. Thank you. class Solution: def findMin(self, nums: List[int]) -> int:
low, high = 0, len(nums) - 1
while low < high: mid = (low + high) // 2
if nums[mid] < nums[high]: high = mid elif nums[mid] > nums[high]: low = mid + 1 return nums[high] #nums[low]
Good explanation, however, I think we can improve it keeping L and R, but looping length/2 times in both direction, if nums[L] > nums[L+1] then L is the position of the minimum or if nums[R] < nums[R-1] then position R holds the minimum: // C# for (int i = 0, j = nums.Length - 1; i < nums.Length / 2; i++, j--) { if (nums[i] > nums[i + 1]) return nums[i + 1]; if (nums[j] < nums[j - 1]) return nums[j]; } return nums[0];
after the condition if nums[m] >= nums[l]: you need to update res to nums[l] because according to the condition it is less than nums[m](our current res) and this is the last time we'll be visiting the current nums[l] (since we update l to m+1)
We are always terminating if nums[l] < nums[r] to handle this, so there is no need to explicitly check nums[l] at each iteration. For instance if nums[m] >= nums[l] we know that nums[l] is also greater than or equal to nums[r] (because we checked this condition first)... therefore there is no way nums[l] at that point will be the minimum result since there is a smaller value on the right side of the array and we update l to mid + 1 to search the right side. Put more simply... because we always check nums[l] < nums[r] we are always guaranteed to terminate and set the result to nums[l] if nums[l] is ever the min.
Thank you for your valuable time. I really appreciate. If anyone is looking for Java Code: public static int findMinimum(int[] input) { if (input == null || input.length == 0) { throw new IllegalArgumentException("Invalid input passed"); } int left = 0, right = input.length - 1, mid = 0; while (left != right) { mid = (left + right) / 2; if (input[mid] >= input[left]) { left = mid + 1; } else { right = mid - 1; } } return input[mid]; }
class Solution: def findMin(self, nums: List[int]) -> int: try: for ele in range(len(nums)): if nums[ele] > nums[ele+1]: return nums[ele+1] except: return nums[0]
@@Rahul-eh3rf What about my code here: l, r = 0, len(nums) - 1 while l < r: if nums[r] > nums[r - 1]: r -= 1 elif nums[r] < nums[r - 1]: return min(nums[l], nums[r]) if l == r: return nums[l] # if nums[r] can move down then keep nums[l] # if nums[r] cannot move down compare value with nums[l] and return smallest value # if index l and index r are the same, return nums[l] everything fine? It passes all test cases but not sure if O(log n).
@@Lambyyy It's O(n) because you are essentially comparing every num against left num. A O(logn) solution is possible here if the problem size is halved every step.
Isn't the time complexity of min() function O(n), which kinda defeats the purpose of using binary search to find the solution in O(logn)? If we must use min(), we can just do `return min(nums)` at that point? Someone please explain, I am a little confused. Thanks!
My gawd, every one of these binary search problems I get some edge cases wrong due to these tiny but important details of settings r = m (instead of m - 1) or having l start from 1 instead of 0 (koko eating bananas). It's super frustrating
In python a single '/' will evaluate to decimal division (e.g. 1 / 2 = 0.5), where as '//' evaluates to integer division which is the default for most languages (e.g. 1 / 2 = 0)
Thanks for the explanation. One point of feedback I would recommend is to cut down or outright stop saying the word "right" when you're not talking about the direction. It can get confusing in problems in which the left/right directions are crucial to explaining the solution (e.g. this solution or tree related solutions). Every time you say "right", we have to differentiate between the direction and you confirming something which just adds extra noise to your explanation
Good point for some people. For me, I am used to his kind of speech pattern and maybe being a native English speaker it helped me not be distracted by it, but it could be a problem for ESL people or just for people who don't speak/think in that pattern. Learning is already complicated, so additional barriers when unnecessary can be frustrating.
I like all of your videos I watched so far except this one. You talked too fast, and I'm lost where you said if the middle is 1 then search on the left.
![โฮ่ง! (SUGOI) - LYKN [ OFFICIAL MV ]](http://i.ytimg.com/vi/nFp4zjAARFs/mqdefault.jpg)
![[FULL EP.73] เปิดบ้าน 70 ล้าน "แป้ง Zbing" ยกมาทั้งญี่ปุ่น l เคหสถานบานปลาย l One Playground](http://i.ytimg.com/vi/YBnJhTt07Pg/mqdefault.jpg)
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Shorter code (don't need to initialize a results variable, since we know that the while loop will break when left pointer is pointing at the minimum):
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l < r:
m = l + (r - l) // 2
if nums[m] > nums[r]:
l = m + 1
else:
r = m
return nums[l]
thanks, this solution made more sense to me
Hey I tried this, but it doesn't work for this set of nums:
nums = [12, 0, 1, 2, 3, 4, 5, 6, 9, 10, 11]
@@christianmorabito4148 works on my end 🤔
@@Grawlix99 Oh yes!! Sorry, I was returning m (mid variable) instead of l (low variable).
@@christianmorabito4148 np! 😃
I've watched this video probably 10-15 times over different days, and only now is it starting to make sense. Bless.
In all fairness, this particular explanation is not the most intuitive. Still grateful tho.
if you dont know what binary search is, i would recommend to learn that first, the problem becomes more easy to understand if you know about that, and this explanation makes more sense if you try around 40 minutes to solve it by yourself, even if you dont get to the answer, the important thing is to solve it conceptually, even if you dont get to solve it with code
There is a much easier solution that I came up with:
class Solution:
def findMin(self, nums: List[int]) -> int:
p1 = 0
p2 = 1
for i in range(1, len(nums)):
if nums[p1] > nums[p2]:
return nums[p2]
p1 += 1
p2 += 1
return nums[0]
You just set two pointers to the first and second elements and then update them through each iteration. If at any point the first pointer is larger than the second, you know the second is the minimum value due to the fact that the list is sorted.
@@mattk.9937 that's o(n) solution, problem prompts you to solve it o(logn)
@@mattk.9937 that's a good solution but not O(log n) time
Dear NeetCode, Thank you so much for your videos! The quality and comprehensiveness of your explanations is incredible. For every problem I solved or struggle to solve I will instantly turn to your videos. I won't even consider other TH-camrs because I know that your explanations are the best. Thank you for this quality content!
I really hate Binary Search problems, Binary search by itself is simple, but its implemented in so many different weird ways, which make it really dumb..
I bet u hate dp too by that kinda logic 😂
@@crosswalker45 don't we all hate dp
@@sarvagyadwivedi2467 haha.. True
You couldn't be more accurate. It's like you have to come up with a different implementation of binary search for every problem.
You can skip the first if condition by doing this:
Instead of comparing mid pointer with left, compare it with right (all other factors remain same).
For example: [4,5,6,7,0,1,2]
Iteration 1:
start pointer (s) = 0
end pointer (e) = 6
mid pointer (m) = (s+e)//2 =3
here, nums[m] >= nums[e]:
therefore, s=m+1
Iteration 2
s=4
e=9
m = 5
here, nums[m]
i like this
I agree, I was thinking this too. What if they rotated it n times and it is back to its original sorted state where the leftmost element is the smallest. If we compare mid to the right, and see if mid is bigger, then go right, else go left
doesn't work for [3,1,2]
@@JamesBond-mq7pd yeah when searching left, e has to be set to m instead of m-1
Wayy more intuitive, thank you bro
more consice solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums)-1
while l=nums[r]:
l = mid+1
else:
r = mid
return nums[l]
Although your answer is more concise, I think it's less efficient than NC's answer.
For example, in a perfectly sorted array, NC's answer is O(1). Your answer still will be O(log(n)).
Thank for explaining this very clearly.
With a minor tweak I was able to solve following as well.
154. Find Minimum in Rotated Sorted Array II
Curious about how you modify the code to make 154 work. Do you mind sharing the script?
@@lxu5148 I tried to add pastebin link here but keeps getting deleted.
But this is what my if condition looks like
if(nums[lo] == nums[mi] && nums[mi] == nums[lo])
return Math.min(findMin(nums, res, lo, mi-1), findMin(nums, res, mi+1, hi));
else if(nums[mi] >= nums[lo]) // If mid is greater then everything on left, the look on right side
lo = mi + 1;
else
hi = mi - 1;
@@hrvmhv4391 appreciate it! I will check it when I am with my laptop.
@@hrvmhv4391
(nums[lo] == nums[mi] &&
nums[mi] == nums[lo])
? didn't get it. isn't that the same condition?
@@lxu5148 so, did it work?
The way I like to think about it is we're searching for the point where the sorted array 'resets' to the minimum. If the middle is less than the leftmost value, that means the 'reset' point is somewhere on the left side. Otherwise, it's on the right side.
you can actually do if m > r search right or if m > l search right. Either one works with the case added for the already sorted array
because of how the sorted array and rotation works, if the inflection point is to the left of M, L and R are always larger than M, but if the inflection point is to the right of M, L and R are always smaller than M.
Beautiful Explanation. I used the same code for the 154. Find Minimum in Rotated Sorted Array II with just one change and it was accepted.
Since in 154 problem, there are duplicates as well, I added an extra check in case all elements at start, mid and end are the same. In that case, we just decrement the end pointer by 1. Otherwise, the code remains the same.
while start = nums[start]: start = mid + 1
# Otherwise, we will find the minimum on the left side
else: end = mid - 1
Just move right to mid, instead of mid -1 and you won't need to check for min result.
Great explanation
My code:
class Solution:
def findMin(self, nums: List[int]) -> int:
low = 0
high = len(nums)-1
while low
hmmm the condition to determine if arr[mid] is in the first sequence to be arr[mid] > = arr[start] is not enough. Counter example: [4,5,6,7,0,1,2], l = 0, r = 6, mid = 3, after first update, start = mid + 1 which is 0, we are searching in subarray[0, 1, 2]in this case arr[mid] > arr[start] still holds, but it is in the second sequence. The only reason that your solution passed is because you're updating the result all the way.
He explained in the video that this condition does not work on sorted lists. The reason it still passes is because he has the nums[l] < nums[r]
Thx NeetCode, here is my solution:
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums)-1
while left < right:
mid = (left+right) // 2
if nums[mid+1] < nums[mid]:
return nums[mid+1]
# left sorted
if nums[mid] > nums[left]:
# search on right
left = mid + 1
# right sorted
else:
# search on left
right = right - 1
return nums[0]
Does this work for [5, 1, 2]?
shoot i guess it does
Works for edge cases where min as middle and [2,1]:
class Solution:
def findMin(self, nums: List[int]) -> int:
ans=nums[0]
l,r=0,len(nums)-1
while l
After watching the solution of problem 33 I solved this problem on my own! However your solution is always the best, I could learn from it a lot!
My solution:
def findMin(self, nums: List[int]) -> int:
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]
very simple indeed
The most effective I suppose would be:
const foo = nums => {
// [4,5,6,7,0,1,2,3]
let [l, r] = [0, nums.length - 1]
while (l < r) {
let m = Math.floor((l+r) / 2)
if (nums[m] >= nums[r]) l = m + 1;
else r = m;
}
return nums[l];
}
i found more shorter way:
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l
wow this is so much better and is way easier to remember
You state the rules:
"If our middle pointer happens to be in the right sorted portion, then we want to search to the left; **if our middle is in the left sorted portion we want to search to the right**".
And later state:
"If we ever got to a portion of the array that's completely sorted we would just **take the leftmost value and see if it's smaller than the current result and stop our binary search.**"
This statement completely conflicts with the algorithm of focus, which says **if the leftmost value is smaller we search to the right**. So do we search to the left or "stop our binary search"?
So are there two algorithms rules at play here or what? I'm guessing yes, but you said an entirely conflicting rule pretty flippantly without clarifying this is an important rule caveat and consideration.
One of the best explanation of this problem. Thank you ❤
This is one of the first medium problems that I correctly new the intuition. LETS GOO
are there people who have never seen this before and just came up with the solution on the spot? Kudos man
I was able to come up with one before seeing the solution but I spent a couple hours going through examples and noticing patterns to think of the solution. Wouldn't be able to come up with it on the spot yet, but I guess that's why we practice!
Well, if we weren't so caught up in trying to learn/solve it with binary search we could actually just look for the minimum number with one for loop 🤷♂
Your explanation is very good. Line no 7, condition should be if (nums[l]
I got this too, good catch.
I'm not sure this applies on Python, but when we calculate the middle element, I think it would be better to write;
middle = left + (right - left) / 2;
instead of
middle = (left + right) / 2;
to prevent arithmetic overflow.
en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues
Thats definitely a good point!
python don't have int overflow issue. java and cpp definitely need left + (right - left) / 2
That's right. That's how we know a senior and a junior
@@mindsetnuggets what joy did you get in putting him down, man? we all gotta learn to be more humble human beings
could be a good practice, but the input list is constrained to max 5000 elements
Ha! Solved this on my own, my code worked but was a bit wonky. Good to see this video :)
I spotted the pattern of if a part was steadily increasing or not.
I didn't use the midpoint to determine any values, I just used it as a pivot and ultimately would return l or r :')
Here's my wonky code (it works!)
var findMin = function(nums) {
let l = 0
let r = nums.length - 1
while (r - l > 1) {
let m = Math.trunc( (l+r) / 2)
const [isLeftIncreasing, isRightIncreasing] = isSteadilyIncreasing(nums[l], nums[m], nums[r])
if (isLeftIncreasing && isRightIncreasing) return nums[l]
else if (isLeftIncreasing) { //pick right
l = m
}
else if (isRightIncreasing) { //pick left
r = m
}
}
if (nums[l] >= nums[r]) return nums[r]
else if (nums[l]
I have another solution based on his logic where I don't keep track of the min res value:
l, r = 0, len(nums)-1
while nums[l] > nums[r]:
mid = (l+r)//2
if nums[mid] >= nums[l]:
l = mid + 1
else:
r = mid
return nums[l]
Firstly: you're a genius, thanks for sharing so much on YT.
Today LC came up with a use case [3,1,2] for this problem which breaks the `mid + 1` or `mid - 1` logic in this case where the answer is mid but given LEFT > MID we would to to index 0 and miss the correct answer.
A little tweak on the original code should suffice tho':
def findMin(self, nums: list[int]) -> int:
if len(nums) == 1:
return nums[0]
left, right = 0, len(nums) - 1
while left = nums[left]:
left = mid
else:
right = mid
it still works right? the answer is MID but LEFT > MID, we capture the minimum already by doing min(res, nums[mid]) before comparing LEFT > MID... the minimum will remain as 1 throughout the entire loop. Your answer is a little better as we don't need to store a variable for the mininum value and perform a comparison to get the minumum value per loop. Great job!
Hey GUstavo, thanks for your insight! I would love to talk to you more about problem solving. Is it possible I can contact you in any way like DIscord or Twitter?
I have a simpler alternative that allows you to not keep track of the minimum, here it is:
class Solution:
def findMin(self, nums: List[int]) -> int:
start, end = 0, len(nums) - 1
while start - end > 1: # if middle exists
mid = (start + end) // 2
if nums[mid] > nums[end]:
start = mid + 1
else:
end = mid
return min(nums[start], nums[end])
Unfortunately this algorithm does not work for test cases such as:
[2,1] or
[3,1,2]
class Solution {
public:
int findMin(vector& nums) {
sort(nums.begin(),nums.end());
return nums[0];
}
};
since the best sorting algorithm is nlogn , your solution is going to be nlogn , which is worse than linear search(n) let alone binary search (logn)
I did this solution quite different by checking if middle is < middle-1 I can itentify the lowest number:
def findMin(self, nums: list[int]) -> int:
l, r = 0, len(nums) - 1
while l nums[r]:
l = middle+1
else:
r = middle-1
return nums[l]
Why do we update res on line 12 after getting the middle point?
mid pointer is always pointing to the potential minimum value in the array. Therefore, you want to keep updating the res variable to be checked against the new mid pointer value each iteration.
Check the case discussed from 9.06. that will answer why we need to update res.
If res would not have been updated, we would get min as 3 instead of 1 in this case.
i think you should clarify what right portion and left portion is if you're referring to the original array sorted
absolutely
Doesn't initializing right pointer to the end of the array itself take O(n) time? Languages like Python might have under the hood optimizations to do this more efficiently, but from algorithmic perspective, if we have to iterate through the array once to initialize the right pointer, wouldn't it be more efficient to just find the minimum in that iteration itself?
My solution which I think is more intuitive:
class Solution:
def findMin(self, nums: List[int]) -> int:
start , end = 0 ,len(nums) - 1
curr_min = float("inf")
while start < end :
mid = (start + end ) // 2
if(nums[mid+1] < nums[mid]):
return nums[mid+1]
# right has the min
if nums[mid] > nums[end]:
start = mid + 1
# left has the min
else:
end = mid
return nums[start]
I had something similar.
Nice Explanation!!
Another approach in O(logn) time will be Two pointer strategy, I solved it using the following approach
Thanks
while(l Think why!
else h = mid;
}
}
For anyone who is struggling, I break these type of questions to 2 cases. (mid is in sorted sub_array, mid is not in sorted_subarray). Write cases accordingly!
Not sure why, but simply using "return min(nums)" (in Python) seems to run faster than the binary search algorithm solution.
what is "min" doing under the hood?
*'min' use O(N) time to search for the minimum element in an array.
* It uses linear search.
* The time taken shown in leetcode doesn't provide you the actual time taken.
@@adarshvats8003 but in this solution, instructor used min function so what's point of using in code then using in first place.
@@vaishaliagrawal4781 min(array) gives you minimum of array in O(N) but if we write min(x, y) gives minimum in O(2) which is a linear operation.
Thus the code still remains O(logn).
I hope this helps!!
@@adarshvats8003 Thanks, make sense
Is the EQUAL SIGN in "(nums[l] >= nums[m])" ONLY for the case of an input like [2,1] where l=0, m=(0+1)//2 = 0 but we randomly need to check the other index value too "just because" (outside of our actual defined rules we've outlined)... just to make sure?
easy way : while l < r:
m = (l + r) // 2
if nums[m] > nums[r]:
l = m + 1
else:
r = m
return nums[l]
This is for sorted and not rotated array iguess
@@numanali8545 No it is for rotated!
@@KumarMukand-dm9iw that is such a more concise solution, thanks!
MORE EASIER WAY!
def findMin(self, nums: List[int]) -> int:
res = float("inf")
l, r = 0, len(nums) - 1
while l nums[r]:
l = m + 1
else:
r = m - 1
return res
you can just return nums[L] at the end and avoid the res
Why do we need line 12, `res = min(res, nums[m])`?
Wouldn't it be caught if we just assigned `l = m` or `r = m` instead of `= m ± 1`?
I think because it saves time. Example has just 5 inputs so it might seem to be less useful.
@@ganeshkamath89 I've been practicing it without storing the minimum result for a few months now. I don't think you need to store the minimum. I just return the `nums[m]` value.
@@PippyPappyPatterson Thanks. You are right. I tried this code change and it worked for me also 😀
@@ganeshkamath89 ofc, good luck internet traveler
The code presented in the video is incorrect, it's different from even the Python code submitted on the website. Can you please fix the video?
def findMin(self, nums: List[int]) -> int:
bad = -1
good = len(nums) - 1
while good - bad > 1:
candidate = (bad + good) // 2
if nums[candidate] < nums[good]:
good = candidate
else:
bad = candidate
return nums[good]
No need to do any storing and comparing.
Simple Binary searching here..
def findMin(nums,l,h):
mid= (l+h)//2
if(nums[l]nums[h]):
return h
return findMin(nums,l,mid)
You mention that the left sorted portion is always going to have values > the right sorted portion. In the event that the array has not been rotated or rotated n - 1 times (which would produce the same array) then wouldn't that statement not be true? Ex: [0,1,2,3,4,5,6,7] ... m = array[4] ... array[4] == 3 ... 3 >= 0 ... we are in the left sorted portion ... all values of the right sorted portion are greater than the left. Maybe I am confused but if someone could clarify I would greatly appreciate it.
Sorry at 8:00 he cleared this up. In the event that left < right then we are in a sorted array. Given left < result then result = left return result.
The funny thing is I test my naive solution which o(n) in Javascript:
function min(nums) {
return Math.min(...nums);
}
and it beats 23% of other solutions which used binary search 🤣
What about this [5,1,2,3,4,]
Not every value in the left portion is bigger than in the right portion
Is it safe to assume that if a search requires O(log n) time and the list is ordered. It's most likely a binary search in some flavor or another?
it's in fact 100% binary search
lost when you just assume mid will be at 1? how can you explain the set up
C++ solution:
class Solution {
public:
int findMin(vector& nums) {
int i = 0 ;
int j = nums.size() - 1;
int mid = (i+j)/2;
if(nums.size()==1)
{
return nums[0];
}
/*
idea: use binary search.
If the value to left of mid is smaller than the right pointer, then
move right pointer to mid
Otherwise, move left pointer to mid
*/
while(i
Thank you very much man
Can I use same algorithm as search in rotated sorted array
Hey, I had quick question. Since the problem statement asks us to solve this in O(logn), don't you think using min() function (which O(m)) make this O(mlogn) ?
Ahh, got it. min() for two values is O(1). Thanks
Your videos are the best
```
def findMin(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
while (left < right):
mid = (left+right)//2
if (nums[mid]
I hope you can make a video about Binary Search Templates and help us understand it better. Thank you.
class Solution:
def findMin(self, nums: List[int]) -> int:
low, high = 0, len(nums) - 1
while low < high:
mid = (low + high) // 2
if nums[mid] < nums[high]:
high = mid
elif nums[mid] > nums[high]:
low = mid + 1
return nums[high] #nums[low]
U a BST God🎉
Good explanation, however, I think we can improve it keeping L and R, but looping length/2 times in both direction, if nums[L] > nums[L+1] then L is the position of the minimum or if nums[R] < nums[R-1] then position R holds the minimum:
// C#
for (int i = 0, j = nums.Length - 1; i < nums.Length / 2; i++, j--)
{
if (nums[i] > nums[i + 1]) return nums[i + 1];
if (nums[j] < nums[j - 1]) return nums[j];
}
return nums[0];
you're supposed to solve it in logarithmic time
class Solution:
def findMin(self, nums: List[int]) -> int:
low, high = 0, len(nums) - 1
while low < high:
mid = (low + high) // 2
if nums[mid] > nums[high]:
low = mid + 1
else:
high = mid
return nums[low]
I tried this too which I thought was great, but it doesn't work for this list:
nums = [12, 0, 1, 2, 3, 4, 5, 6, 9, 10, 11]
Sorry, I was returning m (mid variable) instead of l (low variable).
thanks, clear illustration
Waiting for your 752. Open the Lock video. Thanks in advance.
ur in luck he just uploaded it
after the condition if nums[m] >= nums[l]: you need to update res to nums[l] because according to the condition it is less than nums[m](our current res) and this is the last time we'll be visiting the current nums[l] (since we update l to m+1)
We are always terminating if nums[l] < nums[r] to handle this, so there is no need to explicitly check nums[l] at each iteration. For instance if nums[m] >= nums[l] we know that nums[l] is also greater than or equal to nums[r] (because we checked this condition first)... therefore there is no way nums[l] at that point will be the minimum result since there is a smaller value on the right side of the array and we update l to mid + 1 to search the right side.
Put more simply... because we always check nums[l] < nums[r] we are always guaranteed to terminate and set the result to nums[l] if nums[l] is ever the min.
It does not work for case when minimum is at mid. e.g: [3,1,2]
does it even work for [1,2,3] ?
Thank you!
Thank you for your valuable time. I really appreciate.
If anyone is looking for Java Code:
public static int findMinimum(int[] input) {
if (input == null || input.length == 0) {
throw new IllegalArgumentException("Invalid input passed");
}
int left = 0, right = input.length - 1, mid = 0;
while (left != right) {
mid = (left + right) / 2;
if (input[mid] >= input[left]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return input[mid];
}
class Solution:
def findMin(self, nums: List[int]) -> int:
try:
for ele in range(len(nums)):
if nums[ele] > nums[ele+1]:
return nums[ele+1]
except:
return nums[0]
return min(nums) works as well
no its doesn't, that's not log n time complexity, thats n. Even though it passes in leetcode it's wrong due to the problem constraints.
Great explanation!
return min(nums) did the trick for me but I don't think thats intended
No because that is not in O(log n)
@@Rahul-eh3rf What about my code here:
l, r = 0, len(nums) - 1
while l < r:
if nums[r] > nums[r - 1]:
r -= 1
elif nums[r] < nums[r - 1]:
return min(nums[l], nums[r])
if l == r:
return nums[l]
# if nums[r] can move down then keep nums[l]
# if nums[r] cannot move down compare value with nums[l] and return smallest value
# if index l and index r are the same, return nums[l]
everything fine? It passes all test cases but not sure if O(log n).
@@Lambyyy It's O(n) because you are essentially comparing every num against left num. A O(logn) solution is possible here if the problem size is halved every step.
@@tahsinamio2639 Ah okie, thank you!
Why does it not work for [3,2 ]?
Isn't the time complexity of min() function O(n), which kinda defeats the purpose of using binary search to find the solution in O(logn)? If we must use min(), we can just do `return min(nums)` at that point?
Someone please explain, I am a little confused. Thanks!
when using min(x,y) for only two values, it is constant time but if you give it a list, it will be O(n)
@@Shonia Oh that makes sense - thank you!
here we are doing r=mid instead of r=mid-1?
I did Arrays.sort(nums);
return nums[0]; :D :D
hm..does len(arr) count as time complexity of O(N)?
damn this problem broke my brain for some reason lol
int low = 0, high = arr.size() - 1;
int ans = INT_MAX;
while (low
Bro breathe
Why
You're the best
If an array is rotated to the its size times then this may verdict your answer
what does 'verdict' your answer mean?
@@djSubzz the answer may be wrong.
Isn't binary search already log(n) why not just sort it?
Oh sorting is nLog(n)
You are awesome
thnak you
My gawd, every one of these binary search problems I get some edge cases wrong due to these tiny but important details of settings r = m (instead of m - 1) or having l start from 1 instead of 0 (koko eating bananas). It's super frustrating
don't worry you'll get there. one step at a time
@@jasonahn8658thanks man.
May I know why you use // instead of / in m.
In python a single '/' will evaluate to decimal division (e.g. 1 / 2 = 0.5), where as '//' evaluates to integer division which is the default for most languages (e.g. 1 / 2 = 0)
Why not implement the binary search recursively rather than using the while loop? It's still O(logn) right?
I believe it is done in this to limit the stack usage.
2:29
3:18
8:05
min(nums) got accepted)
Such a great explanation!
Can you do binary cameras tree leetcode?
understood
Thanks for the explanation. One point of feedback I would recommend is to cut down or outright stop saying the word "right" when you're not talking about the direction. It can get confusing in problems in which the left/right directions are crucial to explaining the solution (e.g. this solution or tree related solutions).
Every time you say "right", we have to differentiate between the direction and you confirming something which just adds extra noise to your explanation
Good point for some people.
For me, I am used to his kind of speech pattern and maybe being a native English speaker it helped me not be distracted by it, but it could be a problem for ESL people or just for people who don't speak/think in that pattern.
Learning is already complicated, so additional barriers when unnecessary can be frustrating.
Did not understand at first so confused
please code using c++ too
1 line solution,
just ""return min(nums)" thats it
bro o(logn) is the requirement. you are mentioning o(n) approach
gd video!
I like all of your videos I watched so far except this one. You talked too fast, and I'm lost where you said if the middle is 1 then search on the left.