Rearrange an array with O(1) extra space

 Rearrange an array with O(1) extra space

MediumAccuracy: 56.34%Submissions: 76K+Points: 4

Given an array arr[] of size N where every element is in the range from 0 to n-1. Rearrange the given array so that arr[i] becomes arr[arr[i]].

 

Example 1:

Input:
N = 2
arr[] = {1,0}
Output: 0 1
Explanation: 
arr[arr[0]] = arr[1] = 0.
arr[arr[1]] = arr[0] = 1.

 

Example 2:

Input:
N = 5
arr[] = {4,0,2,1,3}
Output: 3 4 2 0 1
Explanation: 
arr[arr[0]] = arr[4] = 3.
arr[arr[1]] = arr[0] = 4.
and so on.

 

Your Task:
You don't need to read input or print anything. The task is to complete the function arrange() which takes arr and N as input parameters and rearranges the elements in the array in-place. 

 

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

 

Constraints:
1 <= N <= 107
0 <= Arr[i] < N

 

Solution :
In this question we are asked to move the elements of the array such that the position of elements would be equal to the value of element currently and the value to be updated would be the value of the current index(value). 

Explanation: 

arr[] = {4,0,2,1,3}

arr[arr[0]] = arr[4] = 3.

So what we can do is :
make a new array where we store the values according to this logic and finally copy all the elements from the new array to this array.

void arrange(long long arr[],int n){

    long long new_arr[n];

    int temp=0;

    for(int i=0;i<n;i++){

        new_arr[i]=0;

    }

    for(int i=0; i<n;i++){

        temp=arr[i];        

        new_arr[i]=arr[temp];  

    }

    for(int i=0;i<n;i++){

        arr[i]=new_arr[i];

       }

}

Another approach :

We could also solve this by using some mathematics :

our good old formula :

                            dividend = divisor * quotient + remainder

we can use this formula to store two values at one index, and get whichever value we need by division (/) or remainder (%).

Reverse array in groups

Given an array arr[] of positive integers of size N. Reverse every sub-array group of size K.

Note: If at any instance, there are no more subarrays of size greater than or equal to K, then reverse the last subarray (irrespective of its size). You shouldn't return any array, modify the given array in-place.

Example 1:

Input:
N = 5, K = 3
arr[] = {1,2,3,4,5}
Output: 3 2 1 5 4
Explanation: First group consists of elements
1, 2, 3. Second group consists of 4,5.

 

Example 2:

Input:
N = 4, K = 3
arr[] = {5,6,8,9}
Output: 8 6 5 9

 

Your Task:
You don't need to read input or print anything. The task is to complete the function reverseInGroups() which takes the array, N and K as input parameters and modifies the array in-place. 

 

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Solution :
As we can see we need to reverse the array at k partitions, so to do that in O(n) time we must think of a way to traverse the array only once.
Well one solution to traverse the array twice while using one iteration would be to somehow get hold of values from two variables and not just iterator i.

Now the question is how?
so we can use the two pointer approach, dont be afraid by the name, we are not going to create any pointers here.
It's said two pointer because we are going to access the array with two variables by storing two values at a time.

Now lets jump back to the coding part.

so first of all we need to have a function which would be returning nothing
(as we are going to update all the array inside the function and as we pass address of arrays
in cpp so due to access to address of the array the original array would be modified
here we are using address to vector.) :

Step 1 :
void alter(vector<long long> &arr, int n, int k){

}

Okay so function is created now what?
now we need to make the logic, so no worries we will build it step by step.

Before we start coding let me explain you the logic,

What we would be doing is that we would be iterating in the array with incrementing not i++ rather i=i+k (why? because in between i and i+k we need to reverse the array so we need to see to that explicitly)

so now in the logic we know we need to run another loop for k times to reverse the values,
so we would be making a left pointer and right pointer. 
And we would use these pointer to swap the values to reverse that portion of the array.
Let me help you visualize the idea  :

so lets jump to the code:

Void alter(vector<long long> &arr[], int n, int k){

    for(int i {} ; i<n;i=i+k){

        int left=i;
        int right=min(i+k-1,n-1);           //why min?

        while(left<right){

            swap(arr[left],arr[right]);

            left++;

            right--;

        }

    }

}

*Note : we are taking minimum of i+k-1 and n-1 because we are iterating i+3 so if the length of the array is not the multiple of 3 then there would be some remaining elements for which i+k-1 would go beyond the length of the array and cause error so there by taking the min it would consider n-1 as the last element for right.