Find Minimum in Rotated Sorted Array LeetCode Solution

Last updated on January 21st, 2025 at 02:13 am

Here, we see a Find Minimum in Rotated Sorted Array 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

Companies

Microsoft

Level of Question

Medium

Find Minimum in Rotated Sorted Array LeetCode Solution

Find Minimum in Rotated Sorted Array 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,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,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 of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

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 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 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 JavaScript

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

3.4 Find Minimum in Rotated Sorted Array Python

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

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)
Scroll to Top