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

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

Leave a Reply

Your email address will not be published.