Find the Rotation Count in Rotated Sorted array in Java
In this tutorial, we are going to find the rotation count in rotated sorted array in Java. The aim is to determine the value of k given an array arr[] of size N that has distinct numbers ordered in increasing order and has been right rotated (i.e., the last element will be cyclically relocated to the array's starting position) k times.
Examples:
Example 1:
Input: arr[] = {19, 18, 1, 3, 6, 12}
Output: 2
Explanation: There must be a {1, 3, 6, 12, 18, 19} initial array.
After twice rotating the original array, we obtain the given array.
Example 2:
Input: arr[] = {7, 8, 15, 20, 4}
Output: 4
Explanation: There must be a {4, 7, 8, 15, 20} initial array.
After rotating four times the original array, we obtain the given array.
Example 3:
Input: arr[] = {7, 8, 14, 15, 20};
Output: 0
Approach 1: Using linear search
ALGORITHM:
Step 1: Set up two variables at first, one for the minimum value and the other for its index.
Step 2: Go through the array beginning and ending.
Step 3: Determine the lowest value and the index at which it is kept.
Step 4: Give back the minimal value's index.
Filename: RotatedArray.java
import java.io.*;
import java.lang.*;
import java.util.*;
public class RotatedArray {
// Gives the number of rotations for an array that has been rotated after being sorted in ascending order.
static int countRotations(int array[], int size)
{
int minimum = array[0], minIndex = 0;
for (int i = 0; i < size; i++) {
if (minimum > array[i]) {
minimum = array[i];
minIndex = i;
}
}
return minIndex;
}
public static void main(String[] args)
{
int array[] = { 16, 20, 1, 3, 6, 15 };
int size = array.length;
System.out.println(countRotations(array, size));
}
}
Output:
2
Complexity analysis:
Time complexity: The time complexity of the program is O(N).
Space complexity: The space complexity of the program is O(1).
Approach 2: Using rotation point detection approach
ALGORITHM:
Step 1: Go through the array from 0 to n.
Step 2: Return index + 1, when the current element is larger than the next element and make sure that i+1 must be less then the size of array length.
Step 3: Else return 0.
Filename: RotatedSortedArray.java
import java.io.*;
public class RotatedSortedArray
{
static int countRotations(int array[], int size)
{
// Verify if the array is rotated
if (array[0] > array[size - 1])
{
// Go through with the array
for (int i = 0; i < size; i++)
{
// Element index where is greater than the next element
if (array[i] > array[i + 1])
return i + 1;
}
}
return 0;
}
public static void main(String[] args)
{
int array[] = { 16, 20, 1, 3, 6, 15 };
int size = array.length;
System.out.println(countRotations(array, size));
}
}
Output:
2
Complexity analysis:
Time complexity: The time complexity of the program is O(N).
Space complexity: The space complexity of the program is O(1).
Approach 3: Using binary search
ALGORITHM:
Step 1: Determine which element in the array is the smallest.
Step 2: Examine the condition for the middle element by contrasting with the components that are (mid-1)th and (mid+1)th.
Step 2.1: The middle element must be smaller than the final element in order for the minimum element to be in the left half if it is not at the middle (neither mid nor mid+1).
In the right side is the other minimum component.
Filename: RotatedCount.java
import java.io.*;
import java.lang.*;
import java.util.*;
public class RotatedCount
{
// Returns the number of rotations for an array that has been rotated after being sorted in ascending order.
static int countRotations(int array[], int low, int high)
{
if (high < low)
return 0;
if (high == low)
return low;
int mid = low + (high - low) / 2;
if (mid < high && array[mid + 1] < array[mid])
return (mid + 1);
// Verify that the mid element is the minimum one.
if (mid > low && array[mid] < array[mid - 1])
return mid;
// Determine if we should proceed to the left or right half.
if (array[high] > array[mid])
return countRotations(array, low, mid - 1);
return countRotations(array, mid + 1, high);
}
public static void main(String[] args)
{
int array[] = { 16, 20, 1, 3, 6, 15 };
int N = array.length;
System.out.println(countRotations(array, 0, N - 1));
}
}
Output:
2
Complexity analysis:
Time complexity: The time complexity of the program is O(log N).
Space complexity: The space complexity of the program is O(log N).
Approach 4: Using modified binary search
ALGORITHM:
Step 1: Use two pointers, l (left) and r (right) at the beginning of the procedure.
Step 2: Initialize twp pointers to the array's first and end indices, respectively.
Step 3: Determine the middle index m at each iteration of the loop by averaging l and r.
step 4: Compare the values at index m and index r.
step 5: Locate the minimal element to the left of m or at index m itself if the value at index m is smaller than the value at index r.
Step 6: Keep going the loop until l equals r, which means that there is only one element left in the search space.
Step 7: Denote the lowest member in the rotated sorted array, is now returned by the algorithm that the value is at index l.
Filename: MinElement.java
public class MinElement {
public int findMinimum(int[] numbers) {
int indexl = 0;
int indexR = numbers.length - 1;
while (indexl < indexR) {
int m = (indexl + indexR) / 2;
if (numbers[m] < numbers[indexR])
indexR = m;
else
indexl = m + 1;
}
return numbers[indexl];
}
public static void main(String[] args) {
MinElement solution = new MinElement();
int[] numbers1 = {4, 5, 6, 7, 0, 1, 2};
int[] numbers2 = {3, 4, 5, 1, 2};
int[] numbers3 = {1};
System.out.println("Minimum element in nums1: " + solution.findMinimum(numbers1));
System.out.println("Minimum element in nums2: " + solution.findMinimum(numbers2));
System.out.println("Minimum element in nums3: " + solution.findMinimum(numbers3));
}
}
Output:
Minimum element in nums1: 0 Minimum element in nums2: 1 Minimum element in nums3: 1
Complexity analysis:
Time complexity: The time complexity of the program is O(log n).
Space complexity: The space complexity of the program is O(1).