Skip to main content

74. Find Minimum in Rotated Sorted Array

mediumAsked at Datadog

Find the minimum value in a rotated sorted array in O(log n). Datadog asks this because their TSDB rotates compacted chunks across the time axis, and locating the pivot is the prerequisite for any range query.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — TSDB chunk pivot analog.
  • Blind (2025-11)— Recurring at Datadog.

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.

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

Example 3

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

Approaches

1. Linear scan

Min of array.

Time
O(n)
Space
O(1)
// return Math.min(...nums)

Tradeoff: Violates O(log n) constraint.

2. Binary search on pivot (optimal)

Compare nums[mid] to nums[hi]. If nums[mid] > nums[hi], pivot is right of mid; else left (or at mid).

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: Single pass O(log n). Datadog-canonical: same pivot-find logic they use to locate chunk boundaries.

Datadog-specific tips

Datadog grades on whether you compare to hi (not lo or mid+1). The 'compare to hi' version handles the non-rotated case ([1,2,3,4,5]) cleanly because nums[mid] <= nums[hi] always, so hi shrinks to 0.

Common mistakes

  • Comparing nums[mid] to nums[lo] — works but has more edge cases.
  • Using hi = mid - 1 instead of hi = mid — could skip the actual minimum.
  • Forgetting that the answer might be at index 0 (unrotated case).

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

  • Find Minimum II (LC 154) — with duplicates.
  • Search in Rotated Sorted Array (LC 33) — follow-up.
  • Datadog-style: locate the wrap-around boundary in a rotated TSDB chunk.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why compare to hi?

nums[mid] > nums[hi] means the pivot lies between mid+1 and hi. Else (nums[mid] <= nums[hi]), mid itself could be the min, or it's to mid's left.

Why not strict inequality?

With distinct values, equality can only happen when lo == hi, the loop exit. Use strict > for the rotated case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →