Leetcode 154. Find Minimum in Rotated Sorted Array II
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.
- Python: With our Python solution, you will get:
1 2python 3s = Solution() 4print(s.findMin([2,2,2,0,1])) # Output: 0
- 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
- JavaScript: The JavaScript solution would provide:
1 2javascript 3let s = new Solution(); 4console.log(s.findMin([2,2,2,0,1])); // Output: 0
- 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
- 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!
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.