Efficient Method to Identify the Minimum in a Rotated Sorted Array

The Problem:

Link to Problem

Finding the minimum element in a sorted array that has been rotated. An array of length ‘n’ sorted in ascending order can be rotated between 1 and n times.

The given examples; the array

nums = [0,1,2,4,5,6,7] will change into [4,5,6,7,0,1,2] if it was rotated 4 times. if rotated 7 times, it remains the same [0,1,2,4,5,6,7]-as there are only 7 elements in total.

In the given sorted, rotated array nums of unique elements, we have to return the minimum element.

Leetcode has specified Time Complexity requirement as O(n).

But lets come back to that later, after i discuss the solutions i was able to come up with in few minutes after reading the question.

Constraints:

• n equals nums.length.

• n is between 1 and 5000.

• nums[i] is between -5000 and 5000.

• All integers in nums are unique.

• nums is sorted and rotated between 1 and n times.

The Solution:

Using a global variable to store the minimum number while iterating the array.

class Solution {
public:
    int findMin(vector<int>& nums) {
        int min = nums[0];
        for (int i : nums) {
            min = min < i ? min : i;
        }
        return min;
    }
};

Time Complexity is O(n).

Finding the point of start from the original array.

class Solution {
public:
    int findMin(vector<int>& nums) {
        for (int i = 0; i < size(nums) - 1; ++i) {
            if (nums[i] > nums[i+1]) {
                return nums[i+1];
            }
        }
        return nums[0];
    }
};

Time Complexity is O(n).

These are the two solutions that i came up with, both do not satisfy the time complexity.

The Efficient Solution

class Solution {
public:
    int findMin(vector<int>& nums) {
        int head = 0;
        int tail = size(nums) - 1;
        int mid;
        int ans = nums[0];

        while (head <= tail) {
            mid = head + (tail - head) / 2; // so that we can find the mid even when
// the head or end values update.

            if (nums[mid] >= nums[0]) {
                head = mid + 1; // updating the head of subarray to be checked if the
// mid value is lesser than the start value. this helps here, since the arrays are rotated.
            } else {
                ans = nums[mid]; // so that the final subarray which would have
// one or two elements at most, the mid element, which would be lesser of the two
// elements at the worst case can be returned.
                tail = mid - 1; // moving the subarray to right.
            }
        }
        return ans;
    }
};

Time Complexity is O(log(n)).

This is because the algorithm effectively halves the search space with each iteration of the while loop, similar to standard binary search.

You can think, the while loop time function something is kind of like continuous halving of search space.

---

Your Welcome,

Your Fiercely Sincere Java from IDL.