Last Updated: 9 Apr, 2021
Unequal Adjacent Elements
Moderate
Asked in companies
You have been given an array/list ‘ARR’ of integers consisting of ‘N' integers. You need to rearrange ‘ARR’ so that no two adjacent elements are equal. You may return any valid rearrangement and it is guaranteed the answer exists.
Example :
Let’s say you have an array/list ‘ARR = [1,1,2,2]’.
Then a valid rearrangement can be [1,2,1,2] or [2,1,2,1] such that no two adjacent elements are equal. [2,1,1,2] is an invalid arrangement because two adjacent elements are equal.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains a single integer ‘N’ representing the size of the array/list ‘ARR’.
The second line and the last line of input contain ‘N’ single space-separated integers representing the array/list elements.
Output Format :
For each test case, print the rearranged list/array. If it is a valid rearranged list then the code will output ‘True’ otherwise ‘False’.
Note :
1. You do not need to print anything; it has already been taken care of. Just implement the function.
2. You will need to return the rearranged array/list. If the rearranged list is a valid rearrangement then we will display ‘True’ as an output otherwise ‘False’ as output.
Constraints :
1 <= T <= 10
1 <= N <= 1000
1 <= ‘ARR[i]’ <= 10^3
Time Limit: 1sec
Approaches
We can apply the algorithm as follows:-
- Sort the array so that we can use the ‘next_permutation’ function. It helps us iterate over all possible arrangements of the array.
- Iterate the array/list if it is a valid arrangement:-
- If it is a valid arrangement return the list.
We can put the highest frequency element first. It is a greedy approach. We use a set and put all elements and order by their frequencies. We take the highest frequency element and add it to the list. After we add, we decrease the frequency of the character and we temporarily move this element out of the set so that it is not picked next time. For example:- [1,1,2,2,2,3,3] If we do not remove 2 from the set after the first iteration it will again be the top element and then two consecutive elements will be the same in ‘ANS’.
Following is the algorithm for this approach:
- Declare an empty list/array ‘ANS’.
- Sort the array/list ‘ARR’.
- Declare a set ‘S’ that stores elements and their frequencies.
- Iterate over the array/list ‘ARR’:-
- Iterate till we have the same element. Increase the count of that element by 1. Insert the element and its frequency in the set ‘S’.
- Make a temporary variable to store the previous element and its frequency.
- While ‘S’ is not empty:-
- Access the last element and add it to the result. Remove the element from the set.
- Decrease the frequency of the popped element by 1.
- If the previous element frequency was non-zero insert it in the set.
- Make the current element as the previous element for the next iteration.
- Finally, we return the array/list ‘ANS’.
We can put the highest frequency element first. It is a greedy approach. We use a priority queue or binary max-heap and put all elements and order by their frequencies. We take the highest frequency element and add it to the list. After we add, we decrease the frequency of the character and we temporarily move this character out of the priority queue so that it is not picked next time. For example:- [1,1,2,2,2,3,3] If we do not remove 2 from the priority queue after the first iteration it will again be the top element and then two consecutive elements will be the same in ‘ANS’.
Following is the algorithm for this approach:
- Declare an empty list/array ‘ANS’.
- Sort the array/list ‘ARR’.
- Declare a priority queue ‘P_QUEUE’ that stores elements and their frequencies.
- Iterate over the array/list ‘ARR’:-
- Iterate till we have the same element. Increase the count of that element by 1. Insert the element and its frequency in the priority queue ‘P_QUEUE’.
- Make a temporary variable to store the previous element and its frequency.
- While ‘P_QUEUE’ is not empty:-
- Pop an element and add it to the result.
- Decrease the frequency of the popped element by 1.
- If the previous element frequency was non-zero insert it in the priority queue.
- Make the current element as the previous element for the next iteration.
- Finally, we return the array/list ‘ANS’.