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;
}
The question is similar to rotating the array in left direction... Before reading the solution try to apply this... I had rotated the array without using any extra space.. Code is as follows..
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,rot,lpos=0;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
cin>>rot; // number of times to rotate
int num=0,tmp,ntmp=arr[0],npos,pos=0;
while(1)
{
npos=pos-rot; // new position of element at position pos
if(npos<0)
{
npos=n-rot+pos;
}
tmp=arr[npos]; // saved the element at npos
arr[npos]=ntmp;
ntmp=tmp;
num++;
if(num==n) // if first position again occours then exit
break;
if(npos==lpos)
{
lpos++;
pos=lpos;
ntmp=arr[pos];
}
else
pos=npos;
}
for(int i=0;i<n;i++)
cout<<arr[i];
return 0;
}
It is as simple as shifting the element at the 0th index to the last index after shifting the remaining elements one position to the left, m times.
Program:
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int input[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int m = 3;
int temp, i, j;
for (i = 1; i <= m; i++) { // m times
temp = input[0];
for (j = 1; j < input.length; j++) {
input[j - 1] = input[j];
}
input[input.length - 1] = temp;
}
System.out.println(Arrays.toString(input));
}
}
Output:
[4, 5, 6, 7, 8, 9, 10, 1, 2, 3]
You can use Arrays.stream(int[],int,int) method two times to get two streams with the specified ranges of the array: near and far, then swap them and concat back into one stream:
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = 3;
int[] rotated = IntStream
.concat(Arrays.stream(arr, n, arr.length),
Arrays.stream(arr, 0, n))
.toArray();
System.out.println(Arrays.toString(rotated));
// [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]
See also: Rotate an elements in an array between a specified range