Unequal Adjacent Elements

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in companies
WalmartHashedInTrilogy Innovations

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
1 3 3 4  
4 
1 1 2 2
Sample Output 1 :
True
True
Explanation of sample input 1 :
Test case 1:

One of the possible rearrangements is [3,1,4,3].

Therefore the answer is ‘True’. But you have to return a rearranged array.

Test case 2:

One of the possible rearrangements is [1,2,1,2].

Therefore the answer is ‘True’.
Sample Input 2 :
2
4
1 2 3 4
7
1 1 2 2 3 3 4
Sample Output 2 :
True
True
Hint

Naively iterate over all permutations of the array. 

Approaches (3)
Brute Force.

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.
Time Complexity

O(‘N!'), where ‘N’ denotes the size of the array/list. 

 

For an array/list of size ‘N’ there are ‘N!’ permutations.

Space Complexity

O(1).

 

As we are using constant extra space.

Code Solution
(100% EXP penalty)
Unequal Adjacent Elements
Full screen
Console