2

How can we do it most efficiently? Given a list with repeated items, task is to rearrange items in a list so that no two adjacent items are same.

Input: [1,1,1,2,3] 
Output: [1,2,1,3,1] 

Input: [1,1,1,2,2]
Output: [1,2,1,2,1] 

Input: [1,1]
Output: Not Possible

Input: [1,1,1,1,2,3] 
Output: Not Possible

Edit: General Algorithm is fine too! It doesn't need to be Python.

aerin
  • 20,607
  • 28
  • 102
  • 140
  • 1
    Generaly just read the list from start to end looking at two items together at a time and if two items together are the same then swap the second item with its successor. Then the last case is special because you if it requires a swap then swap the last with the first, and continue checking from the start. – Guy Coder Apr 11 '17 at 17:16

2 Answers2

4

I am not good at python, so I am writing the general algorithm here -

  1. Build a max heap, maxHeap that stores numbers and their frequencies <array element, frequency>. maxHeap will be sorted based on the frequency of element.

  2. Create a temporary Key that will used as the previous visited element ( previous element in resultant array. Initialize it as <item = -inf , freq = -1>.

  3. While maxHeap is not empty

    • Pop an element and add it to result.
    • Decrease frequency of the popped element by 1
    • Push the previous element back into the max heap if it's frequency > 0
    • Make the current element as previous element for the next iteration.

  4. If length of resultant array and original, there is no solution for this array. Else return the resultant array.

Edit

Those who're wondering why the greedy solution by putting the current most frequent element in even/odd positions by skipping one position each time won't work, you can try with the test-case [1 1 2 2 3 3].

Community
  • 1
  • 1
Kaidul
  • 15,409
  • 15
  • 81
  • 150
1

Let n be the size of the list. If some element occurs at least (n + 2) / 2 (integer division), there's clearly no solution (according to the pigeonhole principle).

Otherwise, we can always construct the answer. We can do it like this: let's write down all even positions first and then all odd positions (I use 0-based indices). After that, let's sort the elements by their frequency (in decreasing order) and fill the positions in the order described above (note: the elements are sorted as pairs (frequency, element) so that the same elements are grouped together. There're sorted only once at the very beginning of the answer construction).

This algorithm can run in linear time if we use a hash table to count elements and sort them by frequency using count sort.

kraskevich
  • 18,368
  • 4
  • 33
  • 45