How to swap the sub-arrays?

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.

Upvotes: 0

Answers (4)

Arvind Kumar Avinash

Reputation: 79095

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]

Upvotes: 0

user14940971

Reputation:

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]

Upvotes: 0

Vishal_898

Reputation: 300

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;
}

Upvotes: 2

nice_dev

Reputation: 17805

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;
    }

Demo: https://onlinegdb.com/HklMoZKG4U

Upvotes: 3

How to swap the sub-arrays?

Answers (4)

Related Questions