{x}
blog image

Find Minimum in Rotated Sorted Array II

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?

 

Solution Explanation: Finding Minimum in Rotated Sorted Array II

This problem asks to find the minimum element in a rotated sorted array that may contain duplicates. A standard binary search approach needs modification to handle duplicates efficiently.

Approach:

The core idea is similar to finding the minimum in a rotated sorted array without duplicates. We use binary search to narrow down the search space. However, the presence of duplicates introduces a crucial difference: when nums[mid] == nums[right], we can't definitively determine whether the minimum lies in the left or right half. In this case, we simply decrement right to move closer to the potential minimum.

Algorithm:

  1. Initialization: Set left = 0 and right = len(nums) - 1.

  2. Iteration: While left < right:

    • Calculate mid = (left + right) // 2.
    • Case 1: nums[mid] > nums[right]: The minimum element must be in the right half (mid + 1 to right), since the rightmost element is smaller than the middle element, which implies a rotation point exists in the right half.
    • Case 2: nums[mid] < nums[right]: The minimum element must be in the left half (left to mid), as the middle element is smaller than the rightmost element, suggesting the minimum is somewhere to the left.
    • Case 3: nums[mid] == nums[right]: Duplicates exist. We cannot confidently decide which half contains the minimum. To avoid getting stuck in an infinite loop, we decrement right by 1. This is safe because if the minimum is nums[right], we'll find it in the next iteration. If the minimum is not nums[right], it doesn't change the outcome.

  3. Return: When left == right, we have found the minimum element. Return nums[left].

Time Complexity Analysis:

The worst-case time complexity is O(n) because in scenarios where there are many duplicate elements, and the duplicates are concentrated in the sorted part of the array, the nums[mid] == nums[right] condition may be repeatedly triggered, leading to a linear scan in the worst case. This contrasts with the O(log n) complexity of the problem's non-duplicate version. The best-case scenario is still O(log n).

Space Complexity Analysis:

The space complexity is O(1) because the algorithm uses only a constant amount of extra space for variables like left, right, and mid.

Example Walkthrough (with duplicates):

Let's trace the algorithm with nums = [2, 2, 2, 0, 1].

  1. left = 0, right = 4.
  2. mid = 2. nums[mid] = 2, nums[right] = 1. nums[mid] > nums[right], so left = 3.
  3. left = 3, right = 4.
  4. mid = 3. nums[mid] = 0, nums[right] = 1. nums[mid] < nums[right], so right = 3.
  5. left = 3, right = 3. The loop terminates.
  6. The function returns nums[3], which is 0.

The provided code in various languages implements this algorithm effectively. Each implementation follows the same logical steps, efficiently handling the potential for duplicates.