How to rearrange a subarray of integers (for a random m) without auxiliary array like this?
example input [1,2,3,4,5,6,7,8,9,10]
m=3;
expected output :
[4,5,6,7,8,9,10,1,2,3]
example input :
[1,2,3,4,5]
m=4
example output
[5,1,2,3,4]
example input :
[1,2,3,4,5,6]
m=2
example output
[3,4,5,6,1,2]
I have tried creating a temp array and it worked but can it be done more memory efficient.
Yes, you can solve this in O(n) time and O(1) space. This involves reversing subarrays.
Let's take below one as an example:
[1,2,3,4,5,6,7,8,9,10]
m = 3
Have 2 pointers and swap the first and last element, second with second last and so on. So, with the above example, our array would look like:
[10, 9, 8, 4, 5, 6, 7, 3, 2, 1]
---------- ---------
A C
-------------
B
Important: If value of m is greater than half of the size of the array, you would stop the swapping there itself.
In the above scenario, we have successfully divided the array into 3 parts which I have named as A,B and C.
Now, reverse part C. So this part is now figured out.
[10, 9, 8, 4, 5, 6, 7, 1, 2, 3]
----------
A
-------------
B
Reverse part B which would look like below
[10, 9, 8, 7, 6, 5, 4, 1, 2, 3]
----------
A
-------------
B
Now, reverse the entire part (B + A) which is your final output.
[4, 5, 6, 7, 8, 9, 10, 1, 2, 3]
Note: Sometimes, it's possible that part B won't exist. So you would just reverse the entire A array in this case(or you can add additional if conditions)
Snippet:
private static void rotateArray(int[] arr,int m){
int left = 0,right = arr.length - 1;
int limit = Math.min(m,arr.length/2);
while(left < limit){
swap(arr,left++,right--);
}
reverse(arr,arr.length - m,arr.length-1);
reverse(arr,m,arr.length-m-1);
reverse(arr,0,arr.length-m-1);
}
private static void reverse(int[] arr,int left,int right){
while(left < right){
swap(arr,left++,right--);
}
}
private static void swap(int[] arr,int x,int y){
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}