Last Updated: 10 Dec, 2020
Rearrange The Array
Easy
Asked in companies
You are given an array/list NUM of integers. You are supposed to rearrange the elements of NUM such that no two adjacent elements will be the same or find out if it not possible.
For example:
Input: arr[] = {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 elements 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.
Note :
You do not need to print anything; it has already been taken care of.
Constraints :
1 <= T <= 100
1 <= N <= 5000
-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.
Approaches
The key idea is to put the highest frequency element first (a greedy approach). We will be using the priority queue to pick the elements with the highest frequency.
So first, we will store the frequency of each element. And then we will store all the numbers with their frequencies into the priority queue in the highest frequency priority manner.
After that, we will pop elements one by one from the priority queue and add them to result only when the current element is not the same as the most recent element saved in the result. Also, we will decrease the frequency of each element and push it back into the priority queue if the element has a frequency greater than '0'.
Here is the complete algorithm:
- Store the frequency of each element in a HashMap.
- Build the priority queue that stores the element and their frequencies, where comparison of priority queue elements will be based on the highest frequencies of elements.
- Take a temporary pair (elements, frequencies) that will be used as the most recent element which has been added into our result.
- Create a variable say “prev” that will be used as the previously visited element (the previous element in the resultant array. Initialize it to {num = -1, freq = -1}.
- Iterate until priority queue does not become empty:
- Pop an element and add it to the result.
- Decrease the frequency of the current element.
- Push the previous element and their frequency back into the priority queue if it’s frequency is greater than 0.
- Make the current element as the previous element for the next iteration.
- If the size of the result is the same as the given array/list, then return the result.
- Else return array/list containing only a single element as negative infinity, i.e. -2147483648.