Microsoft Coding Interview Question - Find Minimum in Rotated Sorted Array - Leetcode 153

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[GregHogg]

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

[axhraf]

hmm this solution seems a lot more simple than Neetcode’s 🤔

[rids]

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

[mohamedfarid]

Wouldn't the answer always be arr[n/ 2 + 1] ?

[pradyumnachakraborty]

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.

[vasylshkrum]

Why not just iterate till n>n+1? And if halfs rotated, we can start iterating from (n/2)-1. Will it work?

[ashishkumarsingh]

What if elemnets in array have duplicates. How the approach will change

[kinjalbhar]

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

[tylerp.]

I don’t understand why wouldn’t you just iterate thru the array and return lowest value?

[nayanraut]

You took a sorted array in which both the sides of mid are sorted .what if they aren't?

[elthetruth]

Is this guy the programmer from Ex Machina?

[oreokapoor]

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🎉

[thefattysplace]

I can't think of any real world applications for this?

[maervo]

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 😂🤔