Find Minimum in Rotated Sorted Array II LeetCode Solution

Last updated on January 29th, 2025 at 02:12 am

Here, we see a Find Minimum in Rotated Sorted Array II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Binary Search

Level of Question

Hard

Find Minimum in Rotated Sorted Array II LeetCode Solution

Find Minimum in Rotated Sorted Array II LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Modified Binary Search. This pattern is a variation of the standard binary search algorithm, where the search space is adjusted based on specific conditions. In this case, the code is designed to find the minimum element in a rotated sorted array by leveraging the properties of binary search.

3. Code Implementation in Different Languages

3.1 Find Minimum in Rotated Sorted Array II C++

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int low=0, high=n-1;
        
        while(low<high){
            if(nums[low] <= nums[high]) return nums[low];
            int mid = low + (high-low)/2;
            if(nums[low] > nums[mid]){
                high=mid;
            } else if(nums[mid] > nums[high]) {
                low=mid+1;
            } 
        }
        if(nums[low] <= nums[high]) return nums[low];
        return -1;
    }
};

3.2 Find Minimum in Rotated Sorted Array II Java

class Solution {
  public int findMin(int[] nums) {
    int l = 0;
    int r = nums.length - 1;

    while (l < r) {
      final int m = (l + r) / 2;
      if (nums[m] < nums[r])
        r = m;
      else
        l = m + 1;
    }

    return nums[l];
  }
}

3.3 Find Minimum in Rotated Sorted Array II JavaScript

var findMin = function(nums) {
    var left = 0,
        right = nums.length - 1
    
    while (left < right){
        var mid = Math.floor((left + right)/2)
        if (nums[mid] > nums[right]) left = mid + 1
        else right = mid
    }
    return nums[left]
};

3.4 Find Minimum in Rotated Sorted Array II Python

class Solution:
    def findMin(self, num):
        first, last = 0, len(num) - 1
        while first < last:
            midpoint = (first + last) // 2
            if num[midpoint] > num[last]:
                first = midpoint + 1
            else:
                last = midpoint
        return num[first]

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(log n)O(1)
JavaO(log n)O(1)
JavaScriptO(log n)O(1)
PythonO(log n)O(1)
  • The logic is consistent across all four implementations (C++, Java, JavaScript, Python), with minor syntactic differences.
  • The algorithm is efficient for finding the minimum in a rotated sorted array due to its logarithmic time complexity.
  • The space complexity is optimal as it does not require any extra memory allocation.
Scroll to Top