Last Updated: 27 Mar, 2021
Rearrange array elements.
Easy
Asked in companies
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.
Approaches
- 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’.
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’.