Problem Statement
Given an integer array nums of size n, sorted in ascending order with distinct values. The array has been right rotated an unknown number of times, between 1 and n. Determine the number of rotations performed on the array.
Examples
Example 1:
Input: nums = [4, 5, 6, 7, 0, 1, 2, 3]
Output: 4
Explanation: The original array should be [0, 1, 2, 3, 4, 5, 6, 7]. So we can notice that the array has been roated 4 times.Input 2:
Input: nums = [3, 4, 5, 6, 1]
Output: 1
Explanation: The original array should be [1, 3, 4, 5, 6]. So, we can notice that the array has been roated 1 time.Different Approaches
1️⃣ Brute Force (Linear Search)
Intuition:
The straightforward solution to this problem involves performing a simple linear search to find the minimum element of the array by comparing each element individually. The index at which the minimum element is found corresponds to the number of times the array has been rotated. Since the array was initially sorted, the smallest element would have been at the front. Therefore, the index of this smallest element gives the number of rotations because it indicates how many positions the array has been shifted.
Approach:
- First, declare an
ansand an index variable initialized with aINT_MAXand-1respectively. - Next, iterate through the array and compare each element with the variable called
ans. Whenever an element is encountered such that it is smaller thanans, updateanswith that value and also update theindexvariable with the current index. - Finally, we will return
indexas our answer.
Dry Run:
Initialization:
minimum = INT_MAX
index = -1
+-----+-----+-----+-----+-----+
arr | 3 | 4 | 5 | 1 | 2 |
+-----+-----+-----+-----+-----+
0 1 2 3 4First Iteration:
minimum = INT_MAX
index = -1
+-----+-----+-----+-----+-----+
arr | 3 | 4 | 5 | 1 | 2 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
i
If arr[index] < minimum
True
set minimum = min(minimum, arr[index])
minimum = min(INT_MAX, 3)
minimum = 3
index = i
index = 0
i++Second Iteration:
minimum = 3
index = 0
+-----+-----+-----+-----+-----+
arr | 3 | 4 | 5 | 1 | 2 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
i
If arr[index] < minimum
False
i++Third Iteration:
minimum = 3
index = 0
+-----+-----+-----+-----+-----+
arr | 3 | 4 | 5 | 1 | 2 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
i
If arr[index] < minimum
False
i++Fourth Iteration:
minimum = 3
index = 0
+-----+-----+-----+-----+-----+
arr | 3 | 4 | 5 | 1 | 2 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
i
If arr[index] < minimum
True
set minimum = min(minimum, arr[index])
minimum = min(3, 1)
minimum = 1
index = i
index = 3
i++Fifth Iteration:
minimum = 1
index = 3
+-----+-----+-----+-----+-----+
arr | 3 | 4 | 5 | 1 | 2 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
i
If arr[index] < minimum
False
i++Loop Termination:
minimum = 1
index = 3
+-----+-----+-----+-----+-----+
arr | 3 | 4 | 5 | 1 | 2 |
+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
As i exceeds the bounds of the array,
So loop will terminate
and return index (3), which means
this is rotated to right three times.Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find the number of
rotations in a rotated sorted array */
int findKRotation(vector<int>& nums) {
// Get the size of the array
int n = nums.size();
/* Initialize variables to store
minimum value and its index*/
int ans = INT_MAX, index = -1;
/* Iterate through the array to
find the smallest element */
for (int i = 0; i < n; i++) {
if (nums[i] < ans) {
ans = nums[i];
index = i;
}
}
// Return the index of smallest element
return index;
}
};
int main() {
vector<int> nums = {4, 5, 6, 7, 0, 1, 2, 3};
// Create an object of the Solution class
Solution sol;
int ans = sol.findKRotation(nums);
// Print the result
cout << "The array is rotated " << ans << " times.\n";
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N), whereNis size of the array. As the array is being traversed only once using a single loop. - Space Complexity: As no additional space is used, so the Space Complexity is
O(1).
2️⃣ Optimal (Binary Search)
Intuition:
The idea here is to use the binary search algorithm to determine the index at which the minimum element of the array is located. This index will indicate the number of times the array has been rotated. Observing this, it's analogous to finding the minimum element in a rotated sorted array. Here, the additional requirement is to return the index of the minimum element rather than the element itself.
Approach:
- First, initialize few variables:
low to 0(beginning of the array,high to (end of the array),ans to Integer MAX_VALUEto track the minimum element found during the search,index to -1to store the index of the minimum element. - Use a binary search strategy to efficiently find the minimum element in the rotated sorted array, which directly gives the number of rotations. While low is less than or equal to high, calculate the middle index mid.
- If element at
lowis less than or equal to element athigh, the search space is already sorted. In this case, element atlowis the smallest element, representing the start of the rotation. Updateansandindexaccordingly and break out of the loop. - Determine whether the left part of the array is sorted or the right part of the array is sorted
- If the left part is sorted (element at (low) <= element at (mid)):
- Check if element at (low) is less than
ans. If so, updateansandindexto reflect the new minimum element found. - Adjust
lowtomid + 1to search the right half, as the rotation point (minimum element) must be on the right side.
- Check if element at (low) is less than
- If the right part is sorted (element at (low) > element at (mid)):
- Check if element at (mid) is less than
ans. If so, updateansandindexaccordingly. - Adjust
hightomid - 1to search the left half.
- Check if element at (mid) is less than
- Once the loop completes,
indexwill hold the index of the minimum element, which represents the number of rotations. Returnindexas the answer.
Dry Run:
Initialization:
minimum = INT_MAX
index = -1
+-----+-----+-----+-----+-----+
arr | 3 | 4 | 5 | 1 | 2 |
+-----+-----+-----+-----+-----+
0 1 2 3 4First Iteration:
minimum = INT_MAX
index = -1
Left = 0
Right = 4
Mid = Left + (Right - Left) / 2
= 0 + (4 - 0) / 2
= 4 / 2
= 2
+-----+-----+-----+-----+-----+
arr | 3 | 4 | 5 | 1 | 2 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^ ^ ^
| | |
Left Mid Right
Is arr[Left] <= arr[Right]
3 <= 2
False, this means array is not sorted at complete.
Is arr[Left] <= arr[Mid]
3 <= 5
True
If arr[Left] < minimum
3 < INT_MAX
True
Set minimum = arr[Left]
minimum = 3
index = Left
index = 0
// Go to Right side now (Eliminate Left Half)
Left = Mid + 1
= 2 + 1
= 3Second Iteration:
minimum = 3
index = 0
Left = 3
Right = 4
Mid = Left + (Right - Left) / 2
= 3 + (4 - 3) / 2
= 3 + 1/ 2
= 3 + 0
= 3
+-----+-----+-----+-----+-----+
arr | 3 | 4 | 5 | 1 | 2 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^ ^
| |
Left Right
Mid
Is arr[Left] <= arr[Right]
1 <= 2
True, this means array is sorted at complete.
If arr[Left] < minimum
1 < 3
True
Set minimum = arr[Left]
minimum = 1
index = Left
index = 3
Since this part of the array was sorted
and we set the very extreme left element
to the minimum.
Now we no further need to check again.
So break the loop
and return index, which is 3.Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find the number of
rotations in a rotated sorted array */
int findKRotation(vector<int>& nums) {
int low = 0, high = nums.size() - 1;
int ans = INT_MAX;
int index = -1;
while (low <= high) {
int mid = (low + high) / 2;
/* Search space is already sorted
then nums[low] will always be
the minimum in that search space */
if (nums[low] <= nums[high]) {
if (nums[low] < ans) {
index = low;
ans = nums[low];
}
break;
}
// If left part is sorted update the ans
if (nums[low] <= nums[mid]) {
if (nums[low] < ans) {
index = low;
ans = nums[low];
}
// Eliminate left half
low = mid + 1;
}
else {
/*update the ans if it
is less than nums[mid] */
if (nums[mid] < ans) {
index = mid;
ans = nums[mid];
}
// Eliminate right half
high = mid - 1;
}
}
//Return the index as answer
return index;
}
};
int main() {
vector<int> nums = {4, 5, 6, 7, 0, 1, 2, 3};
// Create an object of the Solution class
Solution sol;
int ans = sol.findKRotation(nums);
// Print the result
cout << "The array is rotated " << ans << " times.\n";
return 0;
}
Complexity Analysis:
- Time Complexity:
O(logN), whereNis size of the array. As binary search algorithm is being applied to solve the problem. - Space Complexity: As no additional space is used, so the Space Complexity is
O(1).