Problem Statement: Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums[] = [0,1,2,4,5,6,7] might become:
- [4,5,6,7,0,1,2] if it was rotated 4 times.
- [0,1,2,4,5,6,7] if it was rotated 7 times.
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
Examples:
Example 1: Input: nums=[3,4,5,1,2] Output: 1 Explanation: Original Array was rotated 3 times Example 2: Input: nums=[4,5,6,7,0,1,2] Output:0 Explanation: Original Array was rotated 4 times
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Brute Force Solution
Approach: A basic approach would be to search linearly through the array. Keep a variable minVal=INT_MAX and keep comparing and updating with every element in the array.
Example: [4,5,1,2,3]
Here take, minVal=INT_MAX and start comparing, First, we compare with 4 so minVal is updated to 4. The next 5 get compared, and minVal is unchanged. And so on and at the end minVAl=1.
Code:
C++ Code
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
int ar[5]={4,5,1,2,3};
int minVal=INT_MAX,i;
for(i=0;i<5;i++){
minVal=min(minVal,ar[i]);
}
cout<<"Minimum Value is "<<minVal<<endl;
return 0;
}
Output: Minimum Value is 1
Time Complexity : O(n)
Space Complexity: O(1)
Java Code
import java.util.*;
class TUF{
public static void main(String args[]){
int ar[]={4,5,1,2,3};
int minVal=Integer.MAX_VALUE,i;
for(i=0;i<5;i++){
minVal=Math.min(minVal,ar[i]);
}
System.out.println("Minimum Value is "+minVal);
}
}
Output: Minimum Value is 1
Time Complexity : O(n)
Space Complexity: O(1)
Optimal Approach
We can optimize the solution using binary search. Since the array is sorted we can see that even after rotation one part of the array will still remain sorted.
For ex : {5,1,2,3,4} here 3,4 is sorted Ex : [4,5,6,7,0,1,2] left part is sorted from 4 to 7
We take a left pointer, a right pointer, and a mid. So if the left side is sorted, then the leftmost element is the smallest in that part. So we update our minVal and check on the right side. If the right part is sorted then mid is going to be the smallest value for that part, we update the result as min(mid,minVal).
To know which part is sorted, We can observe that while rotation we are bringing the largest element ahead, so if nums[mid]>=nums[left],i.e, if an element greater than it exists further in the array, then that part is sorted.
if(nums[mid]>=nums[left])
Else we know the right part is sorted. Because at all times at least one side will be sorted.
Another optimization would be if(nums[left]<nums[right])that would mean the whole array between left and right is sorted. We can update the results and break them.
Example:{4,5,1,2,3} L=0,R=4,Mid=2 Check if arr[mid]> = arr[left], its not, So right part is sorted. We take res=min(res,arr[mid], res=1, and R = mid-1. L=0,R=1,Mid=0; arr[mid]>=arr[left] = true. So we update res as min(res,arr[left]), res=1; Since left part was sorted L=mid+1. Which makes L=R L=1,R=1,Mid=1 arr[mid]>=arr[left] = true. So we update res as min(res,arr[left]) ,res=1; Since left part was sorted L=mid+1. Which makes L=2. Loop Stops.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
int main() {
int nums[5] = {4,5,1,2,3};
int i;
int left = 0, right = 4, minVal = INT_MAX;
while (left <= right) {
if (nums[left] < nums[right]) {
minVal = min(minVal, nums[left]);
break;
}
int mid = left + (right - left) / 2;
if (nums[left] <= nums[mid]) {
minVal = min(minVal, nums[left]);
left = mid + 1;
} else {
minVal = min(minVal, nums[mid]);
right = mid - 1;
}
}
cout << "Minimum Value is " << minVal;
return 0;
}
Output: Minimum Value is 1
Time Complexity : O(logn)
Space Complexity: O(1)
Java Code
import java.util.*;
class TUF{
public static void main(String args[]) {
int nums[] = {4,5,1,2,3};
int i;
int left = 0, right = 4, minVal = Integer.MAX_VALUE;
while (left <= right) {
if (nums[left] < nums[right]) {
minVal = Math.min(minVal, nums[left]);
break;
}
int mid = left + (right - left) / 2;
if (nums[left] <= nums[mid]) {
minVal = Math.min(minVal, nums[left]);
left = mid + 1;
} else {
minVal = Math.min(minVal, nums[mid]);
right = mid - 1;
}
}
System.out.println("Minimum Value is "+minVal);
}
}
Output: Minimum Value is 1
Time Complexity : O(logn)
Space Complexity: O(1)
Special thanks to Rishika Gupta for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article