Problem Explanation:

Given an array that has been sorted in ascending order and then rotated at an unknown pivot, the task is to find the minimum element in this array. The array may contain duplicate numbers. We need to find an efficient solution even when the array contains duplicates.

For Example:

• Input: [1,3,5] Output: 1
• Input: [2,2,2,0,1] Output: 0

Approach:

We can use a modified Binary Search to solve this task. Start with the entire array and compare the middle element with the right-most element. If the middle element is smaller or equal to the right-most element, this means that the minimum element is on the left side of (or is) the middle element. Otherwise, the minimum element is on the right side of the middle element. We continue searching in the appropriate half in a similar way as in Binary Search. If the middle and right-most elements are equal, we cannot determine the side of the minimum element and decrease the right end by one.

Example:

If our rotated array is: [2,2,2,0,1]

Our aim is to find the minimum element in this array.

At the start,

• our left pointer (l) is at index 0,
• right pointer (r) is at index 4,
• and middle pointer (m) is at index 2 (calculated by (l+r)/2.) Array looks like this: Index: 0 1 2 3 4 [2, 2, 2, 0, 1] Points: ^ ^ ^ l m r

As array[m] and array[r] are both 2, we cannot determine which side the minimum element is. Hence, we decrease the right pointer. The array looks like this: Index: 0 1 2 3 [2, 2, 2, 0] Points: ^ ^ ^ l m r

Now, array[m] is 2 and array[r] is 0. As array[m] is greater than array[r], the minimum element is on the right side of m. We move the left pointer to m+1=3. Our array looks like: Index: 3 [ 0] Points: ^ l,r,m

Our left and right pointers meet at index 3. This means that the minimum element in our array is at index 3 and it is 0.

Below are the implementations of the problem in multiple programming languages.

Python Solution:

1
2python
3class Solution:
4    def findMin(self, nums):
5        #Defining left and right pointers
6        l, r = 0, len(nums)-1
7        #While loop until left pointer is less than right pointer
8        while l < r:
9            #Calculating middle pointer
10            m = (l + r) // 2
11            #If middle element is larger than right-most element
12            if nums[m] > nums[r]:
13                l = m + 1
14            #If middle element is smaller than right-most element
15            elif nums[m] < nums[r]:
16                r = m
17            #If middle element is equal to right-most element
18            else:
19                r = r - 1
20        #Return the minimum element
21        return nums[l]

Java Solution:

1
2java
3class Solution {
4    public int findMin(int[] nums) {
5        //Defining left and right pointers
6        int l = 0, r = nums.length - 1;
7        //While loop until left pointer is less than right pointer
8        while (l < r) {
9            //Calculating middle pointer
10            int m = l + (r - l) / 2;
11            //If middle element is larger than right-most element
12            if (nums[m] > nums[r]) {
13                l = m + 1;
14            }
15            //If middle element is smaller than right-most element
16            else if (nums[m] < nums[r]) {
17                r = m;
18            }
19            //If middle element is equal to right-most element
20            else {
21                r = r - 1;
22            }
23        }
24        //Return the minimum element
25        return nums[l];
26    }
27}

JavaScript Solution:

1
2javascript
3class Solution {
4    findMin(nums) {
5        //Defining left and right pointers
6        let l = 0, r = nums.length - 1;
7        //While loop until left pointer is less than right pointer
8        while (l < r) {
9            //Calculating middle pointer
10            let m = Math.floor((l+r) / 2);
11            //If middle element is larger than right-most element
12            if (nums[m] > nums[r]) {
13                l = m + 1;
14            }
15            //If middle element is smaller than right-most element
16            else if (nums[m] < nums[r]) {
17                r = m;
18            }
19            //If middle element is equal to right-most element
20            else {
21                r = r - 1;
22            }
23        }
24        //Return the minimum element
25        return nums[l];
26    }
27};

C++ Solution:

1
2c++
3class Solution {
4public:
5    int findMin(vector<int>& nums) {
6        //Defining left and right pointers
7        int l = 0, r = nums.size() - 1;
8        //While loop until left pointer is less than right pointer
9        while (l < r) {
10            //Calculating middle pointer
11            int m = (l + r) / 2;
12            //If middle element is larger than right-most element
13            if (nums[m] > nums[r]) {
14                l = m + 1;
15            }
16            //If middle element is smaller than right-most element
17            else if (nums[m] < nums[r]) {
18                r = m;
19            }
20            //If middle element is equal to right-most element
21            else {
22                r = r - 1;
23            }
24        }
25        //Return the minimum element
26        return nums[l];
27    }
28};

C# Solution:

1
2c#
3public class Solution {
4    public int FindMin(int[] nums) {
5        //Defining left and right pointers
6        int l = 0, r = nums.Length - 1;
7        //While loop until left pointer is less than right pointer
8        while (l < r) {
9            //Calculating middle pointer
10            int m = l + (r - l) / 2;
11            //If middle element is larger than right-most element
12            if (nums[m] > nums[r]) {
13                l = m + 1;
14            }
15            //If middle element is smaller than right-most element
16            else if (nums[m] < nums[r]) {
17                r = m;
18            }
19            //If middle element is equal to right-most element
20            else {
21                r = r - 1;
22            }
23        }
24        //Return the minimum element
25        return nums[l];
26    }
27}

Testing the solutions:

We have provided the solutions in multiple languages including Python, Java, JavaScript, C++ and C#. Now, let's test them with the given examples. We'll take the array [2,2,2,0,1] and see whether our solution correctly outputs the smallest number 0.

1. Python: With our Python solution, you will get:

1
2python
3s = Solution()
4print(s.findMin([2,2,2,0,1])) # Output: 0

2. Java: In Java, our solution will decode as:

1
2java
3Solution s = new Solution();
4System.out.println(s.findMin(new int[]{2,2,2,0,1})); // Output: 0

3. JavaScript: The JavaScript solution would provide:

1
2javascript
3let s = new Solution();
4console.log(s.findMin([2,2,2,0,1])); // Output: 0

4. C++: The C++ solution will provide:

1
2c++
3Solution s;
4vector<int> nums = {2,2,2,0,1};
5cout << s.findMin(nums) << endl; // Output: 0

5. C#: The C# solution would interpret as:

1
2C#
3Solution s = new Solution();
4Console.WriteLine(s.findMin(new int[]{2,2,2,0,1})); // Output: 0

Hopefully, this article provides a clear explanation about how to find the minimum element in a sorted and rotated array with duplicate elements. We have provided an efficient approach and its implementation in Code. Happy Coding!