LeetCode Find Minimum in Rotated Sorted Array II: Worst Case Analysis

Overview

A binary search based algorithm is given to find the minimum in the LeetCode Rotated Sorted Array. It runs in O(N) in worst case, but O(logN) if no duplicates.

LeetCode Problem Definition

Find Minimum in Rotated Sorted Array II:

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Solutions and Worst Time Analysis

Well, this problem is actually a twisted version of an old problem: “LeetCode Search in Rotated Sorted Array II: More General & Compact Code“. The worst time is O(N) because we might not be able to determine the minimum exist in the left half or the right half as in our last discussion: “LeetCode Find Minimum in Rotated Sorted Array: Binary Search, Tricky Boundary Issue“. Consider this example: 1 1 1 1 1 -3 1, and 1 -3 1 1 1 1, so in this case, we have to linear scan the whole sequence. So a small modification on the code given in  ”LeetCode Find Minimum in Rotated Sorted Array: Binary Search, Tricky Boundary Issue” would give us the more general one which could solve both cases (no duplicates and duplicates exist) in one consistent way and the code runs in O(N) worst time but it would run O(logN) if no duplicates exist in the rotated sorted array. The following is the source code accepted by LeetCode OJ:

int findMin(vector<int> &num) {
    int lo = 0, hi = num.size() - 1;
    int mid = 0;

    while (lo < hi - 1) {
        if (num[lo] < num[hi]) return num[lo];
        mid = lo + (hi - lo) / 2;

        if (num[lo] < num[mid])
            lo = mid; 
        else if (num[lo] > num[mid])
            hi = mid;  
        else {
            if (num[lo] == num[mid]) ++lo;
            if (num[hi] == num[mid]) --hi;
        }
    }
    if (lo == hi) return num[lo];
    if (hi > lo)  return min(num[lo], num[hi]);
    return -1;
}

Summary

A binary search based algorithm is given to find the minimum in the LeetCode Rotated Sorted Array. It runs in O(N) in worst case, but O(logN) if no duplicates. Please share your comments if you got better ideas on how to solve this LeetCode Find Minimum in Rotated Sorted Array problem. Thanks!

Written on November 14, 2014