Find the Smallest Element After a Sorted Array Is Rotated

Medium15–20 min

Topics

ArrayBinary Search

Companies

AmazonMicrosoftBloomberg

An array of unique values, sorted in ascending order, is rotated at some unknown pivot — for example [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Given the rotated array nums, return its smallest element. Solve it in O(log n) time by binary-searching for the "seam" where the array's values drop from high back down to low.

Test Case 1:

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

Output:0

Explanation:The array was sorted [0,1,2,4,5,6,7] then rotated — 0 is the smallest value.

Test Case 2:

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

Output:1

Explanation:Rotated from [1,2,3,4,5].

Test Case 3:

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

Output:11

Explanation:Not rotated at all — the minimum is just the first element.

Constraints

◆1 ≤ nums.length ≤ 5000
◆-5000 ≤ nums[i] ≤ 5000
◆All the values of nums are unique
◆nums was sorted in ascending order, then possibly rotated

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (rotated sorted, comma-separated) — 1-12 distinct integers

1	class Solution {
2	public int findMin(int[] nums) {
3	int lo = 0, hi = nums.length - 1;
4	while (lo < hi) {
5	int mid = lo + (hi - lo) / 2;
6	if (nums[mid] > nums[hi]) {
7	lo = mid + 1;
8	} else {
9	hi = mid;
10	}
11	}
12	return nums[lo];
13	}
14	}
15

↑lo

↑hi

Variables

lo0

hi6

INITIALIZE

Search [0, 6] for the seam where the rotation drops back down to the smallest value.

Step 1 / 5

Approach & Solutions

Brute Force — Linear Scan

Brute

Track the smallest value seen so far while walking the whole array once. It works regardless of rotation, but it never uses the fact that a rotated sorted array is really just two sorted runs glued together, which is what lets binary search skip most of the array.

TimeO(n)

SpaceO(1)

Java

Try it out

class Solution {
    public int findMin(int[] nums) {
        int minIdx = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[minIdx]) minIdx = i;
        }
        return nums[minIdx];
    }
}

Optimal — Binary Search

Optimal

The minimum sits exactly at the "seam" where the rotation drops from a high value back down to a low one. Compare nums[mid] against nums[hi]: if nums[mid] > nums[hi], the seam (and the minimum) is somewhere to the right of mid, so search there. Otherwise the array from lo to mid is already the "reset" side, so the minimum is at mid or to its left — keep mid in range.

TimeO(log n)