Minimum in sorted rotated array

In post find element in sorted rotated array, we discussed an algorithm based on binary search, to find a given key in sorted rotated array.

Suppose an array sorted in ascending order 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. You may assume no duplicate exists in the array.

To understand the problem, let’s understand what is a sorted array, and then what is sorted rotated array?

An array is called sorted where for all i and j such that i < j, A[i] <= A[j].
A rotation happens when the last element of an array is pushed at the start and all elements of array move right by one position. This is called as rotation by 1. If the new last element is also pushed to start again, all elements are moved to the right, it’s a rotation by 2, and so on.

minimum in rotated sorted array

Find minimum in sorted rotated array problem is asked during telephonic or online coding rounds of companies like Microsoft or Amazon.

Minimum in sorted rotated array and binary search algorithm

As always, first, come up with a brute force solution without worrying about any optimizations as of now. The simplest way would be to scan through the array and keep track of the minimum. The complexity of this method is O(n).

In the brute force solution, we did not use the fact that the array is sorted and then rotated. Let’s forget about rotation and concentrate only on the sorted part.

What is the minimum element in a sorted array? Obviously, it is the first element of the array. We see that all the elements on the right side of the minimum elements are greater than the minimum.

What will happen if start rotating array now, is the condition that all the elements on the right of the minimum element are greater than it still holds? Yes, it does. Either there will be no element on the right side of minimum or the will be definitely greater than it. So it is obvious, that the first element in the sorted part of the array is a candidate for the minimum element in a sorted rotated array, rest all can be discard.

What if we start with the middle element. How do I know that if array on the right side of it is sorted or not? What information comparison between the middle and end gives us?

If middle element is less than the last element, the array is sorted from index mid to end, in this case, we have to look for minimum on the left part including the mid
minimum in sorted rotated array

If the middle element will be greater than the last element, array on the right side is not sorted, there must be someplace in this right part, where the sorted array start, hence minimum element should be in the right part of the array.

find minimum in rotated array

When should we stop? Well, what is the minimum of an array with only one element? The element itself. We will also stop when there is only 1 element left.

Algorithm to find minimum in sorted rotated array

  1. Find mid = start + (end- start) /2
  2. See if mid is part of sorted array or not, check A[mid] < A[end]
  3. If yes, minimum should be on the left part
  4. If no, minimum should be on the right part

Minimum in sorted rotated array implementation

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

The complexity of the algorithm to find minimum in a sorted rotated array is O(logn) because of binary search algorithm.

This problem is asked in many variations like find pivot in a sorted rotated array or find the number of rotations.

Interview coming up? Check out our full coding interview prep course. There’s a get-the-job-or-your-money-back guarantee, so it only costs money if it actually works.

As always, shoot me an email if there’s anything I can help with.