Skip to content

154. Find Minimum in Rotated Sorted Array II

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

Β 

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums is sorted and rotated between 1 and n times.

Β 

Follow up: This problem is similar toΒ Find Minimum in Rotated Sorted Array, butΒ nums may contain duplicates. Would this affect the runtime complexity? How and why?

Β 

Solutions

We define the left boundary \(l = 0\) and right boundary \(r = n - 1\) for binary search. Each iteration, we calculate the middle position \(mid = (l + r) \gg 1\) and compare the relationship between \(nums[mid]\) and \(nums[r]\):

  • If \(nums[mid] > nums[r]\), the minimum value is to the right of \(mid\), so we update \(l\) to \(mid + 1\).
  • If \(nums[mid] = nums[r]\), we cannot determine the position of the minimum value, but we can move \(r\) to the left by one position, i.e., \(r = r - 1\), to narrow down the search range.
  • If \(nums[mid] < nums[r]\), the minimum value is to the left of \(mid\) or at \(mid\) itself, so we update \(r\) to \(mid\).

When \(l\) and \(r\) meet, the pointer \(l\) points to the position of the minimum value, and we return \(nums[l]\).

The time complexity is \(O(n)\), as in the worst case where all elements in the array are the same, we need to traverse the entire array. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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[r]:
                l = mid + 1
            elif nums[mid] == nums[r]:
                r -= 1
            else:
                r = mid
        return nums[l]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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[r]) {
                l = mid + 1;
            } else if (nums[mid] == nums[r]) {
                r--;
            } else {
                r = mid;
            }
        }
        return nums[l];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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[r]) {
                l = mid + 1;
            } else if (nums[mid] == nums[r]) {
                r--;
            } else {
                r = mid;
            }
        }
        return nums[l];
    }
};

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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[r] {
                l = mid + 1;
            } else if nums[mid] == nums[r] {
                r -= 1;
            } else {
                r = mid;
            }
        }
        nums[l]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * @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[r]) {
            l = mid + 1;
        } else if (nums[mid] == nums[r]) {
            r--;
        } else {
            r = mid;
        }
    }
    return nums[l];
};

Comments