Find Minimum in Rotated Sorted Array

Medium Problem 45 of 151 Java and Python

Problem

An array sorted in ascending order with unique values has been rotated some number of times: 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 minimum element in O(log n) time.

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
Why: Rotated a full cycle: still sorted.

Constraints

1 ≤ n ≤ 5000
All values are unique.

Explanation

A rotated array is two sorted runs; the minimum is where the second run starts.

Compare nums[mid] with nums[hi]. If nums[mid] > nums[hi], the drop (and the minimum) is to the right of mid. Otherwise mid is in the second run, so the minimum is at mid or to its left.

Approach 1 · Naive

Linear scan

Time O(n)
Space O(1)

Return the smallest element by looking at all of them.

Track the minimum while scanning.

Java

class Solution {
    public int findMin(int[] nums) {
        int min = nums[0];
        for (int num : nums) {
            min = Math.min(min, num);
        }
        return min;
    }
}

Python

class Solution:
    def findMin(self, nums: List[int]) -> int:
        return min(nums)

Approach 2 · Optimal

Binary search against the right end

Time O(log n)
Space O(1)

Shrink towards the side that holds the rotation point.

Set lo = 0, hi = n - 1.
While lo < hi: if nums[mid] > nums[hi], lo = mid + 1; else hi = mid.
Return nums[lo].

Java

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

Python

class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[hi]:
                lo = mid + 1
            else:
                hi = mid
        return nums[lo]

Complexity compared

Approach	Time	Space
Naive Linear scan	O(n)	O(1)
Optimal Binary search against the right end	O(log n)	O(1)

Key takeaways

Compare with nums[hi], not nums[lo]: with no rotation, comparing to the left end points the wrong way.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem