Given an array of unique integers that was originally sorted in ascending order and then rotated a certain number of times to the right, find the total number of times the array was rotated.
Example 1
Input: nums = [3, 4, 5, 1, 2]
Output: 3
Explanation: The original sorted array was [1, 2, 3, 4, 5]. It was rotated 3 times to the right to become [3, 4, 5, 1, 2].
Example 2
Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 4
Explanation: The original sorted array was [0, 1, 2, 4, 5, 6, 7]. After rotating it 4 times, we get the input array as [4, 5, 6, 7, 0, 1, 2].
Brute Force Approach
If we look closely at how a sorted array behaves when it is rotated, a clear pattern emerges. Every time we rotate the array to the right, the smallest element moves one step to the right.
This means the index of the minimum element in the array is exactly equal to the number of times the array has been rotated. To solve this, we just need to scan the entire array, find the smallest number, and return its position.
Algorithm
Create a variable to store the minimum value and set it to the first element of the array.
Create another variable to store the index of this minimum value and set it to 0.
Loop through the array from start to finish.
Compare each element with the current minimum value. If you find a smaller element, update both the minimum value and its index.
After checking all elements, return the index.
Dry Run
Find Number of Times array is Rotated Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Function to find how many times a sorted array has been rotated */ int findKRotation(vector<int> &nums) { // Assume the first element is the minimum int minVal = nums[0]; // Store the index of the assumed minimum int index = 0; // Loop through the entire array to find the actual minimum for (int i = 0; i < nums.size(); i++) { // Check if the current element is smaller than our recorded minimum if (nums[i] < minVal) { // Update the minimum value minVal = nums[i]; // Update the index where this new minimum was found index = i; } } // The index of the minimum element is the number of rotations return index; }};// driver code startsint main() { Solution solution; vector<int> nums = {3, 4, 5, 1, 2}; int result = solution.findKRotation(nums); cout << result << endl; return 0;}Complexity Analysis
Time Complexity: O(N), because we look at every element in the array exactly once to find the minimum.
Space Complexity: O(1), because constant space is used.
Optimal Approach
We can see one observation: every time the array is rotated the array minimum moves 1 position right, this makes the problem exactly similar to Find Minimum in Rotated Sorted Array.
When an array is sorted and rotated, dividing it into two halves will always leave at least one half completely sorted. The minimum element is always the pivot point where the sorting breaks.
If the left half is perfectly sorted, the smallest element in that section is simply the very first element. We can record its index as a potential answer and then ignore the entire left half because any other number there will just be larger.
We then repeat this process on the unsorted right half to see if we can find an even smaller number. We do the same logic if the right half is the one that is sorted.
Algorithm
Initialize a pointer at the start
(low)and a pointer at the end(high)of the array, defining the search space.Track the minimum value found so far and its corresponding index.
Calculate the middle position using low + (high-low)/2 to avoid integer overflow issue.
Check if the entire current range from low to high is sorted. If it is, compare the first element with our current minimum, update if needed, and break out early because we have found the smallest element in the whole search space.
If the left half is sorted,
the smallest element on the left side is at the low pointer. Compare it to our minimum value, save the index if it is smaller, and then move the search to the right half.
If the right half is sorted,
the smallest element on the right side is at the mid pointer. Compare it to our minimum value, save the index if it is smaller, and then move the search to the left half.
Return the final recorded index.
Dry Run
Find Number of Times Array is Rotated Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Function to find how many times a sorted array has been rotated using binary search */ int findKRotation(vector<int> &nums) { // Initialize the low pointer to the beginning int low = 0; // Initialize the high pointer to the end int high = nums.size() - 1; // Track the minimum value found, starting with a very large number int ans = INT_MAX; // Track the index of the minimum value found int index = -1; // Loop until the search space is exhausted while (low <= high) { // If the current search space is fully sorted if (nums[low] <= nums[high]) { // Check if the first element is the overall minimum if (nums[low] < ans) { // Update the answer and index ans = nums[low]; index = low; } // Break early since the rest of the elements will only be larger break; } // Calculate the middle point of the current search space int mid = low + (high - low) / 2; // Check if the left half is sorted if (nums[low] <= nums[mid]) { // Check if the smallest element in the left half is a new minimum if (nums[low] < ans) { // Update the index and the minimum value index = low; ans = nums[low]; } // Discard the left half and search the right half low = mid + 1; } // Otherwise, the right half must be sorted else { // Check if the smallest element in the right half is a new minimum if (nums[mid] < ans) { // Update the index and the minimum value index = mid; ans = nums[mid]; } // Discard the right half and search the left half high = mid - 1; } } // Return the final index which represents the number of rotations return index; }};// driver code startsint main() { Solution solution; vector<int> nums = {4, 5, 6, 7, 0, 1, 2}; int result = solution.findKRotation(nums); cout << result << endl; return 0;}Complexity Analysis
Time Complexity: O(log2 N), because we divide our search space in half at each step, significantly reducing the number of elements we have to check.
Space Complexity: O(1), because we only allocate a few variables for tracking our boundaries and our answer.
Interview follow-up Questions
In a strictly sorted array that starts at index 0, the smallest element is at position 0. Every single time you shift all elements to the right by one position, the smallest element also moves to the right by one index. Therefore, its final index perfectly counts how many shifts or rotations happened.
Be the first to add a comment.