[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);
};

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

  15. I want to show my gratitude for your kind-heartedness in support of those people who require help with this one niche. Your special commitment to passing the message all around ended up being astonishingly useful and has always permitted somebody just like me to attain their desired goals. This valuable help denotes much to me and still more to my office workers. Best wishes; from everyone of us.

  16. I am glad for writing to let you know of the awesome discovery my wife’s child encountered using the blog. She figured out lots of issues, which included what it is like to have an incredible coaching character to let many people quite simply master specified problematic matters. You undoubtedly surpassed people’s expectations. I appreciate you for coming up with these warm and friendly, safe, informative and easy guidance on this topic to Emily.

  17. I have to voice my gratitude for your kind-heartedness for those people who actually need help on this particular niche. Your special commitment to getting the solution throughout became really informative and has consistently made women just like me to attain their desired goals. Your own warm and helpful recommendations entails this much a person like me and even more to my office workers. With thanks; from each one of us.

  18. Can I simply say what a aid to find someone who truly knows what theyre speaking about on the internet. You positively know the best way to deliver an issue to light and make it important. Extra people need to read this and understand this facet of the story. I cant imagine youre not more popular because you undoubtedly have the gift.

  19. Can I simply say what a reduction to search out somebody who really is aware of what theyre speaking about on the internet. You positively know the right way to convey a problem to gentle and make it important. More folks must read this and understand this facet of the story. I cant believe youre no more well-liked since you undoubtedly have the gift.

  20. I would like to voice my appreciation for your kind-heartedness for those who must have guidance on this particular concern. Your very own commitment to getting the message all through turned out to be rather powerful and has surely allowed most people like me to achieve their dreams. Your personal important tutorial denotes a whole lot a person like me and a whole lot more to my office colleagues. With thanks; from all of us.

  21. I in addition to my guys have been going through the great guides from the website and then quickly got a terrible feeling I never expressed respect to the blog owner for those techniques. All the women ended up absolutely warmed to see all of them and have in effect absolutely been taking pleasure in them. Many thanks for really being indeed thoughtful as well as for deciding upon varieties of important things most people are really desirous to be informed on. Our sincere apologies for not expressing appreciation to sooner.

  22. I must get across my affection for your kindness supporting people that require help on this particular content. Your very own commitment to passing the message throughout appeared to be remarkably effective and have surely allowed folks like me to arrive at their pursuits. Your warm and helpful advice implies a lot a person like me and much more to my office workers. With thanks; from everyone of us.

  23. My spouse and i were really peaceful Edward managed to finish off his research with the precious recommendations he gained out of your site. It’s not at all simplistic to simply possibly be giving freely steps that many some other people could have been trying to sell. We really understand we have got the writer to appreciate for that. Most of the explanations you have made, the easy blog navigation, the relationships your site help engender – it’s most terrific, and it’s facilitating our son in addition to the family understand the concept is cool, which is exceptionally mandatory. Thank you for all!

  24. I wanted to type a simple remark so as to thank you for these remarkable techniques you are sharing at this site. My particularly long internet search has at the end been recognized with reasonable information to exchange with my friends. I would express that many of us readers actually are unequivocally endowed to live in a great place with very many marvellous people with great tactics. I feel really fortunate to have seen your entire weblog and look forward to tons of more pleasurable times reading here. Thank you once again for a lot of things.

Leave a Reply

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