Skip to main content

25. Find Minimum in Rotated Sorted Array

mediumAsked at Apple

Find the minimum element in a rotated sorted array in O(log n) — Apple asks this to test whether you can adapt binary search when invariants are partially broken, a skill directly applicable to finding pivot points in macOS system log timestamps.

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 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

Approaches

1. Linear scan

Scan the full array tracking the minimum seen so far. Ignores sorted structure.

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

Tradeoff:

2. Modified binary search

Compare mid to right boundary. If nums[mid] > nums[hi], the minimum is in the right half; otherwise it is in the left half (inclusive of mid). Converge until lo === hi.

Time
O(log n)
Space
O(1)
function findMin(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] > nums[hi]) {
      // rotation pivot is in the right half
      lo = mid + 1;
    } else {
      // mid could itself be the minimum
      hi = mid;
    }
  }
  return nums[lo];
}

Tradeoff:

Apple-specific tips

Apple interviewers love this problem because it tests whether you can reason about invariants when data structure assumptions are violated — a skill that shows up when debugging race conditions in macOS subsystems where sorted data can arrive out-of-order due to concurrency. Common trap: comparing mid to lo instead of hi, which breaks when the array is not rotated. Walk through the 'no rotation' edge case out loud to show thoroughness — that's the kind of polish Apple rewards.

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

Practice these live with InterviewChamp.AI →