Find smallest number in Sorted Rotatable Array

Question

I came across this question in one Interview. Please help me in getting the solution.

Question is:

You have sorted rotatable array, i. e. the array contains elements which are sorted and it can be rotated circularly, like if the elements in array are [5,6,10,19,20,29] then rotating first time array becomes [29,5,6,10,19,20] and on second time it becomes [20,29,5,6,10,19] and so on.

So you need to find the smallest element in the array at any point. You won’t be provided with number times array is rotated. Just given the rotated array elements and find out the smallest among them. In this case output should be 5.

Answer 1

Solution for both array with duplicate and not, with the recursive binary search approach.

Unique array

var min = (A, l, h) => {
    if(l >= h) return A[l];
    
    let  m = Math.floor((l + h) / 2);
    // as its unique
    if(A[m] > A[h]) {
        // go towards right as last item is small than mid
        return min(A, m + 1, h);
    } else if(A[m] > A[m - 1]) {
        // go towards left as prev item is smaller than current
        return min(A, l, m - 1);
    } else {
        // right and left is greater than current
        return A[m];
    }
}
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    // If array is rotated nums.length time or same as it is
    if(nums[0] < nums[nums.length - 1]) return nums[0];
    
    return min(nums, 0, nums.length - 1);
};

Array with duplicates

var min = (A, l, h) => {
    if(l >= h) return A[l];
    
    // traverse from left "and right" to avoid duplicates in the end
    while(A[l] == A[l+1]) {
        l++;
    }
    
    let  m = Math.floor((l + h) / 2);
    // as its unique
    if(A[m] > A[h]) {
        // go towards right as last item is small than mid
        return min(A, m + 1, h);
    } else if(A[m] >= A[m - 1]) {
        // go towards left as prev item is smaller than current
        return min(A, l, m - 1);
    } else {
        // right and left is greater than current
        return A[m];
    }
}
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    // If array is rotated nums.length time or same as it is
    if(nums[0] < nums[nums.length - 1]) return nums[0];
    
    return min(nums, 0, nums.length - 1);
};

Answer 2

Here is a very simple answer, it will work for all test cases:

int a[] = {5,6,7,1,2,3,4};
int a[] = {1,2,3};
int a[] = {3,2,1};
int a[] = {3,1,2};
int a[] = {2,2,2,2};

---

public class FindSmallestNumberInSortedRotatedArray {

    public static void main(String[] args) {
        int a[] = { 4, 5, 6, 7, 1, 2, 3 };
        int j = a.length - 1;
        int i = 0;
        while (i < j) {
            int m = (i + j) / 2;
            if (a[m] < a[m + 1] && a[m] < a[m - 1]) {
                System.out.println(a[m] + "is smallest element ");
                break;
            } else if (a[m] > a[m + 1] && a[m - 1] > a[m + 1]) {
                i = m + 1;
            } else {
                j = m - 1;
            }

        }
        if (i == j)
            System.out.println(a[i] + " is smallest element");

    }

Answer 3

This is my pythonic solution using recursion:

Time complexity is O(log(n)) & Space complexity: O(1)

    class Solution(object):
       def findMin(self, nums):
          left = 0
          right = len(nums) -1
          mid = len(nums) // 2

          if len(nums) == 0:
             return -1
         if len(nums) == 1:
            return nums[left]
         if len(nums) == 2:
            return min(nums[left], nums[right])

         if nums[left] < nums[right]:
            return nums[left]
         elif nums[mid] > nums[left]:
            return self.findMin(nums[mid + 1: ])
         elif nums[mid] < nums[left]:
            return self.findMin(nums[: mid + 1])

Answer 4

//java program to find minimum element in a sorted array rotated 
//about any pivot in O(log n) in worst case and O(1) in best case

class ArrayRotateMinimum {
    public static void main(String str[]) {

    // initialize with your sorted rotated array here

    int array[] = { 9, 1, 2, 3, 4, 5, 6, 7, 8, };
    System.out.println("Minimum element is: " + minimumElement(array));
    }

static int minimumElement(int array[]) {

    // variables to keep track of low and high indices

    int low, mid, high;

    // initializing variables with appropriate values

    low = 0;
    high = array.length - 1;
    while (low < high) {

        // mid is always defined to be the average of low and high

        mid = (low + high) / 2;
        if (array[low] > array[mid]) {

            // for eg if array is of the form [9,1,2,4,5],
            // then shift high to mid to reduce array size by half
            // while keeping minimum element between low and high

            high = mid;
        } else if (array[mid] > array[high]) {

            // this condition deals with the end case when the final two
            // elements in the array are of the form [9,1] during the
            // last iteration of the while loop

            if (low == mid) {
                return array[high];
            }

            // for eg if array is of the form [4,5,9,1,2],
            // then shift low to mid to reduce array size by half
            // while keeping minimum element between low and high

            low = mid;
        } else {

            // the array has not been rotated at all
            // hence the first element happens to be the smallest element

            return array[low];
        }
    }

    //return first element in case array size is just 1
    return array[0];

    }
}

Answer 5

def searchinrotatedarray(arr1,l,h):
    if l>h:
        return arr1[0]
    if h==l:
        return arr1[l]
    mid=(l+h)//2
    if mid<h and arr1[mid+1]<arr1[mid]:
        return arr1[mid+1]
    elif mid>l and arr1[mid-1]<arr1[mid]:
        return arr1[mid]
    elif arr1[mid]<arr1[h]:
        return searchinrotatedarray(arr1,l,mid-1)
    else:
        return searchinrotatedarray(arr1,mid+1,h)

first if statement checks if even array is rotated at all. in that case first element is the min . if length of list is 1 then that element is min. else if mid element is less than last element then continue to look in second half else look for the element in first half

Answer 6

To Find the smallest number in the sorted rotated array: using Binary search concept

public class RotatedSortedArrayWithoutDuplicates1 {

    public static void main(String[] args) {
        int[] a = { 4, 6, 8, 10, 34, 56, 78, 1, 3 };

        System.out.println(findMin(a));

    }

    private static int findMin(int[] a) {
        if (a.length == 0 || a == null) {
            return -1;
        }
        int start = 0;
        int last = a.length - 1;
        while (start + 1 < last) {
            int mid = start + (last - start) / 2;
            int m = a[mid];
            int s = a[start];
            int l = a[last];

            if (m > l) {
                start = mid + 1;
            }
            if (m < l) {
                last = mid;
            } else {
                last--;
            }

        } // while

        if (a[start] > a[last]) {
            return a[last];
        } else {
            return a[start];
        }

    }
}

But if you don't want to use Binary Search, then :

public class Abc {
    public static void main(String[] args) {
        int[] a = { 4, 5, 6, 7, 7, 8, 9, 1, 1, 2, 3, 3 };
        System.out.println(findMin(a));
    }

    public static int findMin(int[] a) {

        int min = a[a.length - 1];

        for (int i = 0; i < a.length; i++) {
            if (min > a[i]) {
                min = a[i];
                break;
            }
        }
        return min;

    }// findmin
}// end

Here is the code in Python:

def fix(a):
    min = a[0]
    for i in range(len(a)):
        if(min > a[i]):
            min = a[i]
            break

    return min        


a = [2, 2,3,4,1,2]
print(fix(a))

Answer 7

Question : Find minimum in a sorted rotated array . Solution 1 : Using Binary Search

class Test18 {
    public static void main(String[] args) {
        int[] a = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };

        System.out.println(findmin(a));

    }

    // find min in a sorted rotated array
    private static int findmin(int[] a) {
        int start = 0;
        int last = a.length - 1;
        while (start + 1 < last) {
            int mid = start + (last - start) / 2;
            if (a[mid] > a[last]) {
                start = mid + 1;
            }
            if (a[mid] < a[last]) {
                last = mid;
            } else {
                mid--;
            }

        } // while
        if (a[start] > a[last]) {
            return a[last];
        } else {
            return a[start];
        }

    }
}

Answer 8

I did it using a slightly modified version of binary search. What I am doing here is I keep going left or right based on where the minimum could be. For example in an ascending array if the mid element is less than the left most element, its possible that the minimum is to the left. While recursing thru the array, I also keep track of the minimum. The recursion continues until the end and then the latest min is returned. This also works with repeated elements.

public static void main(String[] args) throws IOException {

    int[] rotated = {6, 7, 8, 1, 2, 3, 4, 5};
    int min = findMin(rotated);
    System.out.println(min);//1


}

public static int findMin(int[] sorted) {
    return findMinRecursively(sorted, sorted[0], 0, (sorted.length - 1));
}


private static int findMinRecursively(int[] sorted, int min, int leftIndex, int rightIndex) {

    if (leftIndex > rightIndex) {
        return min;
    }

    int midIndex = (leftIndex + rightIndex) / 2;
    if (sorted[midIndex] < min) {
        min = sorted[midIndex];
    }

    if (sorted[midIndex] < sorted[leftIndex]) {
        return findMinRecursively(sorted, min, leftIndex, (midIndex - 1));
    } else {
        return findMinRecursively(sorted, min, (midIndex + 1), rightIndex);
    }
}

Answer 9

The above algorihtm fails if data element is repeated like {8,8,8,8,8} or {1,8,8,8,8} or {8,1,8,8,8} or {8,8,1,8,8} or {8,8,8,8,1}

// solution pasted below will work all test cases :)

//break the array in two subarray and search for pattern like a[mid]>a[mid+1]
// and return the min position

public static int smallestSearch(int[] array,int start,int end)
{   
        if(start==end)
        return array.length;

        int mid=(start+end)/2;

        if(array[mid]>array[mid+1])
        return min(mid+1,smallestSearch(array,start,mid),smallestSearch(array,mid+1,end));
        else
        return min(smallestSearch(array,start,mid),smallestSearch(array,mid+1,end));
}

public static int min(int a,int b)
{
    if(a==b)
    return a;
    else if(a<b)
        return a;
        else 
        return b; 
}
public static int min(int a,int b,int c)
{
    if(a<c)
    {
        if(a<b)
        {
            return a;
        }
        else
        {
            return b;
        }
    }
    else
    {
        if(b<c)
        return b;
        else
        return c;
    }

}

Answer 10

The following algorithm takes log(n) time. Assuming the array has no duplicate.

public int findMin(int[] num) {
    if(num.length == 0) return -1
    int r = num.length-1, l = 0;
    while(l<r){
        if(num[l]<=num[r]) return num[l]; //when not rotated, return the left most value
        int mid = (r+l)/2;
        if(num[mid]<num[r]){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    return num[l];
}

Answer 11

    public int findMin(int[] num) {
        return findMin(num, 0, num.length-1);
    }
    public int findMin(int[] num, int left, int right){
        if(left==right) return num[left];
        if(left+1==right) return Math.min(num[left], num[right]);
        int mid = (left+right)/2;
        if(num[mid]>num[right]){
            return findMin(num,mid+1,right);
        }else if(num[mid]<num[right]){
            return findMin(num,left,mid);
        }else{
            if(num[mid]==num[left]){
                return Math.min(findMin(num,left,mid), findMin(num,mid,right));
            }else{
                return findMin(num,left,mid);
            }
        }
    }

Answer 12

In case any one needs it.. My implementation in java..

takes care of sorted/unsorted ascending//descending order usecases..

drawback is it will still perform log n steps to find min value in a perfectly sorted set with no rotation.

http://ideone.com/fork/G3zMIb

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int [] a = {3,3,0,2,2,2,2,1,2,2,2,2,2,2,2,2,2};
        System.out.println(recursiveSplit(a,0,a.length-1));
    }

    public static int findMin(int x, int y){
        if(x<=y){
            return x;
        }else{
            return y;
        }
    }

    public static int recursiveSplit(int[] arr , int a , int b){
        int mid = (int) Math.floor(a + (b-a)/2);
        int h1_l = a;
        int h1_u = mid;
        int h2_l = mid+1;
        int h2_u = b;
        int x=0;
        int y=0;

        //single element
        if(a==b){
            return arr[a];
        }

        //adjacent positions
        if(h1_u-h1_l==1){
            x=findMin(arr[h1_u],arr[h1_l]);
        }else{
            //else split
            x=recursiveSplit(arr,h1_l,h1_u);
        }

        if(h2_u-h2_l==1){
            y=findMin(arr[h2_u],arr[h2_l]);
        }else{
            y=recursiveSplit(arr, h2_l,h2_u);
        }

        return findMin(x, y);
    }
}

Errors/suggestions/failed usecases are welcomed

Answer 13

Find Min index in circular sorted array

Example : [7,8,9,1,2,3,4,5,6]

int findMinIndex(int []a, int start, int end)
{
    int mid = (start + end)/2;

    if (start - end == 1)
        if(a[start] < a[end])
        return start;
        else
        return end;

    if (a[mid] > a[end]){

    return findMinIndex(a,mid,end);

    }

    else{

      return  findMinIndex(a,start,mid);
    }

    return -1; //Not found
}

Answer 14

This can be done in O(1) time best case, O(n) time worst case, and O(lg n) time on average.

For a rotated sorted array, if the first element in the array is less than the last element in the array, then the sorted array is not rotated (or rotated 0 position). The minimum element is simply the first element.

If the middle element is less than the last element, then the minimum element is in [first, middle].

If the middle element is greater than the last element, then the minimum element is in [middle + 1, last].

If the middle element is equal to the last element, then there are two sub-cases:

1. the first element is larger than the last element, in which case the minimum element is in [first, middle + 1];
2. the first element is equal to the last element, in which case it is inconclusive to reject either half of the array. Reduce to linear search. For example, for arrays such as [5,5,5,1,5] and [5,1,5,5,5], it is impossible by just examining the first, last and middle element (since they are all equal) which half of the array the minimum element lies.

I wrote the following code in C++ to solve this problem, which should handle all cases (empty array, repeated elements).

template <typename Iterator>
Iterator rotated_min(Iterator begin, Iterator end)
{
    while (begin != end)
    {
        if (*begin < *(end - 1))
        {
            return begin;
        }
        Iterator mid = begin + (end - 1 - begin) / 2;
        if (*mid < *(end - 1))
        {
            end = mid + 1;
        }
        else if (*mid > *(end - 1))
        {
            begin = mid + 1;
        }
        else 
        {
            if (*begin > *(end - 1))
            {
                end = mid + 1;
                ++begin;
            }
            else 
            {
                //reduce to linear search
                typename ::std::iterator_traits<Iterator>::value_type min_value = *begin;
                Iterator min_element = begin;
                for (Iterator i = begin + 1; i != end; ++i)
                {
                    if (*i < min_value)
                    {
                        min_value = *i;
                        min_element = i;
                    }
                }
                return min_element;
            }
        }
    }
    return begin;
}

Answer 15

My code is below with the algorithm as comments. Works even for the repeated elements.

//Find Min in Rotated Sorted Array
//Example: int array[10] = {7, 8, 9, 10, 11, 12, 3, 4, 5, 6};
// Min in the above array is 3
// Solution: Recursively search (Modified binary search) for the Pivot where is the smallest Element is present
// Algorithm: 
// 1) Find the Mid of the Array 
// 2) call the recursive function on segment of array in which there is a deviation in the order
// If (A[low] > A[mid]) array segment in which deviation in the order present is (low, mid)
// If (A[low] < A[mid]) array segment in which deviation in the order present is (mid + 1, high) 
// Time Complexity: O(logn)
// Space Complexity: is of the recursive function stack that is being used

#define MIN(x,y) (x) <= (y) ? (x): (y)

int MininRotatedSortedArray(int A[], int low, int high)
{
    if(low > high)
        return -1;

    if(low == high - 1)
        return MIN(A[low], A[high]);

    int mid = low + (high - low)/2;

    if(A[low] > A[mid])
        return MininRotatedSortedArray(A, low, mid);
    else if(A[low] < A[mid])
        return MininRotatedSortedArray(A, mid + 1, high);
    else
        return A[mid];
}

Answer 16

Method 1:

You can do this in O(logN) time.

Use a modified binary search to find the point of rotation which is an index i such that
arr[i] > arr[i+1].

Example:

[6,7,8,9,1,2,3,4,5]
       ^
       i

The two sub-arrays
(arr[1], arr[2], .., arr[i]) and
(arr[i+1], arr[i+2], ..., arr[n]) are sorted.

The answer is min(arr[1], arr[i+1])

Method 2:

When you split the sorted, rotated array into two halves (arr[1],..,arr[mid]) and (arr[mid+1],..,arr[n]), one of them is always sorted and the other always has the min. We can directly use a modified binary search to keep searching in the unsorted half

// index of first element
l = 0

// index of last element.
h = arr.length - 1

// always restrict the search to the unsorted 
// sub-array. The min is always there.
while (arr[l] > arr[h]) {
        // find mid.
        mid = (l + h)/2
        // decide which sub-array to continue with.
        if (arr[mid] > arr[h]) {
                l = mid + 1
        } else {
                h = mid
        }
}
// answer
return arr[l]