Rearrange The Array

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
36 upvotes
Asked in companies
AdobeMicrosoftThought Works

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Hint

Can you think some greedy approach will work?

Approaches (1)
Greedy with Priority Queue

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 pop one by one element from the priority queue and add it to the result only when current elements are not the same as the most recent element which one saved in the result. Then we decrease the frequency of the elements and push into the priority queue if the element has a frequency greater than '0'. Steps are as follow:

 

  • Store the frequency of each element. We will be using ‘HASHMAP’ to store the frequency.
  • 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 { 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.
Time Complexity

O(N* log (N)), where ‘N’ is the number of elements in the given array/list.

 

We are storing the frequency of each element into “HashMap” which will take O(N) time. And for each unique element, we are adding it to the priority queue so there can be ‘N’ unique elements. So adding ‘N’ unique element into priority queue will take O(N * log(N)) time, also while we are doing pop, top and push operation for rearrangement of ‘N’ elements. So pop and push operation take O(log N) time and top operation take O(1). So overall time complexity will be O(N* log(N)).

Space Complexity

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

 

We are storing the ‘N’ elements into the result and also into the priority queue. So in the worst case, when all the elements in the given array/list will be distinct, then the priority queue also takes space O(N). So, overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Rearrange The Array
Full screen
Console