Skip to main content

24. Find Minimum in Rotated Sorted Array

mediumAsked at Asana

Locate the minimum in a rotated sorted array in O(log n) — Asana applies binary search on monotonic-but-rotated data structures when quickly finding the earliest due-date task in a reordered sprint queue.

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. Given the rotated array nums of unique elements, return the minimum element. You must solve it in O(log n) time.

Constraints

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All integers in 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: Original array [1,2,3,4,5] rotated 3 times. Minimum is 1.

Example 2

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

Explanation: Rotated 4 times. Minimum is 0.

Approaches

1. Linear scan

Iterate through the array and track the minimum. Simple but O(n).

Time
O(n)
Space
O(1)
function findMin(nums) {
  let min = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < min) min = nums[i];
  }
  return min;
}

Tradeoff:

2. Binary search on the inflection point (optimal)

If nums[mid] > nums[right], the minimum is in the right half. Otherwise it is in the left half (including mid). Converge until lo === hi.

Time
O(log n)
Space
O(1)
function findMin(nums) {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] > nums[hi]) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }

  return nums[lo];
}

Tradeoff:

Asana-specific tips

Asana interviewers want you to recognize that rotation creates exactly one inflection point and that binary search can home in on it. The key invariant: if nums[mid] > nums[hi], the inflection (and thus the minimum) must be to the right of mid. Walk through why you compare mid to hi rather than lo — interviewers have seen candidates choose the wrong comparator and spiral into edge-case bugs. Get that invariant on the board first.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Find Minimum in Rotated Sorted Array and other Asana interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →