[Programming Problem] Find Minimum in Rotated Sorted Array II

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

  • [4,5,6,7,0,1,4] if it was rotated 4 times.
  • [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Example 1:
Input: nums = [1,3,5]
Output: 1

Example 2:
Input: nums = [2,2,2,0,1]
Output: 0

[Problem Link]

We use a `modified` binary search to find the minimum element:-

  • At every point, compare (‘i’, ‘mid’) with (‘mid+1’, ‘j’). Whichever section has the lower value, let’s move that direction. Because of duplicates, we might be in a situation where there’s no one clear winner. In that case, move in both directions.
    if ( (a < c && a < d) || (b < c && b < d) ) // go left
    else if ((c > a && c > b) || (d > a && d > b)) // go right
    else // go both directions.
  • Return the last number remaining in the recursion (when i === j)
 * @param {number[]} nums
 * @return {number}
var findMin = function(nums) {
    return findMinRecursive(nums, 0, nums.length-1);
var findMinRecursive = function(nums, i, j) {    
    if (i === j) return nums[i];
    let mid = i + Math.floor((j-i)/2);
    const a = nums[i];
    const b = nums[mid];
    const c = nums[mid + 1];
    const d = nums[j];
    let left = Number.MAX_VALUE;
    let right = Number.MAX_VALUE;
    if ((a < c && a < d) || (b < c && b < d)) {
        // go left
        left = findMinRecursive(nums, i, mid);
    } else if ((c > a && c > b) || (d > a && d > b)) {
        right = findMinRecursive(nums, mid+1, j);
    } else {
        // go both
        left = findMinRecursive(nums, i, mid);
        right = findMinRecursive(nums, mid+1, j);
    return Math.min(left, right);

17 thoughts on “[Programming Problem] Find Minimum in Rotated Sorted Array II

  1. I have to point out my affection for your generosity supporting people who really want help on this one niche. Your real dedication to passing the message along came to be certainly good and has constantly permitted girls like me to achieve their endeavors. Your entire invaluable help and advice can mean a whole lot a person like me and much more to my colleagues. Regards; from each one of us.

  2. My spouse and i got really satisfied when Michael could deal with his web research through the ideas he made through the web page. It’s not at all simplistic to simply continually be making a gift of helpful hints most people could have been selling. And we all do know we now have you to thank for that. All the explanations you made, the straightforward site navigation, the relationships you can give support to promote – it’s got mostly astounding, and it is leading our son and us believe that the matter is exciting, which is tremendously vital. Many thanks for all the pieces!

  3. I want to show my thanks to you just for bailing me out of this type of challenge. Just after looking out through the online world and getting views that were not helpful, I thought my entire life was done. Existing devoid of the approaches to the difficulties you have resolved through your main report is a critical case, as well as the kind which might have badly affected my entire career if I hadn’t noticed the blog. Your actual talents and kindness in taking care of all the stuff was excellent. I don’t know what I would’ve done if I had not encountered such a step like this. I can also now look forward to my future. Thanks for your time very much for this reliable and sensible help. I will not think twice to refer the blog to anybody who needs and wants direction about this subject.

  4. I would like to express my passion for your kindness supporting those people that actually need help with this subject. Your real dedication to getting the solution all over has been astonishingly interesting and has allowed somebody much like me to realize their desired goals. Your own helpful instruction means a lot a person like me and far more to my mates. Best wishes; from each one of us.

  5. Needed to compose you that bit of observation to be able to give many thanks yet again on your precious opinions you’ve featured in this article. It was certainly strangely generous of people like you to give unhampered exactly what most people would’ve sold as an e book to help make some profit for their own end, principally given that you might well have tried it if you ever considered necessary. Those principles likewise served to become good way to fully grasp that the rest have a similar passion really like my personal own to know the truth great deal more on the topic of this problem. I know there are a lot more pleasurable periods ahead for individuals that look over your site.

  6. Thank you a lot for providing individuals with such a pleasant chance to read in detail from here. It is always very pleasurable and also stuffed with a great time for me and my office fellow workers to search the blog minimum three times in 7 days to see the fresh stuff you have got. And lastly, we’re at all times satisfied for the fantastic hints you give. Some 4 ideas in this article are without a doubt the very best I have ever had.

  7. I not to mention my pals have been reviewing the good recommendations found on your site and then instantly came up with a horrible feeling I never thanked you for those secrets. Those ladies came for this reason warmed to study all of them and now have absolutely been making the most of those things. Appreciate your simply being well helpful and also for utilizing this kind of remarkable areas millions of individuals are really wanting to be aware of. Our sincere regret for not expressing gratitude to you sooner.

  8. I must point out my passion for your kind-heartedness giving support to folks who need assistance with this one content. Your personal commitment to getting the message all over has been extraordinarily advantageous and has surely made professionals like me to realize their targets. Your personal helpful guide indicates a whole lot a person like me and even further to my colleagues. Thanks a lot; from each one of us.

  9. My husband and i were really happy Raymond managed to complete his homework through the entire ideas he made through the web page. It’s not at all simplistic just to happen to be freely giving secrets and techniques which usually other folks might have been selling. And we all grasp we have got the blog owner to appreciate for that. The entire illustrations you have made, the straightforward web site menu, the relationships you can make it possible to foster – it’s got many great, and it is facilitating our son and the family consider that that topic is cool, which is pretty serious. Thanks for the whole lot!

  10. Thank you a lot for providing individuals with remarkably memorable chance to read critical reviews from here. It is usually very ideal and full of a lot of fun for me personally and my office mates to search your website at minimum three times in one week to see the new tips you have got. And of course, we’re certainly fascinated for the very good principles you give. Certain 4 facts in this post are truly the most suitable we have all had.

  11. I want to show my admiration for your kind-heartedness giving support to those individuals that should have guidance on this field. Your personal dedication to passing the message around turned out to be especially informative and has continuously made those much like me to reach their targets. Your personal insightful tips and hints can mean so much to me and far more to my office workers. Best wishes; from each one of us.

  12. I needed to draft you one little bit of note to help say thank you as before with the stunning ideas you have discussed on this page. It’s so wonderfully generous of people like you in giving easily what exactly a few individuals might have distributed as an electronic book to help make some cash for their own end, certainly considering that you could possibly have tried it if you decided. Those tactics likewise worked to provide a good way to fully grasp that other people have a similar interest similar to my very own to understand a lot more pertaining to this issue. I am sure there are numerous more pleasant times up front for individuals who go through your website.

  13. I’m also writing to let you be aware of of the exceptional experience my girl experienced using your site. She came to find numerous things, most notably how it is like to have a marvelous coaching nature to get folks completely understand several very confusing topics. You undoubtedly exceeded our expected results. Many thanks for delivering those helpful, healthy, revealing and as well as fun thoughts on the topic to Evelyn.

  14. Needed to write you that very small word to finally thank you so much once again on the precious secrets you have provided in this case. This is certainly wonderfully generous of people like you to deliver publicly exactly what a lot of folks would’ve offered for an e book to make some profit on their own, even more so now that you might well have done it in case you considered necessary. These creative ideas also served to be the good way to be aware that other people have similar fervor really like my own to figure out much more with respect to this problem. I’m certain there are a lot more pleasurable periods up front for those who examine your site.

Leave a Reply

Your email address will not be published. Required fields are marked *