Find Minimum in Rotated Sorted Array II LeetCode Solution

Problem – Find Minimum in Rotated Sorted Array II LeetCode Solution

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

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums is sorted and rotated between 1 and n times.

Follow up: This problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Find Minimum in Rotated Sorted Array II LeetCode Solution in Python

class Solution(object):
def findMin(self, nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi -lo) / 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid if nums[hi] != nums[mid] else hi - 1
    return nums[lo]

Find Minimum in Rotated Sorted Array II LeetCode Solution in Java

public int findMin(int[] nums) {
	 int l = 0, r = nums.length-1;
	 while (l < r) {
		 int mid = (l + r) / 2;
		 if (nums[mid] < nums[r]) {
			 r = mid;
		 } else if (nums[mid] > nums[r]){
			 l = mid + 1;
		 } else {  
			 r--;  //nums[mid]=nums[r] no idea, but we can eliminate nums[r];
		 }
	 }
	 return nums[l];
}

Find Minimum in Rotated Sorted Array II LeetCode Solution in C++

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r && nums[l] > nums[r]) {
            int m = l + (r - l) / 2;
            if (nums[m] > nums[m + 1]) {
                return nums[m + 1];
            }
            if (nums[m] > nums[r]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return findMin(nums, l, r);
    }
private:
    int findMin(vector<int>& nums, int l, int r) {
        int mini = nums[l++];
        while (l <= r) {
            mini = min(mini, nums[l++]);
        }
        return mini;
    }
};

Find Minimum in Rotated Sorted Array II LeetCode Solution Review:

In our experience, we suggest you solve this Find Minimum in Rotated Sorted Array II LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Find Minimum in Rotated Sorted Array II LeetCode Solution

Find on Leetcode

Conclusion:

I hope this Find Minimum in Rotated Sorted Array II LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions