(5 votes, average: 3.60 out of 5)Given an array of n elements, write an algorithm to rotate it right by k element without using any other array. In other words rotate an array in place.
you can have temp variable to swap two elements.
Ex:-
Initial Array: A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Rotating array A right by 3 elements should result in
A = {8, 9, 10, 1, 2, 3, 4, 5, 6, 7}
Hint: There is a trick, think before doing much of the programming 🙂
See Solution: Rotate an array by k elements
So the trick is to reverse the whole array first then reverse the array from 0 to k-1 and k to n-1.
For example
Array A after reversing whole array: {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Array A after reversing 0 to 2 elements: {8, 9, 10, 7, 6, 5, 4, 3, 2, 1}
Array A after reversing 3 to 9 elements: {8, 9, 10, 1, 2, 3, 4, 5, 6, 7}
Code:
For example
Array A after reversing whole array: {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Array A after reversing 0 to 2 elements: {8, 9, 10, 7, 6, 5, 4, 3, 2, 1}
Array A after reversing 3 to 9 elements: {8, 9, 10, 1, 2, 3, 4, 5, 6, 7}
Code:
void rotateRight(int[] a, int k){
int length = a.length();//in C/C++ it will be given as input
reverse(a, 0, length -1);//reverse whole array
reverse(a, 0, k-1);//assuming 0 < k < length
reverse(1, k, n-1);
}
void reverse(int[] a, int start, int end){
while(start < end){
swap(a, start, end);
start++;
end--;
}
}
void swap(int[] a, int pos1, int pos2){
int temp = a[pos1];
a[pos1]= a[pos2];
a[pos2] = temp;
}
//Note: in interviews you might be asked to handle negative scenarios
// like array out of bound etc.
Facebook Comments
