Skip to main content

153. Find Minimum in Rotated Sorted Array

medium

Find the smallest element in a rotated sorted array of distinct integers. Tests whether you can write binary search when there's no explicit 'target' to compare against.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] if it was rotated 4 times or [0,1,2,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 of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time.

Constraints

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All the integers of nums are unique.
  • nums is sorted and rotated between 1 and n times.

Examples

Example 1

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

Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2

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

Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3

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

Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

There's no explicit target — compare nums[mid] to nums[hi] to decide which side holds the minimum.

Hint 2

If nums[mid] > nums[hi], the minimum is in the right half (mid is in the larger, pre-rotation half).

Hint 3

Otherwise the minimum is in the left half including mid.

Hint 4

Use a half-open window (lo < hi) — when they converge, lo points at the minimum.

Solution approach

Reveal approach

Binary search where the 'target' is the rotation pivot. Use lo = 0, hi = n - 1 with a strict < loop condition. While lo < hi: mid = lo + (hi - lo) / 2. If nums[mid] > nums[hi], the minimum must be strictly right of mid (the pivot lies in (mid, hi]) — set lo = mid + 1. Otherwise nums[mid] <= nums[hi], so the minimum is at mid or to its left — set hi = mid. When lo == hi, return nums[lo]. O(log n) time, O(1) space. Comparing to nums[hi] rather than nums[lo] is the trick — it disambiguates correctly even when the array isn't rotated at all (everything <= nums[hi] sends you left, and lo lands at index 0).

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Goldman Sachs

Practice these live with InterviewChamp.AI

Drill Find Minimum in Rotated Sorted Array and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →