Skip to main content

21. Find Minimum in Rotated Sorted Array

mediumAsked at DigitalOcean

Find the minimum element in a rotated sorted array in O(log n) — a binary search variant that tests systematic halving under a shifted invariant.

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, return the minimum element. All integers are unique and the algorithm must run in O(log n).

Constraints

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All integers are unique

Examples

Example 1

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

Example 2

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

Approaches

1. Linear scan

Traverse the array and track the minimum — O(n), violates the O(log n) requirement.

Time
O(n)
Space
O(1)
function findMin(nums) {
  let min = nums[0];
  for (const n of nums) min = Math.min(min, n);
  return min;
}

Tradeoff:

2. Binary search on rotation pivot

Compare mid with right boundary: if nums[mid] > nums[right], the pivot is in the right half; otherwise narrow to the left half. Converges to the minimum in O(log n).

Time
O(log n)
Space
O(1)
function findMin(nums) {
  let lo = 0, 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:

DigitalOcean-specific tips

DigitalOcean interviewers extend this to 'find the pivot node in a circular linked list' or 'detect the crashed replica in a ring' — understand the rotation invariant deeply.

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 DigitalOcean interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →