Rotated Array

Posted: 15 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You're given a sorted array that has now been rotated 'K' times, which is unknown to you. Rotation here means that every element is shifted from its position to right in each rotation and the last element simply shifts to the first position. For example: 1 2 3 4, after one rotation becomes 4 1 2 3. Your task is to find the minimum number in this array.

Note :
All the elements in the array are distinct. 
Input Format :
The first line contains an integer 'T' denoting the number of test cases.
The first line of each test case contains an integer 'N', the size of the array.
The second line of each test case contains 'N' space-separated integers.
Output Format :
For each test case, print the minimum number in the given array. 

Print the output of each test case in a separate line.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Follow Up :
Can you solve this using not more than O(log(N)) time and O(1) space complexities?
Constraints :
1 <= T <= 10^2
1 <= N <= 10^4
1 <= ARR[i] <= 10^9

Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array ‘ARR’ respectively, and 'ARR[i]' denotes the 'i-th' element of the array 'ARR'. 

Time Limit: 1 sec
Approach 1

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.

Try Problem