 15

# Rearrange The Array

Difficulty: MEDIUM Contributed By
Amandeep Kaur
Avg. time to solve
15 min
Success Rate
90%

Problem Statement

#### You are given an array/list 'NUM' of integers. You are supposed to rearrange the elements of the given 'NUM' so that after rearranging the given array/list there are no two adjacent elements present in the rearranged 'NUM' which will be the same.

##### For example:
``````Input: NUM[] = {1,1,1,2,2,2}
Output: {1,2,1,2,1,2}
Note: {2,1,2,1,2,1} is also valid because there are no two adjacent which are the same.
``````
##### Input format :
``````The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains an Integer 'N' denoting the size of the array/list.

The second line of each test case contains 'N' space-separated Integers denoting the elements of the array/list.
``````
##### Output format :
``````For each test case/query, if it is possible to rearrange then print “YES” else print “NO” in separate lines. And if the output given by the user is wrong then print “Invalid Output”.

If it is possible to rearrange then return any right arrangement of the given array/list otherwise put a single integer INT_MIN in the array/list and return that.
``````
##### 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 ^ 4
-10 ^ 9 <= NUM[i] <= 10 ^ 9

Where 'N' is the size of the given array/list and, NUM[i] denotes the i-th element in the array/list.

Time Limit: 1 sec.
``````
##### Sample Input 1 :
``````2
5
10 10 10 32 32
6
89 47 89 47 42 21
``````
##### Sample Output 1 :
``````YES
YES
``````
##### Explanation to Sample Input 1 :
``````For the first test case, We can put 32 in between 10 and arrangement looks like. {10,32,10,32,10}.

For the second test case, We have to arrange only 47 and 89 because the rest of the element is unique in itself. So one arrangement looks like { 89, 47, 89, 47, 42, 21}.
``````
##### Sample Input 2 :
``````3
5
10 7 21 5 1
6
21 21 21 12 12 21
6
10 10 10 20 20 20
``````
##### Sample Output 2 :
``````YES
NO
YES
``````
##### Explanation to Sample Input 2 :
``````For the first test case, all the elements have the same frequency, so you can return any arrangement of those elements, i.e. {1, 7, 21, 5, 10}.

For the second test case, we can not rearrange the given array/list because after rearranging {21,12,21,12}, we will be stuck with two 21. There is no way to arrange them.

For the third test case, we can put all the 10 in between 20. So there will be no such adjacent existence which will be the same.
``````   Console