In a warehouse, there is a row of barcodes, where the ith barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.

&nbsp;
Example 1:
Input: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]
Example 2:
Input: barcodes = [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,1,2,1,2]

&nbsp;
Constraints:


	1 &lt;= barcodes.length &lt;= 10000
	1 &lt;= barcodes[i] &lt;= 10000


import heapq

class Solution:

    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        barcodes_counter = Counter(barcodes)
        if len(barcodes_counter) == len(barcodes):
            return barcodes

        barcodes_heapq = [ (-c, b) for b, c in barcodes_counter.items() ]
        heapq.heapify(barcodes_heapq)

        idx, prev_count, prev_barcode = 0, 0, 0
        while barcodes_heapq:
            (curr_count, curr_barcode) = heapq.heappop(barcodes_heapq)

            barcodes[idx] = curr_barcode
            idx += 1
            curr_count += 1

            if prev_count:
                heapq.heappush(barcodes_heapq, (prev_count, prev_barcode))

            prev_count, prev_barcode = curr_count, curr_barcode

        return barcodes
class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        
        if(barcodes.length <= 2){
            return barcodes ; //Problem says solution always exist.
        }
        
        Map<Integer, Integer> count = new HashMap<>();
        Integer maxKey = null; // Character having max frequency
        
        for(int i: barcodes){
            count.put(i, count.getOrDefault(i, 0) + 1);
            if(maxKey == null || count.get(i) > count.get(maxKey)){
                maxKey = i;
            }
        }
        
        int pos = 0;
     
        //Fill maxChar
        int curr =  count.get(maxKey);
        while(curr-- > 0){
            barcodes[pos] = maxKey;
            pos += 2;
            if(pos >= barcodes.length){
                pos = 1;
            }
        }
        
        count.remove(maxKey); // Since that character is done, we don't need to fill it again
        
        //Fill the remaining Characters.
        for(int key: count.keySet()){
            curr = count.get(key);
            
            while(curr-- > 0){
                barcodes[pos] = key;
                pos += 2;
                if(pos >= barcodes.length){
                    pos = 1;
                }
            }
        }
        
        return barcodes;
    }
}
class Solution {
public:
    struct comp{
        bool operator()(pair<int,int>&a, pair<int,int>&b){
            return a.first < b.first;
        }
    };
    
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int,int> hmap;
        int n = barcodes.size();
        if(n==1)return barcodes;
        
        for(auto &bar : barcodes){
            hmap[bar]++;
        }
        
        vector<int> ans;
        priority_queue<pair<int,int>, vector<pair<int,int>>, comp> pq;
        
        for(auto &it : hmap){
            pq.push({it.second, it.first});
        }
        
        while(pq.size()>1){
            
            auto firstBar = pq.top();
            pq.pop();
            
            auto secondBar = pq.top();
            pq.pop();
            
            ans.push_back(firstBar.second);
            ans.push_back(secondBar.second);
            
            --firstBar.first;
            --secondBar.first;
            
            if(firstBar.first > 0){
                pq.push(firstBar);
            }
            
            if(secondBar.first > 0){
                pq.push(secondBar);
            }
        }
        
        if(pq.size()){
            ans.push_back(pq.top().second);
            pq.pop();
        }
        
        return ans;
    }
};
var rearrangeBarcodes = function(barcodes) {
    var result = [];
    var map = new Map();
    barcodes.forEach(n => map.set(n, map.get(n) + 1 || 1));
    let list = [...map.entries()].sort((a,b) => {return b[1]-a[1]})
    let i = 0; //list[i][0]=>number list[i][1]=>count of this number
    while(result.length!==barcodes.length){
        if(list[i][1]>0) result.push(list[i][0]), list[i][1]--;
        i++;
        if(list[i]===undefined) i = 0;
        if(list[0][1]-list[i][1]>=1&&result[result.length-1]!==list[0][0]) i = 0;
    } //list has sorted, so list[0] appeared most frequent
    return result;
};
Distant Barcodes