Find Minimum in Rotated Sorted Array II

HARD

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?

Approaches

Checkout 2 different approaches to solve Find Minimum in Rotated Sorted Array II. Click on different approaches to view the approach and algorithm in detail.

Linear Scan

This is a straightforward brute-force approach. We can find the minimum element by simply iterating through the entire array and keeping track of the smallest value encountered.

Algorithm

Initialize minimum to nums[0].
Loop through the array from the second element (i = 1) to the end.
Inside the loop, if nums[i] is less than minimum, update minimum = nums[i].
After the loop, return minimum.

The algorithm works by initializing a variable, say minimum, with the value of the first element of the array. It then traverses the array from the second element to the end. For each element, it compares it with the current minimum. If the current element is smaller, minimum is updated. After checking all elements, the minimum variable will hold the smallest value in the array. This approach does not take advantage of the fact that the array is a rotated sorted array, but it is guaranteed to be correct.

class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1; // Based on constraints, this won't be reached.
        }
        
        int minimum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < minimum) {
                minimum = nums[i];
            }
        }
        return minimum;
    }
}

Complexity Analysis

Time Complexity: O(n)Space Complexity: O(1)

Pros and Cons

Pros:

Very simple to understand and implement.
Works for any array, not just rotated sorted ones.

Cons:

Inefficient as it doesn't use the properties of the input array.
Has a time complexity of O(n), which can be improved upon.

Code Solutions

Checking out 4 solutions in different languages for Find Minimum in Rotated Sorted Array II. Click on different languages to view the code.

class Solution {
public
  int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] > nums[right]) {
        left = mid + 1;
      } else if (nums[mid] < nums[right]) {
        right = mid;
      } else {
        --right;
      }
    }
    return nums[left];
  }
}

Video Solution

Watch the video walkthrough for Find Minimum in Rotated Sorted Array II

Algorithms:

Binary Search

Data Structures:

Array

Companies:

Google |