Rearrange array elements.
Given an array ‘A’ having ‘N’ integers and an integer ‘m’. You need to rearrange the array elements such that after re-arrangement difference of array elements with ‘m’ should be in a sorted fashion.

If the difference between any two array elements and ‘m’ is the same, then the element which comes first in the given array will be placed first in the re-arranged array.

For Example

If we have A = [3, 5, 7, 9, 2, 6] and m = 5. Difference of array elements with m : [2, 0, 2, 4, 3, 1]. Array after rearrangement : [5, 6, 3, 7, 2, 9].

Input Format

The first line contains a single integer ‘T’ denoting the number of test cases. The first line of each test contains two integers, ‘N’ - number of elements in the array and ‘m’ The second line of each test case contains ‘N’ space-separated integers that make up ‘A’.

Output Format

For each test case, you need to print space-separated integers denoting the elements of the re-arranged array. Print the output of each test case in a separated line.

Note

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints

1

Question

Rearrange array elements.

Given an array ‘A’ having ‘N’ integers and an integer ‘m’. You need to rearrange the array elements such that after re-arrangement difference of array elements with ‘m’ should be in a sorted fashion.

If the difference between any two array elements and ‘m’ is the same, then the element which comes first in the given array will be placed first in the re-arranged array.

For Example

If we have A =  [3, 5, 7, 9, 2, 6]  and m = 5.
Difference of array elements with m : [2, 0, 2, 4, 3, 1].
Array after rearrangement : [5, 6, 3, 7, 2, 9].

Input Format

The first line contains a single integer ‘T’ denoting the number of test cases.
The first line of each test contains two integers, ‘N’ - number of elements in the array and ‘m’
The second line of each test case contains ‘N’ space-separated integers that make up ‘A’.

Output Format

For each test case, you need to print space-separated integers denoting the elements of the re-arranged array.

Print the output of each test case in a separated line.

Note

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints

1 <= T <= 10
1 <= N <= 10^5
1 <= m <= 10^5

Where ‘T’ is the number of test cases, ‘N’ is the length of array ‘A’, and ‘m’ is the value given as described in the problem statement.

Accepted Answer

A direct approach would be to use an additional empty array of size n, where n is the size of the input array. Manage two pointers, one at the starting index of the input array and another one at the endpoint. Copy the last element of the array first, in the additional array, then the first element of the array, and increment both the pointers one index further. Follow the same pattern unless the start pointer becomes less than or equal to the end pointer. This approach has a time complexity of O(n) and used O(n) auxiliary space.
To solve the question in O(1) auxiliary space, multiple modular tricks can be used to rearrange the array. Initialize the indices of the first max and first min elements as 0 and n-1 where n is the size of the array respectively. Then, iterate over the input array and store the maximum elements in a decreasing order at even places, Similarly, store the minimum elements of the input array in increasing order at odd places. The array thus obtained will be the resultant array.

Algorithm :
max_index : Index of remaining maximum element
(Moves from right to left)
min_index : Index of remaining minimum element
(Moves from left to right)

Initialize: max_index = 'n-1'
min_index = 0
max_element = arr[max_index] + 1 //can be any element which is more than the maximum value in array
For i = 0 to n-1
If 'i' is even
arr[i] += arr[max_index] % max_element * max_element
max_index--
ELSE // if 'i' is odd
arr[i] += arr[min_index] % max_element * max_element
min_index++

Accepted Answer

Brute Force Approach

We will solve this problem by finding the array elements that will give the minimum difference between the array element and ‘ m ‘.
We will maintain an array ‘visited’ where visited[ i ] = 1 denotes that A[ i ] is visited already.
We will iterate through the array ‘A’ and find the array element that is not visited yet or gives minimum difference with ‘ m ‘. Once we get this array element, we will add this to another array ‘result’, mark this element as visited, and iterate through the array again to find the rest of the elements.

Algorithm

Initialize an array ‘visited’ of size ‘N’ and a 1-D array ‘res’ that will store the re-arranged array.
Take a variable ‘minVal’ that will store the minimum value obtained in an iteration and a variable ‘ idx ’ that will store the corresponding element’s index.
Run a loop i : 0 to N - 1 to place all the ‘N’ elements in the rearranged array.
- Store maximum value of int data type in ‘ minVal ’
- Run a loop j : 0 to N-1
  - If A[ j ] is not visited and difference of A[ j ] with ‘ m ‘ is less than ‘minValue’, update minValue as abs( A[ j ] - m ) and idx = j.
- Add A[ idx ] to the ‘ res ’ array as A [ idx ] gives the minimum difference value among the not visited array elements.
Return ‘res’.

Space Complexity: O(n)Explanation:

O( N ), where ‘ N ’ is the number of elements in the array.

We have used an extra array ‘res’ of size ‘N’, making the space complexity O( N ).

Time Complexity: O(n^2)Explanation:

O( N^2 ), where ‘ N ’ is the number of elements in the array.

For every element in the ‘res’ array, we are iterating through the given array. Therefore time complexity is O( N^2).

Python (3.5)

"""
  Time Complexity : O( N^2 )
  Space Complexity : O( N )

  where 'N' is the number of elements in array.

"""


INT_MAX = 2147483647


def rearrangeArray(A, m):

    # Size of the array.
    n = len(A)

    visited = [0]*n

    # Array to store re-arranged array.
    res = []

    minVal = 0
    idx = 0

    # Iterate for all elements.
    for i in range(n):

        minVal = INT_MAX

        # Finding minimum difference among not visited elements.
        for j in range(n):

            if (visited[j] != 1 and abs(A[j] - m) < minVal):

                minVal = abs(A[j] - m)
                idx = j

        # Pushing element with minimum difference.
        res.append(A[idx])

        # Marking A[ idx ] as visited.
        visited[idx] = 1

    return res

Java (SE 1.8)

/*

  Time Complexity : O( N )

  Space Complexity : O( N )



  where 'N' is the number of elements in array.



*/



import java.util.ArrayList;

import java.util.HashMap;

import java.util.TreeMap;



import static java.lang.Math.abs;



public class Solution{



    public static int[] rearrangeArray(int[]A, int m) {



        int n = A.length;



        // visited array for marking elements as left to visit or done visiting

        int []visited=new int[n];



        // resultant array

        int[]res=new int[n];

        int j=0;



        while(true) {



            int mini=Integer.MAX_VALUE;



            for(int i=0;i                if(visited[i]==1)continue;



                // get the minimum difference

                if(abs(A[i]-m)                    mini=abs(A[i]-m);

                }

            }



            for(int i=0;i                if(visited[i]==0 && abs(A[i]-m)==mini){

                    visited[i]=1;

                    res[j++]=A[i];

                }

            }



            // no element is left to visit

            if(mini==Integer.MAX_VALUE)break;

        }



        return res;

    }



}

C++ (g++ 5.4)

/*

  Time Complexity : O( N^2 )

  Space Complexity : O( N )

  

  where 'N' is the number of elements in array.

  

*/



#include 

#define INT_MAX 2147483647



vector rearrangeArray(vector &A, int m)

{

    //Size of the array.

    int n = A.size();



    int visited[n] = {0};



    //Array to store re-arranged array.

    vector res;



    int minVal, idx;



    //Iterate for all elements.

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

    {

        minVal = INT_MAX;



        //Finding minimum difference among not visited elements.

        for (int j = 0; j < n; j++)

        {

            if (visited[j] != 1 && abs(A[j] - m) < minVal)

            {

                minVal = abs(A[j] - m);

                idx = j;

            }

        }



        //Pushing element with minimum difference.

        res.push_back(A[idx]);



        //Marking A[ idx ] as visited.

        visited[idx] = 1;

    }



    return res;

}

Accepted Answer

Multimap Implementation

We can solve this problem by using a multimap.

Multimap is similar to a map with an addition that in multimap, multiple elements can have the same key. Multimap also stores all the keys in sorted order, and if two elements have the same key, then the element inserted first is stored before the second in multimap.

We will maintain a multimap where the key of the map stores the difference of array elements with ‘ m ‘ and values at any key denote the array elements corresponding to that difference value.
We will iterate through the array elements and find the difference between array element and ‘ m ‘ and map this difference value with array element in multimap.
In the end, the values of the multimap will store the re-arranged array.

For example if A = [ 2, 5, 9, 3 ] and m =7

Multimap will store values as

2 -> 5

2 -> 9

4 -> 3

5 -> 2

The re-arranged array will be [ 5, 9, 3, 2 ].

Algorithm

Initialize a multimap ‘Map’ that maps values from integer to integer.
Run a loop i : 0 to N-1.
- Insert abs( A[ i ] - m ) , A[ i ] in ‘Map’
Iterate through the ‘Map’ and place the values in array ‘A’ as the map’s order.
Return array ‘A’.

Space Complexity: O(n)Explanation:

O( N ), where ‘ N ’ is the number of elements in the array.

We have used a multimap, and the number of elements in the map will always be equal to the array’s length. So the space complexity is O( N ).

Time Complexity: O(n)Explanation:

O( N ), where ‘ N ’ is the number of elements in the array.

We are creating a multimap that will take O( log( N ) ) time and then iterating through the multimap that will take O( N ) time. So the overall time complexity will be O( N ).

Java (SE 1.8)

/*

  Time Complexity : O( N )

  Space Complexity : O( N )



  where 'N' is the number of elements in array.



*/



import java.util.ArrayList;

import java.util.HashMap;

import java.util.TreeMap;



import static java.lang.Math.abs;



public class Solution{



    public static int[] rearrangeArray(int[]A, int m) {



        //Initializing map with key as integer and value as an array

        TreeMap> map=new TreeMap<>();



        int n = A.length;



        //Inserting values in map.

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

            // previous integers in array

            ArrayListprevArr=new ArrayList<>();

            if(map.containsKey(abs(A[i]-m))){

                prevArr=map.get(abs(A[i]-m));

            }



            prevArr.add(A[i]);

            map.put(abs(A[i]-m),prevArr);

        }



        //Store re-arranged array.

        int []res=new int[n];

        int j=0;



        //Storing elements in 'res'.

        for(ArrayListarr:map.values()) {

            for(int i=0;i                res[j++]=arr.get(i);

            }

        }



        return res;

    }



}

Python (3.5)

"""
  Time Complexity : O( N )
  Space Complexity : O( N )

  where 'N' is the number of elements in array.

"""

from collections import defaultdict
from collections import OrderedDict


def rearrangeArray(A, m):

    # Initializing multimap.
    Map = defaultdict(list)

    n = len(A)

    # Inserting values in map.
    for i in range(n):
        Map[abs(A[i]-m)].append(A[i])
    res = []
    Map = OrderedDict(sorted(Map.items()))
    for i in Map:
        for j in Map[i]:
            res.append(j)

    return res

C++ (g++ 5.4)

/*

  Time Complexity : O( N )

  Space Complexity : O( N )

  

  where 'N' is the number of elements in array.

  

*/



#include 

#include 



vector rearrangeArray(vector &A, int m)

{

    //Initializing multimap.

    multimap Map;



    int n = A.size();



    //Inserting values in map.

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

    {

        Map.insert({abs(A[i] - m), A[i]});

    }



    //Store re-arranged array.

    vector res;



    //Iterator to multimap.

    multimap::iterator itr;



    //Storing elements in 'res'.

    for (itr = Map.begin(); itr != Map.end(); itr++)

    {

        res.push_back(itr->second);

    }



    return res;

}

Top Info Edge Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Info Edge Software Developer