Skip to content

153. Find Minimum in Rotated Sorted Array

Description

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.

 

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All the integers of nums are unique.
  • nums is sorted and rotated between 1 and n times.

Solutions

Thinking

A rotated sorted array with distinct values; a linear scan is \(O(n)\) and \(n\le 5000\) is fine, but order allows \(\log n\). The minimum splits the array into two increasing runs. Compare the mid to the last value: larger means the min is on the right, otherwise on the left (including mid). Shrink to one index.

We can use binary search to solve this problem.

First, we define two pointers \(l\) and \(r\) pointing to the start and end of the array respectively. Then we enter a loop until \(l\) is no longer less than \(r\).

In each iteration, we calculate the middle position \(mid\) and compare \(nums[mid]\) with \(nums[n-1]\). If \(nums[mid]\) is greater than \(nums[n-1]\), the minimum value is to the right of \(mid\), so we update \(l\) to \(mid + 1\). Otherwise, the minimum value is at \(mid\) or to its left, so we update \(r\) to \(mid\). When the loop ends, pointer \(l\) will point to the minimum value, and we return \(nums[l]\).

The time complexity is \(O(\log n)\), where \(n\) is the length of array \(\textit{nums}\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] > nums[-1]:
                l = mid + 1
            else:
                r = mid
        return nums[l]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > nums[nums.length - 1]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return nums[l];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > nums.back()) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return nums[l];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func findMin(nums []int) int {
    l, r := 0, len(nums)-1
    for l < r {
        mid := (l + r) >> 1
        if nums[mid] > nums[len(nums)-1] {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return nums[l]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function findMin(nums: number[]): number {
    let l = 0,
        r = nums.length - 1;
    while (l < r) {
        let mid = (l + r) >> 1;
        if (nums[mid] > nums[nums.length - 1]) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return nums[l];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn find_min(nums: Vec<i32>) -> i32 {
        let (mut l, mut r) = (0, nums.len() - 1);
        while l < r {
            let mid = (l + r) >> 1;
            if nums[mid] > nums[nums.len() - 1] {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        nums[l]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
    let l = 0,
        r = nums.length - 1;
    while (l < r) {
        let mid = (l + r) >> 1;
        if (nums[mid] > nums[nums.length - 1]) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return nums[l];
};

Comments