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

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@justinpardo-mw8wy]

this was so good i tried looking at other explanations but it felt like it went against my intuition for solving the problem this was perfect

[@GregHogg]

Really happy you enjoyed it!

[@hinocenciopaulo]

That was a beautiful approach, so precise and simple. Excellent job sir. Thank you for sharing.

[@GregHogg]

Very glad you enjoyed it!

[@DeepakGupta-zz1vf]

All sorted rotated arrays have one thing in common that is there will be atleast one sorted half for sure This can be proved by taking 5 elements and all its possible rotations and then see how left,mid and right varies Post that we will come to the above mentioned conclusion Now using this technique one can easily solve any variant problem related to sorted rotated array

[@donghyunsuh4469]

I think the explanation was very intuitive. Thank you!

[@JoeTan-nq4fq]

A sllightly faster way (but longer code) - Each time after finding nums[m], check its neighbour. If the value to the right is lower, it means it is the first element of the original array. If the value to the left is higher, it means it is the last element of the original array. If both of these conditions are not met, narrow the search by half. l, r = 0, len(nums) - 1 while l < r: mid = (l + r) // 2 # Since original array is ascending, # a lower right value means it is the first element if nums[mid+1] < nums[mid]: return nums[mid+1] # a higher left value means it is the last element elif nums[mid-1] > nums[mid]: return nums[mid] # Narrow the search by half if nums[mid] > nums[r]: l = mid + 1 else: r = mid - 1 return nums[l] # To handle single element array

[@md-ayaz]

simple and neat solution. Thank you.

[@enryost1059]

you're the goat, thank you for this video!

[@devpragmatico]

Very good explanation. Thank you

[@nav213]

First of all thank you so much for the videos! I am a big fan. Secondly, it's one of those questions that you need to memorize because I couldn't get it when I tried to do it by myself.

[@GregHogg]

That's so sweet! And yeah this one is definitely tricky lol

[@skyaqa2108]

Hi there, in one of your videos you mentioned the order of types of ds we should follow and solve because they are prerequisite for others, why you don't do the same, for example start with 5 problem from the first one to ... 5 problem of last one(dyn programming was the last one, i remember), and in the end of solving each problem recommend 5 similar important problems for practice It would be really helpful if you do that instead of just randomly solving problem, inform us about what you think about this idea Thanks

[@sumanthreddykarri]

class Solution(object): def findMin(self, nums): if nums: nums.sort() else: return False return nums[0] nums = [4,5,6,7,0,1,2] solution=Solution() print(solution.findMin(nums))

[@giancarlokuosmanen9723]

You are defeating the purpose of the task by sorting it It is a binary search problem.

[@anirbandas12]

Make a video for the find target when sorted arr is rotated problem too

[@sharukhsm007]

Why is M = 6 when it's actually 7 in your example?

[@GregHogg]

Sorry did I get something wrong here?

[@adithyar3160]

luvd it mate

[@GregHogg]

Super glad to hear it ☺️

[@fadygamilmahrousmasoud5863]

another solution is : pushing the items into max-heap then loop through the heap values -> pop the root as long as the heap has more than one value left, once the heap has one value left, its the min value return it and done but its nLongn I guess