Minimum in sorted rotated array

Find 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.  Problem today is bit different, there is no key to find first of all. Ask of problem is to find minimum in sorted rotated array.

To understand problem, first let’s understand what is 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 last element of array is push at the start and all elements of array move right by one position. This is called as rotation by 1. If new last element is also pushed to start again, all elements are moved to right, it’s rotation by 2 and so on.

Find element in sorted rotated array
Sorted array
Sorted rotated array

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

Find minimum in sorted rotated array : Thought process

As always, first come up with a brute force solution without worrying about any optimizations as of now. Simplest way would be to scan through array and keep track of minimum. Complexity of this method is O(N), however, what is the fun if we do it in O(N) time complexity ?

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

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

What will happen if start rotating array now, is the condition that all the elements on right of minimum element are greater than it still hold? Yes, it does. Either there will be no element on right side of minimum or the will be definitely greater than it.

So, idea is we randomly pick an element and see if elements on right side of it are greater. No need to go through each element, compare selected element with last index element, if last index element is greater, selected element can be minimum. (Remember we are working sorted array!).
Start comparing with middle element. What information comparison between middle and end element gives us?
Array could have been in two ways : It is rotated more than half or it is rotated less than half.
If middle element is less than last element, array is rotated less than half, and hence, minimum element should be on the left half of array.
If middle element will be greater than last element, array is rotated more than half, hence minimum element should be in right part of array.
What if middle element is the minimum element? See if element on left and right of mid are both greater than element at mid, mid is index of minimum element.
Let’s take an example and see how this method works and then come up with concrete algorithm to find minimum in sorted rotated array. For example, array is given as below.
minimum in sorted rotated array
First, we find the mid, check if mid is minimum?  A[mid] > A[mid-1], so it cannot be minimum element. So, see if array is rotated more than half or less than half.
Since, A[mid] > A[end], array is rotated more than half and hence, minimum should be on the right side.
We will discard the left subarray and focus on right subarray to find minimum.
Again, find the mid, is mid the minimum? No, so compare it with end, since, A[mid] < A[end],  minimum should be on the left side, discard right subarray.
Find mid again and this time mid satisfy the condition : A[mid-1] and A[mid+1] both are greater than A[mid], hence, A[mid] should be the minimum element.
minimum in sorted rotated array
Can you come up with execution trace when array is not rotated more than half to start with?

Minimum in sorted rotated array : Algorithm

  1. Find mid = start + (end- start) /2
  2. See if mid is minimum element i.e is A[mid] < A[mid-1] and A[mid] < A[mid+1]. If yes, return mid
  3. Else if A[mid] > A[end]:
    • Array is rotated more than half, minimum should be on right subarray
    • Continue with subarray with start =  mid+1
  4. Else if A[mid] < A[end]:
    • Array is rotated less than half, minimum should be on left subarray
    • Continue with subarray with end = mid-1

Minimum in sorted rotated array implementation

package com.company;

/**
 * Created by sangar on 22.3.18.
 */
public class SortedRotatedArray {

    public static int findMinimumIterative(int[] input, int start, int end) {

        while (start < end) {
            int mid = start + (end - start) / 2;

            if (mid == 0 || (input[mid] <= input[mid+1]
                    && input[mid] < input[mid-1])) return mid;
            else if (input[mid] > input[mid]) {
                 /* Array is rotated more than half, hence minimum
                 should be in right sub-array
                  */
                start  = mid + 1;
            } else {
                 /* Array is rotated less than half, hence minimum
                 should be in left sub-array
                  */
                end  = mid - 1;
            }
        }
        return start;
    }
    public static void main(String[] args) {
        int[] input = {10,11,15,17,3,3,3,3,3,3};

        int index = findMinimumIterative(input,0, input.length-1);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

    }
}

Recursive implementation of same function

package com.company;

/**
 * Created by sangar on 22.3.18.
 */
public class SortedRotatedArray {

    public static int findMinimumRecursive(int[] input, int start, int end){

        if(start < end){
            int mid = start + (end - start) / 2;

            if(mid == 0 || (input[mid] < input[mid-1]
                            && input[mid] <= input[mid+1] ) ) return mid;

            else if(input[mid] > input[end]){
                /* Array is rotated more than half and hence,
                search in right subarray */
                return findMinimumRecursive(input, mid+1, end);
            }else {
                return findMinimumRecursive(input, start, mid - 1);
            }
        }
        return start;
    }

    public static void main(String[] args) {
        int[] input = {3,10,11,15,17,18,19,20};

        int index = findMinimumRecursive(input,0, input.length-1);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

    }
}

Complexity of algorithm to find minimum in sorted rotated array is O(log N), with recursive implementation having implicit space complexity of O(log N).

What did we learn from this problem?
First learning is to always go for brute force method. Second, try to draw the effect of any additional operations which are done on original array. In sorted rotated array, try to have rotation one by one and see what impact it has on minimum element? Try to classify individual class and design your algorithm. In this problem, we identify that based on how many times array is rotated, minimum can be in right or left subarray from middle and that gave idea for discarding half of the array.

Please share if there is something wrong or missing, or any improvement we can do. Please reach out to us if you are willing to share your knowledge and contribute to learning process of others.