{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Find Minimum in Rotated Sorted Array – Solution & Complexity

Interview solutions
/
Find Minimum in Rotated Sorted Array

Solution Walkthrough

  1. Step 1: Read the rotated structure

    • A rotated ascending array is two sorted runs, e.g. [4,5,6,7] then [0,1,2].
    • The minimum value is exactly the first element of the second run (the pivot).
    • If the array is not rotated, the pivot is index 0.

  2. Step 2: Brute-force scan

    • The simplest answer is to scan every element and track the smallest.
    • This is O(n) and ignores the sorted structure, but it is a good correctness baseline.
    def find_min(nums):
    smallest = nums[0]
    for value in nums:
        if value < smallest:
            smallest = value
    return smallest

  3. Step 3: Binary search on the halves

    • Compare nums[mid] with nums[right].
    • If nums[mid] > nums[right], the pivot is to the right, so move left = mid + 1.
    • Otherwise the pivot is at mid or to its left, so move right = mid.
    • The loop ends when left == right, pointing at the minimum.

  4. Step 4: Logarithmic solution

    • Keep halving the search window based on the comparison above.
    • No mid + 1 on the right side, because mid itself may be the minimum.
    def find_min(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

  5. Step 5: Dry run

    Trace nums = [4, 5, 6, 7, 0, 1, 2].

    leftrightmidnums[mid] vs nums[right]action
    0637 > 2left = 4
    4651 <= 2right = 5
    4540 <= 1right = 4
    44—loop endsanswer nums[4] = 0

  6. Step 6: Final solution and complexity

    Binary search finds the pivot in O(log n) time and O(1) extra space.

    def find_min(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]
Learn the Binary Search pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Find Minimum in Rotated Sorted Array online (run code in the browser)Binary Search solution (easy)Koko Eating Bananas solution (medium)Longest Increasing Subsequence solution (hard)Median of Two Sorted Arrays solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?