# Rotated Array

Posted: 15 Jan, 2021

Difficulty: Moderate

#### 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.

Approach 2

As it is given in the hint itself, we want to decrease the search space in order to optimize our solution. Hence we want to apply the technique of divide and conquer for this. Here use a binary search algorithm to do so.

- We start by making two variables named low and high, where low = 0 and high = n-1. Now we run a loop that will run till low <= high. We also make another variable mid, which is equal to (low+high)/2.
- Now we make 4 cases and accordingly solve our problem.
- Case 1: arr[low] <= arr[high]
- We return arr[low] since the array is sorted, arr[low] will be the minimum element.

- Now we make a variable named next which will be equal to (mid+1)%n and previous which will be equal to (mid+n-1)%n.
- Case 2: (arr[mid] <= arr[next]) and (arr[mid] <= arr[previous])
- We return arr[mid]. We do this because on observing we can see that only the minimum element will have this special property where it is smaller than both of its neighbours. Example 4 1 2 3, here you can see that only 1, which is the minimum element, in this case, is the element that is smaller than both of its neighbours 4 and 2.

- Case 3: arr[mid] <= arr[high]
- Here we see that if the current middle element is less than the current high element, that means the minimum element won't be present in the right half of the array(with reference to mid). Hence we discard this search space and make high = mid-1.

- Case 4: arr[mid] >= arr[low]
- This case is similar to Case 3, the only difference is that here we can observe that if our current middle element is greater than the current lower element, the minimum element won’t be present in the left half of the array(with reference to mid). Hence we discard this search space and make low = mid+1.

SIMILAR PROBLEMS

# Game of 3

Posted: 11 Jul, 2021

Difficulty: Easy

# Lexicographic Permutation Rank

Posted: 13 Jul, 2021

Difficulty: Moderate

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy