Skip to main content
DSA patterns

Find Minimum in Rotated Sorted Array

mediumBinary search Must-doAmazonMicrosoftCisco

Problem statement

Start with a list of unique numbers sorted from smallest to largest. Now rotate it: take some number of values off the front, one at a time, and move each one to the back, keeping the rest in the same order. Do that anywhere from 1 up to n times (rotating n times just brings the array back to how it started).

You're given the array nums after this rotation and need to return its minimum value. Because the array is really just a sorted array that's been split into two pieces and swapped, you don't need to look at every element — you should be able to answer in O(log n) time.

Examples

Example 1

Input: nums = [3,4,5,1,2]

Output: 1

Explanation: The original sorted array [1,2,3,4,5] was rotated 3 times, so 1 — the smallest value — ended up at index 3.

Example 2

Input: nums = [4,5,6,7,0,1,2]

Output: 0

Explanation: The original sorted array [0,1,2,4,5,6,7] was rotated 4 times, moving 0 to index 4.

Example 3

Input: nums = [11,13,15,17]

Output: 11

Explanation: This array was rotated a full 4 times, landing back in its original sorted order, so the minimum is just the first element.

Hints

Hint 1: If the array hadn't been rotated at all, the minimum would simply be the first element — how could a single comparison tell you whether you're already looking at that case?

Approach

Optimal: Binary search on the rotation point

Intuition

A rotated sorted array is really two sorted stretches glued together: everything from the rotation point to the end is smaller than everything from the start up to the rotation point. The minimum value is exactly the first element of that smaller, second stretch.

Comparing nums[mid] with nums[right] tells you which stretch mid is sitting in, without ever needing to know the whole array is sorted end to end:

  • If nums[mid] > nums[right], the values are still climbing between mid and the right edge, which means the rotation point — and the minimum — must be somewhere to the right of mid.
  • Otherwise, nums[mid] <= nums[right] means mid is already inside the smaller, second stretch, so the minimum is at mid or somewhere to its left, and mid itself has to stay a candidate.

Each comparison throws away half the array, which is what makes this O(log n) instead of the brute force's O(n).

Steps

  1. Set left = 0 and right = n - 1.
  2. While left < right:
    • Compute mid = left + (right - left) / 2.
    • If nums[mid] > nums[right], the minimum is to the right of mid, so set left = mid + 1.
    • Otherwise the minimum is at mid or to its left, so set right = mid.
  3. When left == right, nums[left] is the minimum — return it.

Dry run

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

left right mid nums[mid] nums[right] action
0 6 3 7 2 7 > 2 → left = 4
4 6 5 1 2 1 <= 2 → right = 5
4 5 4 0 1 0 <= 1 → right = 4
4 4 — loop ends — return nums[4] = 0

Edge cases: an array that wasn't really rotated (or rotated by exactly n) never satisfies nums[mid] > nums[right], so right keeps shrinking down to index 0, correctly returning nums[0]. An array of length 1 skips the loop entirely and returns its only element.

Complexity

Time O(log n) - each comparison between nums[mid] and nums[right] rules out half of the remaining candidates, so the search window shrinks to size 1 in about log2(n) steps. This is the bound the problem statement asks for.

Space O(1) - only two pointers and a midpoint are kept, regardless of the array's size.

class Solution:
    def findMin(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        return nums[left]


if __name__ == "__main__":
    print(Solution().findMin([3, 4, 5, 1, 2]))         # 1
    print(Solution().findMin([4, 5, 6, 7, 0, 1, 2]))   # 0
    print(Solution().findMin([11, 13, 15, 17]))        # 11
RecapThe whole problem in a few lines, for the night before
  • Spot it: a sorted array that's been rotated (split into two sorted pieces and swapped), asking for the minimum in O(log n)
  • Idea: binary search using nums[mid] vs nums[right] — if nums[mid] > nums[right], the minimum is to the right of mid, otherwise it's at mid or to the left
  • Cost: O(log n) time, O(1) space (a plain scan for the minimum is O(n))
  • Trap: comparing nums[mid] to nums[0] instead of nums[right] and getting the direction backwards when mid lands past the rotation point

Interview follow-ups

  • What if you also need to find a specific target value in the rotated array, not just its minimum?

    Once you know which half is properly sorted at each step (using the same nums[mid] vs nums[right] comparison), you can check whether the target falls inside that sorted half's range and search there, or otherwise search the other half — this is the classic Search in Rotated Sorted Array problem, still O(log n).

  • What if you needed to know how many times the array was rotated, not just the minimum value?

    The number of rotations equals the index where the minimum sits, since that's exactly how many elements were moved from the front to the back. The same binary search already computes that index as left right before returning nums[left], so no extra work is needed beyond returning the index instead of the value.

Frequently asked questions

Comparing against nums[right] works cleanly no matter where the rotation point is, because it directly tells you whether the segment from mid to right is still in ascending order (no wraparound in between) or not. Comparing against nums[0] instead is also possible, but needs a bit more care to handle the case where mid itself lands before the rotation point versus after it.

The problem guarantees every value in nums is unique, so mid and right can never hold equal values unless mid == right, which only happens once the loop has already finished. That's what makes the two-way if/else in the optimal approach safe, with no separate tie-breaking case needed.

Rotated sorted data comes up whenever a ring buffer, circular log, or wrap-around index is involved — for example, a fixed-size buffer of recent events where the oldest slot gets overwritten first. Recognizing that a rotated sorted array is still made of two sorted pieces is the same skill needed to reason about where the "oldest" and "newest" entries sit in that kind of structure.

The nums[mid] > nums[right] rule stops being reliable, because nums[mid] == nums[right] no longer guarantees mid and right are the same element — it could also mean the array has flattened into a run of equal values that hides where the minimum actually is. The fix is to also handle the equal case by simply shrinking right by one and re-checking, which still works but can degrade to O(n) in the worst case (e.g. an array of all-equal values with one dip).