Solution: This is an easy problem but a graceful solution is not that straightforward. When I mean "graceful", I mean a solution of O(n) time complexity and O(1) space complexity. The trick is try to reverse the array twice. The detail is as follow:
- First, reverse the whole array. If a[] = {1, 2, 3, 4, 5}, after reversing, we have a[] = {5,4,3,2,1}.
- Then reverse the subarray from idx 0 to idx k-1, with the previous example we have a[] = {4,5,3,2,1}. Then reverse the subarray from idx k to idx n-1, after this, we get a[] = {4, 5, 1, 2, 3}.
Another way to think of this is to do N modulo mappings, like so.
ReplyDeletepublic static void shift(int[] arr,int k) {
int placeHolder;
int oldIdx = 0;
int newIdx;
placeHolder = arr[oldIdx];
for(int i=0;i<arr.length;i++) {
newIdx = (oldIdx+k)%arr.length;
int temp = arr[newIdx];
arr[newIdx] = placeHolder;
placeHolder = temp;
oldIdx = newIdx;
}
}