Rotated Array Minimal Element — Problem Statement & Solution Guide

Binary SearchHardSearch in Rotated Array

TimeO(log n)

SpaceO(1)

Problem Description

You are given an array nums that was originally sorted in strictly increasing order and then rotated an unknown number of positions to the right. The rotation preserves the relative order of the elements, but the smallest value is no longer guaranteed to be at index 0. Your task is to determine the index of the minimal element in nums. The required algorithm must run in O(log n) time, i.e., you should employ a binary‑search‑style approach rather than scanning the entire array.

Input: An integer n (1 ≤ n ≤ 10^5) followed by n space‑separated integers representing nums. The array contains no duplicate values and each element satisfies -10^9 ≤ nums[i] ≤ 10^9.

Output: A single integer – the 0‑based index of the smallest element in the given rotated array.

DSA Pattern Breakdown

"Rotated Array Minimal Element"

hard

WHY DOES IT MATTER?

Finding the pivot in a rotated array is a classic example of leveraging partial order to achieve logarithmic search, a pattern that recurs in many real‑world problems such as versioned data stores, circular buffers, and time‑zone calculations.

OPTIMIZATION CHALLENGE

The key insight is that at any step one half of the array is guaranteed to be sorted. By comparing the middle element with the rightmost (or leftmost) element we can discard the sorted half entirely, reducing the search space by half each iteration.

REAL-WORLD CONNECTION

Consider a distributed log that continuously appends entries and periodically rolls over to a new file. The newest file starts at index 0, but the logical order of timestamps is preserved across files; locating the earliest timestamp mirrors finding the minimal element in a rotated sequence.

During an interview, write the loop invariant explicitly: low always points to a candidate for the minimal element. Update low only when you are sure the minimal cannot be left of mid. This mental model prevents off‑by‑one errors.

COMPLEXITY AT A GLANCE

⏱ Time:O(log n)

💾 Space:O(1)

Core Theory — Why This Approach?

The rotated sorted array retains the monotonic property except at the pivot where the maximum element is followed by the minimum. A naive linear scan can locate the minimal element but incurs O(n) time, which is prohibitive for large n. By exploiting the fact that each half of the array is still sorted, we can apply a modified binary search: compare the middle element with the rightmost element to decide which side contains the pivot, discarding the other half each iteration. This halving process guarantees logarithmic time.

When the middle element is greater than the rightmost element, the minimal value lies to the right of mid because the rotation point has not been passed yet. Conversely, if the middle element is less than or equal to the rightmost element, the minimal element is at mid or to its left, allowing us to shrink the search window from the right. Repeating until low equals high yields the exact index of the smallest element. This approach leverages the ordered substructure and avoids unnecessary comparisons, achieving O(log n) time with O(1) extra space.

Interview Questions on This Problem

Q1How would you modify the binary search if the array could contain duplicate values?

When duplicates are present, the comparison nums[mid] == nums[right] no longer tells us which side is sorted. In that case we can safely decrement right by one (right--) to shrink the window, because duplicates at the end cannot be the minimal element unless the whole subarray is equal. This degrades worst‑case time to O(n) but retains O(log n) on average.

Q2Explain why checking nums[mid] > nums[right] is sufficient to decide the search direction in a strictly increasing rotated array.

In a strictly increasing rotated array, the rightmost element belongs to the sorted suffix that starts at the minimal element. If nums[mid] > nums[right], mid lies in the left unsorted part where values are larger than the suffix, so the pivot must be to the right of mid. Otherwise, mid is in the sorted suffix (or at the pivot), so the minimal element is at mid or to its left.

Q3Can you derive the index of the minimal element using the array length and the original sorted order without binary search?

If we knew the original sorted order and the rotation count, the minimal element would be at index (n - rotationCount) % n. However, without explicit rotation count, we must discover the pivot via comparisons; binary search is the optimal way to infer that count in O(log n) time.

Examples

Example 1

Input

7
15 18 2 3 6 12 13

Output

Explanation: The original sorted sequence would be [2,3,6,12,13,15,18]. After rotation, the smallest value 2 appears at index 2, so the answer is 2.

Example 2

Input

5
40 50 5 10 20

Output

Explanation: The array is a rotation of the sorted list [5,10,20,40,50]. The minimal element 5 is located at index 2.

Example 3

Input

1
-7

Output

Explanation: With a single element the array is trivially sorted; the only element is also the minimum, located at index 0.

Constraints

1 <= nums.length <= 100000
-10^9 <= nums[i] <= 10^9
All elements in nums are distinct
The array is a non‑empty rotation of a strictly increasing sequence

Optimal Approach & Strategy

Apply a modified binary search that discards the sorted half each iteration by comparing the middle element with the rightmost element, converging on the pivot in O(log n) time.

Brute Force Approach

Scan the array from left to right, tracking the smallest value and its index. This takes linear time O(n).

Verified Code Solutions

Language:

JavaScript Solution

Time: O(log n)

function findMin(nums) {
   if (nums.length === 1) return 0;
   let left = 0, right = nums.length - 1;
   while (left < right) {
       let mid = Math.floor((left + right) / 2);
       if (nums[mid] > nums[right]) {
           left = mid + 1;
       } else {
           right = mid;
       }
   }
   return left;
}

class Solution {
   public:
       int findMin(vector<int>& nums) {
           if (nums.size() == 1) return 0;
           int left = 0, right = nums.size() - 1;
           while (left < right) {
               int mid = left + (right - left) / 2;
               if (nums[mid] > nums[right]) {
                   left = mid + 1;
               } else {
                   right = mid;
               }
           }
           return left;
       }
   };

class Solution {
   public int findMin(int[] nums) {
       if (nums.length == 1) return 0;
       int left = 0, right = nums.length - 1;
       while (left < right) {
           int mid = left + (right - left) / 2;
           if (nums[mid] > nums[right]) {
               left = mid + 1;
           } else {
               right = mid;
           }
       }
       return left;
   }
}

def find_min(nums):
   if len(nums) == 1:
       return 0
   left, right = 0, len(nums) - 1
   while left < right:
       mid = (left + right) // 2
       if nums[mid] > nums[right]:
           left = mid + 1
       else:
           right = mid
   return left

function findMin(nums) {
   if (nums.length === 1) return 0;
   let left = 0, right = nums.length - 1;
   while (left < right) {
       let mid = Math.floor((left + right) / 2);
       if (nums[mid] > nums[right]) {
           left = mid + 1;
       } else {
           right = mid;
       }
   }
   return left;
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Rotated Array Minimal Element Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Binary Search

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Rotated Array Minimal Element — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor