Find Minimum in Rotated Sorted Array

NeetCode: Find Minimum in Rotated Sorted Array · LeetCode: 153. Find Minimum in Rotated Sorted Array · Difficulty: Medium

A sorted array of distinct values was rotated between 1 and n times, for example [3, 4, 5, 6, 1, 2]. Return its minimum element in O(log n) time.

Example

Text

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

Brute force: scan for the minimum

Keep the smallest value seen so far while walking the array. LeetCode guarantees at least one element, so nums[0] is a safe starting value.

Java

class Solution {
    public int findMin(int[] nums) {
        int min = nums[0];
        for (int x : nums) {
            if (x < min) {
                min = x;
            }
        }
        return min;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findMin(new int[] {3, 4, 5, 6, 1, 2}));
        System.out.println(s.findMin(new int[] {4, 5, 0, 1, 2, 3}));
    }
}

Output

1
0

Time: O(n). Space: O(1).

Optimal: binary search for the rotation point

Compare the middle element with the last element. If nums[mid] > nums[hi], the drop (the minimum) is to the right of mid. Otherwise the minimum is at mid or to its left. The range [lo, hi] always contains the minimum, and the loop ends when it holds one index.

lo + (hi - lo) / 2 is used for the middle because lo + hi can overflow int when the array is very large.

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];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findMin(new int[] {3, 4, 5, 6, 1, 2}));
        System.out.println(s.findMin(new int[] {4, 5, 0, 1, 2, 3}));
        System.out.println(s.findMin(new int[] {1, 2, 3}));
        System.out.println(s.findMin(new int[] {7}));
    }
}

Output

Time: O(log n). Space: O(1).