Find Minimum in Rotated Sorted Array

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
163 upvotes
Asked in companies
OlaPaytm (One97 Communications Limited)Amazon

Problem statement

You are given an array 'arr' of size 'n' having unique elements that has been sorted in ascending order and rotated between 1 and 'n' times which is unknown.


The rotation involves shifting every element to the right, with the last element moving to the first position. For example, if 'arr' = [1, 2, 3, 4] was rotated one time, it would become [4, 1, 2, 3].


Your task is to find the minimum number in this array.


Note : 
All the elements in the array are distinct.


Example : 
Input: arr = [3,4,5,1,2]

Output: 1

Explanation: The original array was [1,2,3,4,5] and it was rotated 3 times.


Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'n', the size of the array.
The second line contains 'n' space-separated integers.


Output Format : 
The only line contains the minimum number in the given array.


Note : 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Sample Input 1 :
4
3 4 1 2


Sample Output 1 :
1


Explanation of Sample Input 1 :
The original array was [1, 2, 3, 4] and it was rotated 2 times.


Sample Input 2 :
6
25 30 5 10 15 20


Sample Output 2 :
5


Explanation of Sample Input 2 :
The original array was [5, 10, 15, 20, 25, 30] and it was rotated 2 times.


Expected Time Complexity:
Try to solve this with O(log(n)) time complexity.


Constraints :
1 <= n <= 10^5
1 <= arr[i] <= 10^9

Time Limit: 1 sec
Hint

Try to think of a brute approach to solve the problem.

Approaches (2)
Brute Force

The basic approach to find the minimum element is to traverse the whole array and keep updating the minimum value as we traverse that array.

  • This is somewhat similar to a linear search. Start by assigning the first element(arr[0]) of the array to a variable named min.
  • Then iterate the array using a variable i from 1 till n and check if the current element(arr[i]) is less than min. If arr[i] is less than min then assign arr[i] to min.
  • Now when we come out of this loop, min will give us the minimum element, which is our answer.

Example: 3 4 1 2

Initialize min = 3 and start traversing the array. When we reach 4 we see that 4 > 3 hence we don’t update min. Now we see that 1 < 3, therefore we update min. Now min = 1. Now finally we reach 2 and we see that 2 > 1, hence we don’t update min. Now we have reached the end of the array, hence we print our answer(min), which is equal to 1.

Time Complexity

O(N), where N is the number of elements in the array.

 

We are traversing the whole array once. We will be accessing all the N elements. Hence, the overall time complexity is O(N).

Space Complexity

O(1).

 

We are using extra constant memory. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Find Minimum in Rotated Sorted Array
Full screen
Console