We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Minimum in Rotated Sorted Array II

Number: 154

Difficulty: Hard

Paid? No

Companies: Microsoft, Google, Apple, Amazon

Problem Description

Given a rotated sorted array that may contain duplicates, return the minimum element in the array. The array was originally sorted in ascending order and then rotated between 1 and n times. Efficiently determine the minimum element, even when duplicates impact the binary search process.

Key Insights

  • The array is initially sorted and then rotated, meaning it is composed of two sorted subarrays.
  • When duplicates are present, the direct comparison might be inconclusive, which requires cautiously reducing the search space.
  • A modified binary search can be applied:
    • If the middle element is greater than the rightmost element, the minimum lies to the right.
    • If the middle element is less than the rightmost element, the minimum lies to the left, including the middle.
    • If the middle element equals the rightmost element, the optimal approach is to shrink the window by reducing the right pointer.
  • Worst-case time complexity may degrade to O(n) when many duplicates are present.

Space and Time Complexity

Time Complexity: Worst-case O(n) due to duplicates, otherwise O(log n) average. Space Complexity: O(1)

Solution

The solution uses a modified binary search:

  1. Initialize two pointers, left and right, at the beginning and end of the array.
  2. While left is less than right, compute the mid index.
  3. Compare the element at mid with the element at right:
    • If nums[mid] > nums[right], the minimum must be in the right half (exclude mid).
    • If nums[mid] < nums[right], the minimum is in the left half or might be mid itself, so move the right pointer to mid.
    • If nums[mid] equals nums[right], it is uncertain which half contains the minimum, so reduce the right pointer by one to safely shrink the space.
  4. When the loop finishes, the pointer left will point at the minimum element.

Key data structures include:

  • A simple array with integer elements.
  • Two pointers (indices) to perform the binary search.

This algorithm efficiently finds the minimum, adjusting to handle duplicates without risking skipping the potential candidate for the minimum.

Code Solutions

# Python implementation with inline comments

def findMin(nums):
    # Initialize left and right pointers
    left, right = 0, len(nums) - 1
    
    # Continue binary search until pointers converge
    while left < right:
        mid = left + (right - left) // 2  # safe mid calculation
        
        # if mid element is greater than right element, split to right half
        if nums[mid] > nums[right]:
            left = mid + 1
        # if mid element is less than right element, potential candidate found, include mid in next search
        elif nums[mid] < nums[right]:
            right = mid
        # if nums[mid] equals nums[right], cannot determine, reduce right by one
        else:
            right -= 1
            
    # left will be at the minimum element when loop ends
    return nums[left]

# Example Usage
print(findMin([2,2,2,0,1]))  # Output: 0
← Back to All Questions