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

Number: 153

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, TikTok, Bloomberg, Goldman Sachs, Microsoft, Apple, Walmart Labs, Yandex, eBay, Adobe, Uber, Oracle, Paytm, Arista Networks, Tesla, Nutanix, FreshWorks

Problem Description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array of unique elements, return the minimum element of this array. The solution must run in O(log n) time.

Key Insights

  • The rotated sorted array consists of two sorted subarrays.
  • A modified binary search can be used to locate the pivot point where the rotation occurs.
  • By comparing the middle element to the rightmost element, we can decide which half of the array contains the minimum.

Space and Time Complexity

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

Solution

Use a binary search approach. Initialize two pointers, left and right, at the start and end of the array. While left is less than right, calculate the middle index. If the middle element is greater than the right element, then the minimum is in the right half, so move the left pointer to mid + 1; otherwise, the minimum must be in the left half including mid, so adjust the right pointer to mid. When the loop terminates, left equals right and points to the minimum element. This approach leverages the properties of the rotated sorted array to achieve logarithmic time complexity.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

def findMin(nums):
    # Initialize left and right pointers
    left, right = 0, len(nums) - 1
    # Continue while the search space is valid
    while left < right:
        mid = (left + right) // 2  # Compute middle index
        # If middle element is greater than the rightmost element,
        # the minimum must be in the right half
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            # Otherwise, the minimum is in the left half (including mid)
            right = mid
    # When loop ends, left == right, pointing to the minimum element
    return nums[left]
← Back to All Questions