Skip to main content

153. Find Minimum in Rotated Sorted Array

mediumAsked at Bloomberg

Bloomberg's market-data systems store price histories as circular buffers that reset at midnight — finding the rotation pivot is the same binary search insight Bloomberg engineers apply when locating the session-open price in a ring buffer.

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 write an algorithm that runs in O(log n) time.

Constraints

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

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 from left; return the first element smaller than its predecessor, or nums[0] if none found.

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

Tradeoff:

2. Binary search on rotation pivot

Compare mid against the rightmost element. If nums[mid] > nums[right] the minimum is in the right half; otherwise it is in the left half (including mid). Converge to a single element.

Time
O(log n)
Space
O(1)
function findMin(nums) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const mid = (left + right) >> 1;
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return nums[left];
}

Tradeoff:

Bloomberg-specific tips

Bloomberg interviewers expect O(log n) immediately — mentioning linear scan as a baseline is fine but move quickly. The key insight to articulate: you don't compare mid against nums[0] (ambiguous when not rotated); you always compare against nums[right] so the invariant holds regardless of rotation count. Draw the two-segment picture on the whiteboard; it shows you reason in terms of array structure, not just index arithmetic.

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

Practice these live with InterviewChamp.AI →