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

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.

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!


Posted

in

,

by

Comments

Leave a Reply

Discover more from The Full Stack Developer

Subscribe now to keep reading and get access to the full archive.

Continue reading