Find Minimum in Rotated Sorted Array - Binary Search - Leetcode 153 - Python

0:00 - Read the problem
1:34 - Drawing Explanation
10:10 - Coding Explanation

leetcode 153

#rotated #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[world]

I've watched this video probably 10-15 times over different days, and only now is it starting to make sense. Bless.

[camoenv]

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]

[TheOtrama]

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 YouTubers because I know that your explanations are the best. Thank you for this quality content!

[hrvmhv]

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

[evynsrefuge]

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

[ggmadmax]

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]<nums[e]
therefore, e=mid-1

Iteration 3:
s=4
e=4
mid=4
Here, we are at the minimum element so return it

This change is used to tackle an edge case where we are already in a sorted array. (hence removing the if condition)
In this example, at iteration 2, subarray [0, 1, 2] is sorted. If we checked mid pointer with left we would get subarray [2] but we checked mid pointer with right so we got sub array [0]

[sergiofranklin]

more consice solution:

def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums)-1

while l<r:
mid = (l+r)//2

if nums[mid]>=nums[r]:
l = mid+1
else:
r = mid
return nums[l]

[Byte-ul]

Just move right to mid, instead of mid -1 and you won't need to check for min result.

[symbol]

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..

[spageen]

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.

[DroidHolicOfficial]

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 <= end:
# If the "start" element is smaller than "end"
if nums[start] < nums[end]: return min(minimum, nums[start])

mid = start + (end - start) // 2

# IF this mid value is smaller than previous minimum we found
# Then update the minimum
minimum = min(minimum, nums[mid])

# If start, end and mid are all same e.g. if [3, 3, 0, 3] is the test case
# Then, we will simply decrement end pointer
if nums[start] == nums[mid] == nums[end]: end -= 1
# Otherwise, we check
# Is this "mid" value part of left sorted subarray or right sorted subarray?
# If this is part of the left sorted subarray, we will find minimum on right side
elif nums[mid] >= nums[start]: start = mid + 1
# Otherwise, we will find the minimum on the left side
else: end = mid - 1

[anaisliu]

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!

[ShubhamMishra-mzzw]

One of the best explanation of this problem. Thank you ❤

[rongrongmiao]

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.

[soltomoon]

This is one of the first medium problems that I correctly new the intuition. LETS GOO

[rmaskaban]

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<=r:
if nums[l]<nums[r]:
ans=min(ans, nums[l])
break
m= (l+r)//2
ans=min(ans, nums[m])
if nums[m]>=nums[l]:
l=m+1
# if l<len(nums):
# ans=min(ans, nums[l])
else:
r=m-1
return ans

[causalinference]

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]

[ritiksaxenaofficial]

Great explanation <3

Someone mentioned the following logic and it is also easy to understand.

1. Find the mid element i.e. mid = (low+high)/2
2. If the (mid+1)th element is less than mid element then return (mid+1)th element
3. If the mid element is less than (mid-1)th element then return the mid element
4. If the last element is greater than mid element then search in left half
5. If the last element is less than mid element then search in right half

[rustamkarimov]

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];
}

[khandokarsabbir]

Your explanation is very good. Line no 7, condition should be if (nums[l] <= nums[r]), i mean <= instead of <. My array was { 6, 7, 0, 1, 2, 3, 4, 5 }