Data Structures and Algorithms in Java – Arrays – Minimum in Rotated Sorted Array

Problem:

Given an array of integers which are sorted and rotated , find the minimum element.

Rotated means the numbers at the end of the array are transferred to the start of the array.

For example,

If the sorted array [1,2,3,4,5] is rotated twice , it becomes [4,5,1,2,3]

If the sorted array [6,8,9] is rotated once , it becomes [9,6,8]

Input:

input = [3,4,5,1,2]

Output:

1 since it is the least element in the array

Try out the solution here:

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array

Advertisements

Solution:

The brute force solution for this problem can be obtained in O(n) time complexity by traversing the array and comparing each element if it is the smallest traversed so far.

Here is the code:

class Solution {
    public int findMin(int[] nums) {
        
        
        int min = nums[0];
        
        
        for(int i=1;i<nums.length;i++){
            
            
            if(min > nums[i]){
                
           
                
                min = nums[i];
            }
        }
        
        return min;
    }
}

A better solution of time complexity O(logn) exists.

Hint:

  1. Find out which half of your array you need to search.
  2. This can be found out by comparing the middle element to the last element in the array
  3. If middle element is greater than the last element then you have to search the second half
  4. Similarly if middle element is less than the last element you have to search the first half.

Algorithm:

As shown in the hint , you can solve this problem through Divide and Conquer strategy.

STEP1: Initialize three variables to denote the first index , the middle index and the last index of the array

STEP2: Until only one element is left , check if middle element is less than the last element , if so update the last index to the middle element so that search continues in the first half

STEP2 a: In the same loop , check if middle element is greater than the last element , if so update the start index to the next index of the middle element so that the search continues in the second half

STEP2 b: If there is only one element left (start index = last index) return the element

For example let’s take the input:

input = [3,4,5,1,2]

Let’s initialize three variables:

low (startIndex) = 0

high (lastIndex) = 4

middle = 4/2 = 2

First iteration:

low = 0, high = 4, middle = 2

input[middle]=5

input[high] = 2

input[middle] is greater than input[high]

So low = middle +1 = 2+1=3

Now the search continues in the second half of the array [1,2]

middle = low + (high-low)/2 = 3+ (4-3)/2 = 3

Iteration 2:

low = 3, high = 4, middle = 3

input[middle] = 1

input[high] = 2

input[middle]< input[high]

So , high = middle => high = 3

Now the search continues in the first half which is [1]

middle = 3+ (3-3)/0 = 3

At this stage low also equals high , so we return the current element which is 1.

Advertisements

Code:

Here is the code:

class Solution {
    public int findMin(int[] nums) {
     
        
        
        int low = 0;
        
        int middle = nums.length /2;
        
        int high = nums.length -1;
        
        
        
        while(low <= high){
            
           
            if(low == high){
                
                return nums[low];
            }
            
            if(nums[middle] < nums[high]){
                
                
                high = middle;
            }else if(nums[middle] > nums[high]){
                
                
                low = middle +1;
            }
            
            
            
              middle = low+ ((high - low) / 2);
            
          
            
        }
        
        return -1;
    }
}

This is a slight variation of the last solution given in geeks for geeks here:

https://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/

and it turned out to be 100% faster than all other submissions:

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s