In a warehouse, there is a row of barcodes, where the i-th 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.
 
Example 1:
Input: [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]


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

 
Note:

1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000

Difficulty: interview

Starter code:

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        

Solutions:
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        if len(barcodes) < 2:
            return barcodes
        
        sorted_codes = sorted(barcodes)
        halfway = len(barcodes)//2
        ans =  [0] * (halfway * 2)
        ans[::2], ans[1::2] = sorted_codes[-halfway:], sorted_codes[:halfway]
            
        if len(barcodes) % 2 == 1:
            prev = None
            mid = sorted_codes[halfway]
            for i in range(len(ans) - 1):
                if ans[i] == mid:
                    i += 1
                elif ans[i] != prev:
                    ans.insert(i, mid)
                    break
                prev = ans[i]
        return ans


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        barcodes.sort()
        n = len(barcodes)
        result = list()
        
        if n%2 == 0:
            for x, y in zip(barcodes[:n//2], barcodes[n//2:]):
                result.extend([y,x])
        else:
            midVal = barcodes[n//2]
            isAdded = False
            prev = -1
            for x,y in zip(barcodes[:n//2], barcodes[n//2+1:]):
                if isAdded == False and prev != midVal and y != midVal:
                    result.append(midVal)
                    isAdded = True
                result.extend([y, x])
                prev = x
            if isAdded == False:
                result.append(midVal)
        return result

from collections import Counter
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        barcodes = Counter(barcodes)
        a = []
        for i,j in barcodes.most_common():
            a.extend([i]*j)
        l = len(a)
        res = [0]*l
        j=0
        for i in range(0,l,2):
            res[i]=a[j]
            j+=1
        for i in range(1,l,2):
            res[i]=a[j]
            j+=1
        return res
            


from heapq import heappush,heappop
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        hashmap = {}
        for i in range(len(barcodes)):
            key = barcodes[i]
            if key not in hashmap:
                hashmap[key] = 1
            else:
                hashmap[key] = hashmap[key]+1
        h = []
        for key,val in list(hashmap.items()):
            heappush(h,(-val,key))
        result = [ ]
        tlist = []
        while h:
            pending_lst = []
            for i in range(2):
                if h:
                    frequency, char = heappop(h)
                    positive_frequency = -frequency
                    if positive_frequency > 0:
                        pending_lst.append((positive_frequency-1, char))
                        if result and char == result[-1]:
                            continue
                        result.append(char)
            if not h and not pending_lst:
                break
            for frequency, char in pending_lst:
                heappush(h, (-frequency, char))
        return result
                    
        
        
            


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        # https://leetcode.com/problems/distant-barcodes/discuss/801339/Easy-to-Read-and-Understand-Python-Solution-with-Comments!
        # Get the counts of all of our barcode elements.
        cnts = collections.Counter(barcodes)
\t\t# Put the -'ve counts along with themselves into a min heap.
\t\t# For those new to this we use -'ve because this is a min heap, so largest cnt pop'd first.
        heap = [(-v, k) for k,v in cnts.items()]
        heapq.heapify(heap)
        res = []
        # While we have elements on our heap.
        while heap:
\t\t    # pop the top element.
            cnt1, num1 = heapq.heappop(heap)
\t\t\t# If the top element was the last we used, we need something different.
            if res and res[-1] == num1:
\t\t\t    # pop the next highest cnt element. 
                cnt, num = heapq.heappop(heap)
                res.append(num)
                cnt += 1
\t\t\t\t# If there's still elements left we put them back on the heap.
                if cnt != 0:
                    heapq.heappush(heap, (cnt, num))
\t\t\t\t# We can also add the first that we popped, and push it back on the heap as well.
                res.append(num1)
                cnt1 += 1
                if cnt1 != 0:
                    heapq.heappush(heap, (cnt1, num1))
\t\t\t# else we just add the highest cnt element and put the remaining back on.
            else:
                res.append(num1)
                cnt1 += 1
                if cnt1 != 0:
                    heapq.heappush(heap, (cnt1, num1))
            
        return res
    
# Run time O(NlogN), space O(N)

from collections import Counter
import heapq

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        count = Counter(barcodes)
        pq = []
        
        for tup in count.items():
            heapq.heappush(pq,(-tup[1],tup[0]))
            
        res = []
        
        prev_freq,prev_char = 0,None
        
        while pq:
            
            freq,num = heapq.heappop(pq)
            
            if -prev_freq > 0 and prev_char:
                heapq.heappush(pq,(prev_freq,prev_char))
            
            res.append(num)
            prev_freq = freq+1
            prev_char = num
            
        
        return res

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        mp = collections.defaultdict(int)
        for b in barcodes:
            mp[b]+=1
        heap = []
        for k,v in list(mp.items()):
            heapq.heappush(heap,(-v,k))
        idx = 0
        n = len(barcodes)
        ans = [0]*n
        while heap:
            f,v = heapq.heappop(heap)
            f=-f
            while f>0:
                ans[idx]=v
                idx+=2
                f-=1
                if idx>=n: 
                    idx=1
        return ans



class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        max_v = max(len(barcodes), max(barcodes))+1
        freq = [0]*max_v
        for v in barcodes:
            freq[v]+=1
        sortedList=[[] for _ in range(max_v)]
        for v, f in enumerate(freq):
            if f > 0:
                sortedList[-f].extend([v]*f)
        result = []
        for index in sortedList:
            for mi in index:
                    result.append(mi)
        barcodes = result
        res = [\"\"]*len(barcodes)
        i = 0
        j = 0
        while j < len(barcodes):
            res[i] = barcodes[j]
            i=i+2
            j=j+1
            if i > len(res)-1:
                i=1
        return res
        
        

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        count = {}
        for code in barcodes:
            if code in count:
                count[code] += 1
            else:
                count[code] = 1
        count = {k: v for k, v in sorted(count.items(), key=lambda item: item[1],reverse=True)}

        it = iter(count.keys())
        cur = next(it)
        i = 0
        while i < len(barcodes):
            while count[cur] == 0:
                cur = next(it)
            barcodes[i] = cur
            count[cur] -= 1
            i += 2
        i = 1
        while i < len(barcodes):
            while count[cur] == 0:
                cur = next(it)
            barcodes[i] = cur
            count[cur] -= 1
            i += 2
        return barcodes

class Solution:
    def rearrangeBarcodes(self, A: List[int]) -> List[int]:
        c=collections.Counter(A)
        A.sort(key=lambda x:(c[x],x))
        
        A[1::2],A[::2]=A[:len(A)//2],A[len(A)//2:]
        return A


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        dicta = collections.defaultdict(int)
        max_word = 0
        for i in barcodes:
            dicta[i]+=1
            if dicta[i]>dicta[max_word]:
                max_word = i
        
        n=len(barcodes)
        ans = [0 for i in range(n)]
        idx=0
        
        for i in range(dicta[max_word]):
            ans[idx] = max_word
            idx+=2    
        del dicta[max_word]
        #print(ans)
        #idx=1
        for let in dicta:
            for i in range(dicta[let]):
                if idx>=n:
                    idx=1
                ans[idx]=let
                idx+=2
        
        return ans


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        count = defaultdict(int)
        for i in barcodes:
            count[i] -= 1
        h = []
        for i in count:
            heappush(h, (count[i], i))
        # even
        out = [0 for _ in range(len(barcodes))]
        freq, code = heappop(h)
        for i in range(0, len(barcodes), 2):
            out[i] = code
            freq += 1
            if not freq and h:
                freq, code = heappop(h)
        
        if not freq and h:
            freq, code = heappop(h)
        
        # odd
        for i in range(1, len(barcodes), 2):
            out[i] = code
            freq += 1
            if not freq and h:
                freq, code = heappop(h)
                
        return out


from collections import Counter
from heapq import heapify, heappop
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        c = Counter(barcodes)
        h = []
        for k, count in list(c.items()):
            h.append((-count, k))
        heapify(h)
        
        res = [0] * len(barcodes)
        index = 0
        while h:
            count, num = heappop(h)
            count = -count
            while count:
                if index >= len(barcodes):
                    index = 1
                res[index] = num
                index += 2
                count -= 1
        return res


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter = collections.Counter(barcodes)
        data = [[] for i in range(len(barcodes)+1)]
        
        for i in counter:
            data[counter[i]].append(i)
            
        res = [None for k in range(len(barcodes))]
        temp = 0
        for j in range(len(data)-1, 0, -1):
            if len(data[j]) == 0:
                continue
            for char in data[j]:
                times = j
                while(times > 0):
                    res[temp] = char
                    temp += 2
                    times -= 1
                    if temp >= len(res):
                        temp = 1
        return res


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        dicta = [0]*10001
        max_word = 0
        for i in barcodes:
            dicta[i]+=1
            if dicta[i]>dicta[max_word]:
                max_word = i
        
        #n=len(barcodes)
        ans = [0 for i in range(len(barcodes))]
        idx=0
        
        for i in range(dicta[max_word]):
            ans[idx] = max_word
            idx+=2    
        dicta[max_word]=0
        
        for j in range(10001):
            if dicta[j]>0:
                for i in range(dicta[j]):
                    if idx>=len(barcodes):
                        idx=1
                    ans[idx]=j
                    idx+=2
        
        return ans


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        n = len(barcodes)
        
        counter = Counter(barcodes)
        
        sorted_barcodes = sorted(barcodes,key=lambda x: (counter[x],x))
        
        res = [0] * n
        
        res[1::2],res[::2] = sorted_barcodes[:n//2],sorted_barcodes[n//2:]
        
        return res

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        count = {}
        for code in barcodes:
            if code in count:
                count[code] += 1
            else:
                count[code] = 1
        count = {k: v for k, v in sorted(count.items(), key=lambda item: item[1],reverse=True)}
        def nextCode(last: int) -> int:
            for k in count.keys():
                if count[k] > 0:
                    count[k] -= 1
                    return k
        it = iter(count.keys())
        cur = next(it)
        i = 0
        while i < len(barcodes):
            while count[cur] == 0:
                cur = next(it)
            barcodes[i] = cur
            count[cur] -= 1
            i += 2
        i = 1
        while i < len(barcodes):
            while count[cur] == 0:
                cur = next(it)
            barcodes[i] = cur
            count[cur] -= 1
            i += 2
        return barcodes

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        n=len(barcodes)
        if n==1:
            return barcodes
        ans=[]
        barcodes.sort()
        if n%2==0:
            for x,y in zip(barcodes[:n//2],barcodes[n//2:]):
                ans.extend([y,x])
        else:
            mid=barcodes[n//2]
            added,x_last=0,-1 # added: flag indicating if the middle element is added to the result
            for x,y in zip(barcodes[:n//2],barcodes[n//2+1:]):
                if not added and x_last!=mid and y!=mid: 
                    ans.append(mid)
                    added=1
                ans.extend([y,x])
                x_last=x
            if not added:
                ans.append(mid)
        return ans


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        record=dict()
        for bar in barcodes:
            record[bar]=record.get(bar,0)+1
        record=sorted([(k,v) for k,v in record.items()], key=lambda x: x[1], reverse=True)
        max_count=record[0][1]
        read=[]
        for k,v in record:
            read+=[k]*v
        L=len(read)
        res=[[] for _ in range(max_count)]
        for idx in range(L):
            res[idx%max_count].append(read[idx])
        ress=[]
        for r in res:
            ress+=r
        return ress

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        len_ = len(barcodes)
        freq = collections.Counter()
        maxFreqCode = 0
        for code in barcodes:
            freq[code] += 1
            if freq[code] > freq[maxFreqCode]:
                maxFreqCode = code
        
        i = 0
        ans = [0] * len_
        
        for _ in range(freq[maxFreqCode]):
            ans[i] = maxFreqCode
            i += 2
        freq[maxFreqCode] = 0    
        
        for code in freq:    
            for _ in range(freq[code]):
                if i >= len_:
                    i = 1
                ans[i] = code
                i += 2
            freq[code] = 0    
            
        return ans

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        i, n = 0, len(barcodes)
        res = [0] * n
        for k, v in collections.Counter(barcodes).most_common():
            for _ in range(v):
                res[i] = k
                i += 2
                if i >= n: i = 1
        return res


class Solution:
    def rearrangeBarcodes(self, barcodes):
        cnt = dict()
        for v in barcodes:
            cnt[v] = cnt.get(v, 0) + 1
        N = len(barcodes)
        barcodes.sort(key = lambda v: (cnt[v], v), reverse = True)
        A = [0] * N
        A[::2], A[1::2] = barcodes[:(N+1)//2], barcodes[(N+1)//2:]
        return A

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        count = collections.Counter(barcodes)
        barcodes.sort(key=lambda a: (count[a], a))
        barcodes[1::2], barcodes[::2] = barcodes[0:len(barcodes) // 2], barcodes[len(barcodes) // 2:]
        return barcodes

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        dt = collections.Counter(barcodes)
        hp = []
        for code, freq in list(dt.items()):
            heapq.heappush(hp, (-freq, code))
        res = []
        while len(hp) > 1:
            freq1, bar1 = heapq.heappop(hp)
            freq2, bar2 = heapq.heappop(hp)
            res.append(bar1)
            res.append(bar2)
            if freq1 < -1:
                heapq.heappush(hp, (freq1+1, bar1))
            
            if freq2 < -1:
                heapq.heappush(hp, (freq2+1, bar2))
        
        if hp:
            res.append(heapq.heappop(hp)[1])
        
        return res
            


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        m = [0 for _ in range(10001)]
        max_cnt = 0
        max_n = 0
        for n in barcodes:
            m[n] += 1
            if m[n] > max_cnt:
                max_cnt = m[n]
                max_n = n 
                
        res = [0 for _ in range(len(barcodes))]
        pos = 0
        for i in range(10001):
            n = max_n if i == 0 else i
            
            while m[n] > 0:
                m[n] -= 1
                
                res[pos] = n
                pos = pos + 2 if pos + 2 < len(barcodes) else 1
                
                
        return res 

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        import heapq
        from collections import Counter

        cnt = Counter(barcodes)
        items = [(-v, k) for k, v in cnt.items()]

        heapq.heapify(items)
        res = []

        while len(items) > 1:

            v1, k1 = heapq.heappop(items)
            v1 += 1

            v2, k2 = heapq.heappop(items)
            v2 += 1

            res.extend([k1, k2])

            if v1 != 0:
                heapq.heappush(items, (v1, k1))

            if v2 != 0:
                heapq.heappush(items, (v2, k2))
                
        if len(items) == 1:
            res.append(items[0][1])

        return res

from collections import Counter
import heapq as q

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        c = Counter(barcodes)
        
        xs = []
        for k, v in list(c.items()):
            q.heappush(xs, (-v, k))
        
        r = []
        while len(xs) > 1:
            av, ak = q.heappop(xs)
            bv, bk = q.heappop(xs)
            
            r.append(ak)
            r.append(bk)
            
            av += 1
            bv += 1
            if av < 0:
                q.heappush(xs, (av, ak))
            if bv < 0:
                q.heappush(xs, (bv, bk))
        
        
        if len(xs) == 0: return r
        
        av, ak = q.heappop(xs)
        
        r.append(ak)
        
        return r
        


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        c=collections.Counter(barcodes)
        heap=[]
        for cha,time in list(c.items()):
            heapq.heappush(heap,(-time,cha))  
        res=[]
        while heap:
            n=len(heap)
            if n>=2:
                t1,c1=heapq.heappop(heap)
                res.append(c1)
                t2,c2=heapq.heappop(heap)
                res.append(c2)
                if t1+1<0:
                    heapq.heappush(heap,(t1+1,c1))
                if t2+1<0:
                    heapq.heappush(heap,(t2+1,c2))
            else:
                t,c=heapq.heappop(heap)
                res.append(c)
        return res


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        i, n = 0, len(barcodes)
        res = [0] * n
        for k, v in collections.Counter(barcodes).most_common():
            for _ in range(v):
                res[i] = k
                i += 2
                if i >= n: i = 1
        return res

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        h=[]
        c=collections.Counter(barcodes)
        for i in c:
            heapq.heappush(h,(-c[i],i))
        res=[]
        if len(barcodes)<2:
            return str(barcodes[0])
        while h:
            val1,char1=heapq.heappop(h)
            char2=''
            if h:
                val2,char2=heapq.heappop(h)
            res.append(char1)
            res.append(char2)
            
            if val1*(-1) > 1:
                heapq.heappush(h,(val1+1,char1))
            if val2*(-1)>1:
                heapq.heappush(h,(val2+1,char2))
        return res                        
            
            
            


from heapq import heappush,heappop
from collections import defaultdict

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        freq = defaultdict(int)
        for code in barcodes:
            freq[code] += 1
           
        maxH, res = [], []
        for num, count in freq.items():
            heappush(maxH, (-count, num))
        
        while maxH:
            count1, num1 = heappop(maxH)
            count1 += 1
            res.append(num1)
            if maxH:
                count2, num2 = heappop(maxH)
                res.append(num2)
                count2 += 1
                if count2 < 0:
                    heappush(maxH, (count2, num2))
            if count1 < 0:  
                heappush(maxH, (count1, num1))
        
        return res

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter = Counter(barcodes)
        heap = [(-v, c) for c, v in counter.items()]
        heapq.heapify(heap)
        res = []
        while heap:
            popped = []
            for _ in range(2):
                if not heap: return res
                v, c = heapq.heappop(heap)
                res.append(c)
                if v<-1:
                    popped.append([v+1, c])
            
            for v, c in popped:
                heapq.heappush(heap, (v, c))
                    
        return res

class Solution:
    def rearrangeBarcodes(self, barcodes):
        cnt = dict()
        for v in barcodes:
            cnt[v] = cnt.get(v, 0) + 1
        N = len(barcodes)
        barcodes.sort(key = lambda v: (-cnt[v], v))
        A = [0] * N
        A[::2], A[1::2] = barcodes[:(N+1)//2], barcodes[(N+1)//2:]
        return A

from collections import defaultdict
import heapq
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        d = defaultdict(int)
        heap = []
        res = []
        for bc in barcodes:
            d[bc] += 1
        
        for key, val in d.items():
            heapq.heappush(heap,(-val,key))
        while heap:
            cur = heapq.heappop(heap)
            if res and res[-1] == cur[1]:
                tmp = heapq.heappop(heap)
                res.append(tmp[1])
                val = 1 + tmp[0]
                if val != 0:
                    heapq.heappush(heap,(val, tmp[1]))
                heapq.heappush(heap,(cur))

            else:
                res.append(cur[1])
                v = cur[0] + 1
                if v != 0:
                    heapq.heappush(heap,(v, cur[1]))
        return res

from collections import Counter, deque
from heapq import *
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        count = Counter(barcodes)
        res = []
        maxHeap = []
        for num, freq in list(count.items()):
            heappush(maxHeap,(-freq, num))
        q = deque([])
        while maxHeap:
            negCnt, num = heappop(maxHeap)
            res.append(num)
            
            q.append((negCnt, num))
            if len(q) == 2:
                negCnt, num = q.popleft()
                negCnt += 1
                if negCnt < 0:
                    heappush(maxHeap, (negCnt, num))
        
        return res
                
        


import heapq as hq
from collections import Counter

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter = Counter(barcodes)
        cqueue = [(-v, k) for k, v in list(counter.items())]
        hq.heapify(cqueue)
        res = []
        while len(cqueue) > 0:
            neg_count, barcode = hq.heappop(cqueue)

            if len(res) != 0 and res[-1] == barcode:
                neg_count_2, barcode_2 = hq.heappop(cqueue)
                hq.heappush(cqueue, (neg_count, barcode))
                neg_count, barcode = neg_count_2, barcode_2
            res.append(barcode)

            if neg_count != -1:
                hq.heappush(cqueue, (neg_count + 1, barcode))
        
        return res
                
        


import heapq
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        count = {}
        for i in barcodes:
            if i not in count:
                count[i] = 0
            count[i] += 1
            
        heap = [(-v,k) for k,v in list(count.items())]
        heapq.heapify(heap)
        
        op = [None]
        i = 0
        
        while heap:
            temp = []
            while True:
                maxVal, maxKey = heapq.heappop(heap)
                if maxKey == op[-1]:
                    temp.append((maxVal, maxKey))
                else:
                    break
            
            op.append(maxKey)
            
            currVal = maxVal+1
            if currVal<0:
                heapq.heappush(heap,(currVal,maxKey))
                
            while temp:
                val,key = temp.pop()
                heapq.heappush(heap,(val,key))
            # print(\"This is heap:\",heap)        
        return op[1:]
        
                
                
                


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        '''
        Method
        
        
        1). Create a count the frequency
        2) use that count to create a min heap by taking the neg values of the count
        3) use the two highest count nums in the heap to change the barcode indicies
        4) at the same time, decrement said values by adding 1 and keep a check to see when the heap is empty
        5) at the end, make sure the heap is empty as there may be 1 extra value due to an odd num
        
        '''
        
        
        count = defaultdict(int)
        
        for i in barcodes:
            count[i] += 1
            
            
        heap= []
        
        for key, val in list(count.items()):
            heap.append([-val, key])
            
        heapq.heapify(heap)
        idx = 0
        
        while len(heap) > 1:
            one = heapq.heappop(heap)
            two = heapq.heappop(heap)
            
            barcodes[idx] = one[1]
            idx += 1
            barcodes[idx] = two[1]
            idx += 1
            
            one[0] += 1
            two[0] += 1
            
            
            if one[0] != 0:
                heapq.heappush(heap, one)
            if two[0] != 0:
                heapq.heappush(heap, two)
                
            
        if heap:
            barcodes[idx] = heapq.heappop(heap)[1]
            
        return barcodes
                
            



from heapq import heappush, heappop, heapify

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        # 1. Heap: O(N log N) Time, O(N) Space
#         counter = defaultdict(int)
#         for n in barcodes:
#             counter[n] += 1
        
#         maxHeap = []
#         for n, val in counter.items():
#             heappush(maxHeap, [-val, n])
        
#         prev = None
#         for i in range(len(barcodes)):
#             val, id = heappop(maxHeap)
#             if val < 0:
#                 temp = [val + 1, id]
#             else:
#                 temp = None
            
#             barcodes[i] = id
            
#             if prev:
#                 heappush(maxHeap, prev)
#             prev = temp
#         return barcodes

        # 2. Bucket Sort
        counter = Counter(barcodes)
        i = 0
        for n, count in counter.most_common():
            for _ in range(count):
                barcodes[i] = n
                i += 2
                if i >= len(barcodes):
                    i = 1
        return barcodes
            
        
        


class Solution:
    def update(self, freq, key, heap):
        if freq > 1:
            heappush(heap, (-1 * (freq - 1), key))
            
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        freq_map = defaultdict(int)
        heap = []
        res = []
        for n in barcodes:
            freq_map[n] += 1
        
        for key in list(freq_map.keys()):
            heappush(heap, (-1 * freq_map[key], key))
        
        while len(heap) > 0:
            freq_a, key_a = heappop(heap)
            res.append(key_a)
            
            if len(heap) == 0:
                break
            freq_b, key_b = heappop(heap)
            res.append(key_b)
            self.update(-1 * freq_a, key_a, heap)
            self.update(-1 * freq_b, key_b, heap)
        return res


import heapq
from collections import Counter

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counts = Counter(barcodes)
        arr = [[-v, k] for k, v in list(counts.items())]
        heapq.heapify(arr)
        newBarcodes = []
        while len(arr) != 0:
            elem1 = heapq.heappop(arr)
            newBarcodes.append(elem1[1])
            if len(arr) == 0:
                return newBarcodes
            elem2 = heapq.heappop(arr)
            newBarcodes.append(elem2[1])
            elem1[0] += 1
            if elem1[0] < 0:
                heapq.heappush(arr, elem1)
            elem2[0] += 1
            if elem2[0] < 0:
                heapq.heappush(arr, elem2)
        return newBarcodes
            


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        h=collections.Counter(barcodes)
        heap=[(-value,key) for key,value in list(h.items())]
        heapq.heapify(heap)
        a=[]
        while heap:
            x=heapq.heappop(heap)
            if heap==[]:
                a.append(x[1])
                return a
            y=heapq.heappop(heap)
            a.append(x[1])
            a.append(y[1])
            if x[0]+1!=0:
                heapq.heappush(heap,(x[0]+1,x[1]))
            if y[0]+1!=0:
                heapq.heappush(heap,(y[0]+1,y[1]))
        return a
            


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        freq = {}
        
        # create frq
        for b in barcodes:
            if b in freq:
                freq[b] += 1
            else:
                freq[b] = 1
        
        descBarcode = sorted([(k, v) for (k, v) in list(freq.items())], key=lambda i: i[1], reverse=True)
        # print(descBarcode)
        
        newBarcode = []
        maxIncrements = descBarcode[0][1] # -1
        
        curIndex, curIncrements = 1, 0
        for num, count in descBarcode:
            if not newBarcode:
                newBarcode = [num] * count
            else:
                while count > 0:
                    # print(f\"Inserting {num} at {curIndex}\", newBarcode)
                    newBarcode.insert( curIndex, num )
                    curIndex += 2
                    maxIncrements += 1
                    if curIncrements > maxIncrements or curIndex > len(newBarcode):
                        curIndex = 1
                        maxIncrements = 0
                    count -= 1
        
        # for i in range(len(newBarcode)):
        #     if i > 0 and newBarcode[i] == newBarcode[i-1]:
        #         newBarcode.pop(i)
        #         newBarcode.insert(0, newBarcode[i-1])
        # # print(newBarcode)
        return newBarcode
                
        
        
                


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        if len(barcodes) < 2:
            return barcodes
        
        counter = collections.Counter(barcodes)
        
        heap = []
        
        for k,v in counter.items():
            heapq.heappush(heap,(-v,k))
        result = []
        while len(heap) > 1:
            count1,key1 = heapq.heappop(heap)
            count2,key2 = heapq.heappop(heap)
            result.append(key1)
            result.append(key2)
            count1 +=1
            count2+=1
            if count1 < 0:
                heapq.heappush(heap,(count1,key1))
            if count2 < 0:
                heapq.heappush(heap,(count2,key2))
        
        print(heap)
        if len(heap) > 0:
            count,key = heapq.heappop(heap)
            result.append(key)
            return result
        else:
            return result

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        freq = [0] * 10001
        maxFreqCode = 0
        for code in barcodes:
            freq[code] += 1
            if freq[code] > freq[maxFreqCode]:
                maxFreqCode = code
        i, n = 0, len(barcodes)
        ans = [0] * n
        for code in range(10001):    
            if code == 0:
                code = maxFreqCode
            for _ in range(freq[code]):
                if i >= n:
                    i = 1
                ans[i] = code
                i += 2
            freq[code] = 0    
        return ans

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        freq = {}
        
        # create frq
        for b in barcodes:
            if b in freq:
                freq[b] += 1
            else:
                freq[b] = 1
        
        frqBarcode = [(k, v) for (k, v) in list(freq.items())]
        maxNum, maxIncrements = max(frqBarcode, key=lambda i: i[1])
        
        newBarcode = [maxNum] * maxIncrements
        
        curIndex, curIncrements = 1, 0
        for num, count in frqBarcode:
            if num == maxNum:
                continue
            while count > 0:
                newBarcode.insert( curIndex, num )
                curIndex += 2
                maxIncrements += 1
                if curIncrements > maxIncrements or curIndex > len(newBarcode):
                    curIndex = 1
                    maxIncrements = 0
                count -= 1

        return newBarcode
                
        
        
                


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        h=[]
        d=defaultdict(int)
        for ele in barcodes:
            d[ele]+=1
            
        for key, val in d.items():
            heappush(h, (-1*val, key))
        res=[]
        prev=()
        while h:
            ele=heappop(h)
            freq=ele[0]*-1
            res.append(ele[1])
            if prev!=():
                heappush(h, prev)
            if freq!=1:
                prev=(-1*(freq-1), ele[1])
            else:
                prev=()
        return res

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        hq = [(-v, i) for i, v in collections.Counter(barcodes).items()]
        heapq.heapify(hq)
        
        res = []
        while hq:
            temp = []
            for _ in range(min(len(hq), 2)):
                val, number = heapq.heappop(hq)
                temp.append((val, number))
                res.append(number)
            
            for _ in range(len(temp)):
                val, number = temp.pop()
                if val < -1:
                    heapq.heappush(hq,(val+1, number))
        
        return res

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        freq = {}
        
        # create frq
        for b in barcodes:
            if b in freq:
                freq[b] += 1
            else:
                freq[b] = 1
        
        descBarcode = sorted([(k, v) for (k, v) in list(freq.items())], key=lambda i: i[1], reverse=True)
        
        newBarcode = []
        maxIncrements = descBarcode[0][1] # -1
        
        curIndex, curIncrements = 1, 0
        for num, count in descBarcode:
            if not newBarcode:
                newBarcode = [num] * count
            else:
                while count > 0:
                    newBarcode.insert( curIndex, num )
                    curIndex += 2
                    maxIncrements += 1
                    if curIncrements > maxIncrements or curIndex > len(newBarcode):
                        curIndex = 1
                        maxIncrements = 0
                    count -= 1

        return newBarcode
                
        
        
                


from collections import Counter

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        freqs = Counter(barcodes)
        result = [-1] * len(barcodes)
        i = 0
        for bc, c in sorted(freqs.items(), key=lambda x: -x[1]):
            for _ in range(c):
                if i >= len(result):
                    i = 1
                result[i] = bc
                i += 2
        return result

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        if len(barcodes) <= 1:
            return barcodes
        
        def helper(barcodes, k):
            
            freqCount = collections.defaultdict(int)
            for ele in barcodes:
                freqCount[ele] += 1
                
            result = []
            cooldown = collections.deque()
            heap = []
            for key, value in freqCount.items():
                heapq.heappush(heap, (-value, key))
                
            while len(heap) > 0:
                
                count, element = heapq.heappop(heap)
                count *= -1
                
                result.append(element)
                cooldown.append((count - 1, element))
                if len(cooldown) < k:
                    continue
                cooldownCount, cooldownElement = cooldown.popleft()
                if cooldownCount > 0:
                    heapq.heappush(heap, (-cooldownCount, cooldownElement))
                    
            return result
        
        return helper(barcodes, 2)

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counts = {k: 0 for k in barcodes}
        for n in barcodes:
            counts[n] += 1
        # barcode = []
        # def backtrack(size):
        #     if len(barcode) == size:
        #         return True
        #     for k in counts:
        #         if counts[k] > 0:
        #             if len(barcode) == 0 or barcode[-1] != k:
        #                 barcode.append(k)
        #                 counts[k] -= 1
        #                 if backtrack(size):
        #                     return True
        #                 else:
        #                     barcode.pop()
        #                     counts[k] += 1
        #     return False
        # backtrack(len(barcodes))
        # return barcode
        barcodes.sort()
        barcode = []
        
        heap = [(-y,x) for x,y in list(counts.items())]
        heapq.heapify(heap)
        print(heap)
        
        while len(heap) > 0:
            freq,digit = heapq.heappop(heap)
            if len(barcode) == 0 or barcode[-1] != digit:
                barcode.append(digit)
                if freq < -1:
                    freq += 1
                    heapq.heappush(heap,(freq,digit))
            else:
                nextFreq,nextDig = heapq.heappop(heap)
                barcode.append(nextDig)
                heapq.heappush(heap,(freq,digit))
                if nextFreq < -1:
                    nextFreq += 1
                    heapq.heappush(heap,(nextFreq,nextDig))
                    
        
        
        return barcode
            
                
                
                    


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        cnts = collections.defaultdict(int)
        for n in barcodes:
            cnts[n] += 1
        
        barcodes.sort(key = lambda x : (cnts[x], x))
        n = len(barcodes)
        first, second = barcodes[:n//2], barcodes[n//2:]
        res = []
        f, s = 0, 0
        #print(barcodes)
        #print(first, second)
        while f < len(first) or s < len(second):
            if s < len(second):
                res.append(second[s])
                s += 1
            if f < len(first):
                res.append(first[f])
                f += 1
        return res


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        q = [[-v, k] for k, v in collections.Counter(barcodes).items()]
        heapq.heapify(q)
        result = []
        while q:
            if result and result[-1] == q[0][1]:
                tmp = heapq.heappop(q)
                item = heapq.heappop(q)
                result.append(item[1])
                item[0] += 1
                if item[0] < 0:
                    heapq.heappush(q, item)
                heapq.heappush(q, tmp)
            else:
                item = heapq.heappop(q)
                result.append(item[1])
                item[0] += 1
                if item[0] < 0:
                    heapq.heappush(q, item)
        return result

from collections import Counter, defaultdict
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter = Counter(barcodes)
        memo = defaultdict(list)
        rest = 0
        for e, c in counter.most_common():
            memo[c].append(e)
            rest += c
        ret = []
        while rest:
            rest -= 1
            for c in sorted(memo.keys(), reverse=True):
                for idx, e in enumerate(memo[c]):
                    if ret and ret[-1] == e:
                        continue                
                    ret.append(e)
                    del memo[c][idx]
                    if not memo[c]:
                        del memo[c]
                    memo[c-1].append(e)
                    break
                if rest == len(barcodes) - len(ret):
                    break
                    
        return ret

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256
\"\"\"
startSI
nextSI
totalUsed

curEnd = si + (cnt - 1) * (m+1)
if curEnd >= nextSI:
    nextSI = curEnd + 1

if startSI

totalUsed += cnt

123123144 -> 143124123 -> 12312412455
14312412355


\"\"\"

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *

from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256


class Solution:

    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        h = []
        N = len(barcodes)
        ans = []
        cnts = {}
        for c in barcodes:
            if not c in cnts:
                cnts[c] = 0
            cnts[c] += 1
        for c, cnt in cnts.items():
            heappush(h, (-cnt, c))
        while len(h):
            negCnt, c = heappop(h)
            if len(ans) and c == ans[-1]:
                negCnt2, c2 = heappop(h)
                ans.append(c2)
                newCnt2 = -negCnt2 - 1
                if newCnt2:
                    heappush(h, (-newCnt2, c2))
                heappush(h, (negCnt, c))
            else:
                ans.append(c)
                newCnt = -negCnt - 1
                if newCnt:
                    heappush(h, (-newCnt, c))
        return ans

\"\"\"
S = Solution()
l = [1, 1, 1, 2, 2, 2]
l = [1, 1, 1, 1, 2, 2, 3, 3]
print(S.rearrangeBarcodes(l))
\"\"\"

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        if len(barcodes) <= 1:
            return barcodes
        counts = defaultdict(int)
        for b in barcodes:
            counts[b] += 1
        max_count = 0
        max_b = 0
        for b, c in counts.items():
            if c > max_count:
                max_count = c
                max_b = b
        everything_else = [b for b in barcodes if b != max_b]
        arranged = [max_b] * max_count
        # Split everything once
        i = 1
        while i <= len(arranged) and len(everything_else) != 0:
            arranged.insert(i, everything_else.pop(0))
            i += 2
        # Add everything else
        def can_add_at(i, b):
            if i == 0:
                return arranged[i] != b
            elif i == len(arranged):
                return arranged[-1] != b
            else:
                return arranged[i] != b and arranged[i-1] != b
        i = 0
        while len(everything_else) != 0:
            if can_add_at(i, everything_else[0]):
                arranged.insert(i, everything_else.pop(0))
            i += 1
        return arranged

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        queue = deque()
        heap = []
        d = {}
        res = []
        time = 0
        
        for code in barcodes:
            d[code] = d.get(code, 0) - 1
        
        for k, v in d.items():
            heapq.heappush(heap, (v, k))
        
        while heap or queue:
            if heap:
                count, code = heapq.heappop(heap)
                count += 1
                res.append(code)

                if count < 0:
                    queue.append([time + 1, (count, code)])
            
            if queue and queue[0][0] <= time:
                heapq.heappush(heap, queue.popleft()[1])
            
            time += 1
        
        return res

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        i, n = 0, len(barcodes)
        
        res = [0] * n
        
        for k, v in collections.Counter(barcodes).most_common():
            for _ in range(v):
                res[i] = k
                i += 2
                if i >= n: 
                    i = 1
        return res

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        import heapq
        n=len(barcodes)
        d={}
        for x in barcodes:
            if(d.get(x)!=None):
                d[x]+=1
            else:
                d[x]=1
        barcodes=[]
        for x in list(d.keys()):
            heapq.heappush(barcodes,(-d[x],x))
        ans=[]
        for x in range(n):
            temp=[]
            if(ans==[]):
                curr=heapq.heappop(barcodes)
                ans.append(curr[1])
                if(curr[0]!=-1):
                    heapq.heappush(barcodes,(curr[0]+1,curr[1]))
                # print(barcodes)
            else:
                while(True):
                    # print(barcodes,ans)
                    curr=heapq.heappop(barcodes)
                    if(ans[-1]!=curr[1]):
                        ans.append(curr[1])
                        if(curr[0]!=-1):
                            heapq.heappush(barcodes,(curr[0]+1,curr[1]))
                        break
                    else:
                        temp.append(curr)
                while(len(temp)):
                    heapq.heappush(barcodes,temp.pop())
        return ans

            


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        l=barcodes[::]
        n=len(l)
        c=Counter(l)
        c=list(sorted(list(c.items()),key=lambda x:-x[1]))
        nl=[0]*n
        y=0
        x=c[y][1]
        val=c[y][0]
        for i in range(0,n,2):
            nl[i]=val
            x-=1
            if x==0:
                y+=1
                if y<len(c):
                    x=c[y][1]
                    val=c[y][0]        
        for i in range(1,n,2):
            nl[i]=val
            x-=1
            if x==0:
                y+=1
                if y<len(c):
                    x=c[y][1]
                    val=c[y][0]
        return nl
            


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        i, n = 0, len(barcodes)
        res = [0] * n
        for k, v in collections.Counter(barcodes).most_common():
            for _ in range(v):
                res[i] = k
                i += 2
                if i >= n: i = 1
                # print(res)
        return res

import heapq
from collections import Counter
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        ans = []
        c = Counter(barcodes)
        heap = []
        for b in c:
            heapq.heappush(heap, (-c[b], b))
        while(heap):
            temp = heapq.heappop(heap)
            if(ans and ans[-1] == temp[1]):
                temp2 = heapq.heappop(heap)
                ans.append(temp2[1])
                heapq.heappush(heap, (temp[0], temp[1]))
                if(temp2[0] < -1):
                    heapq.heappush(heap, (temp2[0]+1, temp2[1]))
            else:
                ans.append(temp[1])
                if(temp[0] < -1):
                    heapq.heappush(heap, (temp[0]+1, temp[1]))
        return ans

from collections import Counter, defaultdict
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter = Counter(barcodes)
        memo = defaultdict(list)
        rest = 0
        for e, c in counter.most_common():
            memo[c].append(e)
            rest += c
        ret = []
        while rest:
            rest -= 1
            for c in sorted(memo.keys(), reverse=True):
                for idx, e in enumerate(memo[c]):
                    if ret and ret[-1] == e:
                        continue                
                    ret.append(e)
                    del memo[c][idx]
                    if not memo[c]:
                        del memo[c]
                    memo[c-1].append(e)
                    break
                if rest == len(barcodes) - len(ret):
                    break
                    
                    
        return ret

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        d=collections.Counter(barcodes)
        res=[]
        pq=[]
        for no,f in list(d.items()):
            heapq.heappush(pq,[-f,no])
        temp=[]    
        while len(pq)!=0 or temp!=0:
            if(len(pq)!=0):
                f,no=heapq.heappop(pq)
                if(temp!=[]):
                    heapq.heappush(pq,temp)
                    temp=[]
            else:
                if(temp!=[]):
                    f,no=temp
                    temp=[]
                else:
                    break
            f=f*-1
            f=f-1
            res.append(no)
            if(f!=0):
                if(len(pq)==0):
                    heapq.heappush(pq,[-f,no])
                elif -f>pq[0][0]:
                    heapq.heappush(pq,[-f,no])
                else:
                    temp=[-f,no]
                    
                
        return res        


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        d = Counter(barcodes)
        cand = barcodes[0]
        maxi = d[cand]
        
        for idx,(k,v) in enumerate(d.items()):
            
            if v > maxi:
                maxi = v
                cand = k
        
        res =[None for i in range(len(barcodes))]
        pos = 0
        for i in range(maxi):
            res[pos] = cand
            pos+=2
        
        del d[cand]
        
        for idx,(k,v) in enumerate(d.items()):
            
            for j in range(v):
                if pos >= len(res):
                    pos = 1
                    
                res[pos] = k
                pos+=2
        
        return res
                
            
            
        


import heapq
from collections import Counter
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
            c = Counter(barcodes)
            heap = []
            res = []
            for key, val in list(c.items()):
                heap.append((-val, key))
                
            heapq.heapify(heap)
            prevCnt = 0
            
            while heap:
                cnt, code = heapq.heappop(heap)
                cnt = -cnt
                res.append(code)
                if prevCnt>0: heapq.heappush(heap, (-prevCnt, prevCode))
                prevCnt = cnt-1
                prevCode = code
                
            return res
                


import collections
from heapq import heappush, heappop
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        elementCountMap = collections.Counter(barcodes)
        elementStack = []
        for element, count in list(elementCountMap.items()):
            heappush(elementStack, [-count, element])
        
        result = []
        
        previousElement = None
        
        while elementStack:
            tmp = None
            count, element = heappop(elementStack)
            if element == previousElement:
                tmp = [count, element]
                count, element = heappop(elementStack)
                
            result.append(element)
            previousElement = element
            count += 1
            if count < 0:
                heappush(elementStack, [count, element])
            
            if tmp:
                heappush(elementStack, tmp)
                
        return result


import heapq
from collections import Counter
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        maxheap=[]
        K=0
        map1=Counter(barcodes)
        index=0
        for k,v in list(map1.items()):
            heappush(maxheap,(-v,k))
        
        res=[0]*len(barcodes)
        while len(maxheap)>0:
            
            element=heappop(maxheap)
            
            res[index]=element[1]
            if len(maxheap)==0:
                break
            index+=1
            
            element2=heappop(maxheap)
            
            res[index]= element2[1]
            
            self.updateMap(map1,maxheap,element)
            self.updateMap(map1,maxheap,element2)
            
            index+=1
        return res
    def updateMap(self,map1,maxheap,element):
        if map1[element[1]]==1:
            del map1[element[1]]
        else:
            map1[element[1]]=map1[element[1]]-1

            heappush(maxheap,(-map1[element[1]],element[1]))


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        count=Counter(barcodes)
        heap=[(-count[x],x) for x in list(count.keys())]
        heapq.heapify(heap)
        out=[]
        while len(heap)>1:
            count1, code1=heapq.heappop(heap)
            count2, code2=heapq.heappop(heap)
            out.extend([code1,code2])
            count1+=1
            count2+=1
            if count1<0: heapq.heappush(heap, (count1,code1))
            if count2<0: heapq.heappush(heap, (count2,code2))
        if heap:
            count1,code1=heapq.heappop(heap)
            out+=[code1]
        return out


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        cnts = collections.Counter(barcodes)
        heap = [(-v, k) for k,v in list(cnts.items())]
        heapq.heapify(heap)
        res = []
        
        while heap:
            cnt1, num1 = heapq.heappop(heap)
            if res and res[-1] == num1:
                cnt, num = heapq.heappop(heap)
                res.append(num)
                cnt += 1
                if cnt != 0:
                    heapq.heappush(heap, (cnt, num))
                res.append(num1)
                cnt1 += 1
                if cnt1 != 0:
                    heapq.heappush(heap, (cnt1, num1))
            else:
                res.append(num1)
                cnt1 += 1
                if cnt1 != 0:
                    heapq.heappush(heap, (cnt1, num1))
            
        return res
    
# Run time O(NlogN), space O(N)


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        d = defaultdict(lambda:0)
        for b in barcodes:
            d[b] += 1
        
        #heap = [(d[b],b) for b in barcodes]
        counter = 0
        heap = []
        for b in d:
            heap.append((-d[b],counter,b))
            counter += 1
        heapify(heap)
        result = []
        while heap:
            count1,tmp,b1 = heappop(heap)
            result.append(b1)
            if not heap:
                return result
            
            count2,tmp,b2 = heappop(heap)
            result.append(b2)
            
            count1 += 1
            count2 += 1
            
            if count1:
                heappush(heap, (count1,counter,b1))
                counter += 1
            if count2:
                heappush(heap, (count2,counter,b2))
                counter += 1
        return result

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        freq = dict()
        
        for i in range(len(barcodes)):
            freq[barcodes[i]] = freq.get(barcodes[i], 0)+1
        
        heap = list()
        reverse = collections.defaultdict(list)
        
        for el in freq:
            heap.append(-freq[el])
            reverse[freq[el]].append(el)
        
        heapq.heapify(heap)
        
        temp_list = list()
        answer = list()
        
        while True:
            if len(temp_list)>1:
                temp = temp_list.pop(0)
                if temp[0]>0:
                    heapq.heappush(heap, -temp[0])
                    reverse[temp[0]].append(temp[1])
            
            if len(heap)>0:
                cur_freq = -heapq.heappop(heap)
                cur_el = reverse[cur_freq].pop(0)
                answer.append(cur_el)
                temp_list.append([cur_freq-1, cur_el])
            else:
                break
            
        while len(temp_list)>0:
            temp = temp_list.pop(0)
            if temp[0]>0:
                answer.append(temp[1])
                
        return answer


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:

        count = collections.Counter(barcodes)
        
        ans = [0] * len(barcodes)
        
        index = 0
        for key, freq in count.most_common():
            
            for _ in range(freq):
                if index >= len(barcodes):
                    index = 1
                ans[index] = key
                index += 2
                
        return ans
                
            


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        import heapq
        from collections import defaultdict
        
        d = defaultdict(int)
        
        for i in barcodes:
            d[i] += 1
        h = []
        for i in d:
            h.append((-d[i], i))
        heapq.heapify(h)
        ans = []
        
        while(len(h) > 1):
            c1, val1 = heapq.heappop(h)
            c2, val2 = heapq.heappop(h)
            
            c1 += 1
            c2 += 1
            
            ans.append(val1)
            ans.append(val2)
            
            if c1:
                heapq.heappush(h, (c1, val1))
            if c2:
                heapq.heappush(h, (c2, val2))
                
        if h:
            ans.append(heapq.heappop(h)[1])
        
        return ans


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        c = Counter(barcodes)
        heap = []
        ans = []
        for k, v in c.items():
            heapq.heappush(heap, (-v, k))
        while heap:
            # print(heap)
            most, d1 = heapq.heappop(heap)
            if ans and ans[-1]==d1:
                more, d2 = heapq.heappop(heap)
                ans.append(d2)
                if more < -1:
                    heapq.heappush(heap, (more+1, d2))
                heapq.heappush(heap, (most, d1))
                continue
            ans.append(d1)
            if most < -1:
                heapq.heappush(heap, (most+1, d1))
        # print('done')
        return ans

import collections
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        dic={}
        lst=[0]*len(barcodes)
        for i in barcodes:
            if(i in dic):
                dic[i]+=1
            else:
                dic[i]=1
        sorted_x = sorted(dic.items(), key=lambda kv: kv[1],reverse=True)
        sorted_dict = collections.OrderedDict(sorted_x)
        var=0
        for i,j in sorted_dict.items():
            for _ in range(j):
                lst[var]=i
                var+=2
                if(var>=len(barcodes)):
                    var=1
        return(lst)

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        if not barcodes:
            return []
        res = [None] * len(barcodes)
        barCount = collections.defaultdict(int)
        for barcode in barcodes:
            barCount[barcode] += 1
        mostFreq = max(barCount, key = barCount.get)
        i = 0
        for _ in range(barCount[mostFreq]):
            res[i] = mostFreq
            i += 2
        if i >= len(barcodes):
            i = 1
        barSet = set(barcodes)
        barSet.remove(mostFreq)
        for key in barSet:
            if key == mostFreq:
                continue
            for _ in range(barCount[key]):
                res[i] = key
                i += 2
                if i >= len(barcodes):
                    i = 1
        return res


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        cnts = collections.defaultdict(int)
        for n in barcodes:
            cnts[n] += 1
        barcodes.sort(key = lambda x : (cnts[x], x))
        n = len(barcodes)
        first, second = barcodes[:n//2], barcodes[n//2:]
        res = []
        f, s = 0, 0
        while f < len(first) or s < len(second):
            if s < len(second):
                res.append(second[s])
                s += 1
            if f < len(first):
                res.append(first[f])
                f += 1
        return res


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter = Counter(barcodes)
        keys = sorted(list(counter.keys()), key = lambda k:counter[k], reverse=True)
        numbers = []
        for key in keys:
            numbers.extend([key]*counter[key])
        ans = [0]*len(numbers)
        N = len(numbers)
        ans[::2] = numbers[:(N+1)//2]
        ans[1::2] = numbers[(N+1)//2:]
        return ans


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        cnt = Counter(barcodes)
        M = 0
        
        for k, v in cnt.items():
            if v>M:
                mark = k
                M = v
        
        barcodes.sort()
        pos = defaultdict(list)
        j = 0
        
        for i in range(len(barcodes)):
            if barcodes[i]!=mark:
                pos[j].append(barcodes[i])
                j = (j+1)%M
        
        ans = []
        
        for i in range(M):
            ans += [mark]+pos[i]
        
        return ans

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        count = Counter(barcodes)
        pq = []
        for c in count:
            heappush(pq, [-count[c],c])
        # print(pq)
        output = []
        prev = None
        
        while pq:
            
            # if output and output[-1] == pq[0]:
            #     toPush = heappop(pq)
                
            c, v = heappop(pq)
            c += 1
            output.append(v)
            
            if prev:
                heappush(pq, prev)
                prev = None
            
            if c != 0:
                prev = [c, v]
        
        return output


class Solution:
    def rearrangeBarcodes(self, a: List[int]) -> List[int]:
        count = collections.Counter(a)
        a.sort(key=lambda x: (count[x], x))
        a[1::2], a[::2] = a[:len(a)//2], a[len(a)//2:]
        return a

class Solution:
    def rearrangeBarcodes(self, A: List[int]) -> List[int]:
        count = collections.Counter(A)
        A.sort(key=lambda a: (count[a], a))
        A[1::2], A[::2] = A[0:len(A) // 2], A[len(A) // 2:]
        return A


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        counter = collections.Counter(barcodes)
        
        pq = []
        
        for key,value in counter.items():
            heapq.heappush(pq,(-value,key))
        
        temp_list = []
            
        result = []
        
        while pq:
            
            k = 2
        
            while pq and k > 0:
                
                #print(pq)
                
                count, curr = heapq.heappop(pq)
                count = count * -1
                
                result.append(curr)
                
                if count > 1:
                    temp_list.append((count-1,curr))
            
                k -= 1
            
            if len(temp_list) == 0 and len(pq) == 0:
                break
            
            while temp_list:
                
                count, curr = temp_list.pop()
                
                heapq.heappush(pq,(-count,curr))
            
        return result

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter_dict = collections.Counter(barcodes)
        kk_heap = []
        for it in list(counter_dict.items()):
            heapq.heappush(kk_heap, [-it[1], it[0]])
                    
        last_kk = None
        res = []
        
        while kk_heap:
            if len(kk_heap) == 1:
                res.append(kk_heap[0][1])
                break
                
            choose_from = [heapq.heappop(kk_heap), heapq.heappop(kk_heap)]
            idx = 0 if last_kk != choose_from[0][1] else 1
            kk = choose_from[idx][1]
            
            res.append(kk)
            choose_from[idx][0] += 1
            for cf in choose_from:
                if cf[0]:
                    heapq.heappush(kk_heap, cf)
            last_kk = kk
            
        return res
        


class Solution:
    def rearrangeBarcodes(self, S: List[int]) -> List[int]:
        if not S:
            return []
        
        d = collections.Counter(S)
        heap = []
        for key,value in list(d.items()):
            heapq.heappush(heap,[-value,key])
            
        res = []
        pre = heapq.heappop(heap)
        res.append(pre[1])
        
        while heap:
            cur = heapq.heappop(heap)
            res.append(cur[1])
            
            pre[0] += 1
            if pre[0] < 0:
                heapq.heappush(heap,pre)
                
            pre = cur
            
        if len(res) != len(S):
            return []
        else:
            return res
            


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        cnts = collections.Counter(barcodes)
        heap = [(-v, k) for k,v in list(cnts.items())]
        heapq.heapify(heap)
        res = []
        
        while heap:
            cnt1, num1 = heapq.heappop(heap)
            if res and res[-1] == num1:
                cnt, num = heapq.heappop(heap)
                res.append(num)
                cnt += 1
                if cnt != 0:
                    heapq.heappush(heap, (cnt, num))
                heapq.heappush(heap, (cnt1, num1))
            else:
                res.append(num1)
                cnt1 += 1
                if cnt1 != 0:
                    heapq.heappush(heap, (cnt1, num1))
            
        return res
    
# Run time O(NlogN), space O(N)


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        cnts = collections.Counter(barcodes)
        heap = [(-v, k) for k,v in cnts.items()]
        heapq.heapify(heap)
        res = []
        
        while heap:
            cnt1, num1 = heapq.heappop(heap)
            if res and res[-1] == num1:
                cnt, num = heapq.heappop(heap)
                res.append(num)
                cnt += 1
                if cnt != 0:
                    heapq.heappush(heap, (cnt, num))
                heapq.heappush(heap, (cnt1, num1))
            else:
                res.append(num1)
                cnt1 += 1
                if cnt1 != 0:
                    heapq.heappush(heap, (cnt1, num1))
            
        return res

from collections import Counter
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counts = Counter(barcodes)
        n = len(barcodes)
        res = [0] * n
        i = 0
        for k,v in counts.most_common():
            while v>0:
                res[i] = k
                i += 2
                v -= 1
                if i>n-1:
                    i = 1
        return res


from collections import Counter
import itertools
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        barcodes = [(freq, k) for k, freq in Counter(barcodes).items()]
        barcodes.sort(reverse=True)
        barcodes = list(itertools.chain.from_iterable([[k]*f for f, k in barcodes]))
        res=[\"\"]*len(barcodes)
        i = 0
        j = 0
        while j < len(barcodes):
            res[i] = barcodes[j]
            i=i+2
            j=j+1
            if i > len(res)-1:
                i=1
        return res
        
        

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        import collections
        import heapq
        
        c_dic = collections.Counter(barcodes)
        hp = []
        for key in c_dic:
            heapq.heappush(hp, (-c_dic[key],key))
            
        res = []
        while hp:
            collect = []
            if res:
                while hp[0][1] == res[-1]:
                    cur = heapq.heappop(hp)
                    collect.append(cur)
            
            cur = heapq.heappop(hp)   
            res.append(cur[1])
            if cur[0] != -1:
                heapq.heappush(hp, (cur[0]+1, cur[1]))
                
            for nodes in collect:
                heapq.heappush(hp, nodes)
                
        return res

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        c=collections.Counter(barcodes)
        heap=[]
        for cha,time in c.items():
            heapq.heappush(heap,(-time,cha))  
        res=[]
        while heap:
            n=len(heap)
            if n>=2:
                t1,c1=heapq.heappop(heap)
                res.append(c1)
                t2,c2=heapq.heappop(heap)
                res.append(c2)
                if t1+1<0:
                    heapq.heappush(heap,(t1+1,c1))
                if t2+1<0:
                    heapq.heappush(heap,(t2+1,c2))
            else:
                t,c=heapq.heappop(heap)
                res.append(c)
        return res

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        cb = collections.Counter(barcodes)
        for kk,l in cb.most_common():
            out = [[kk] for _ in range(l)]
            break
        i = 0
        for k in cb:
            if k != kk:
                for v in range(cb[k]):
                    out[i%l].append(k)
                    i += 1
        output = []
        for o in out:
            output += o
        return output

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        if len(barcodes) <= 1:
            return barcodes
        
        heap, res = [], []
        counter = collections.Counter(barcodes)
        for val, cnt in counter.items():
            heapq.heappush(heap, (-cnt, val))
        
        res = []
        while len(heap) > 1:
            cnt1, val1 = heapq.heappop(heap)
            cnt2, val2 = heapq.heappop(heap)
            res.extend([val1, val2])
            cnt1 += 1
            cnt2 += 1
            if cnt1: heapq.heappush(heap, (cnt1, val1))
            if cnt2: heapq.heappush(heap, (cnt2, val2))
        
        if heap:
            res.append(heap[0][1])
        return res 

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        freq = collections.Counter(barcodes)
        heap = []
        for k, v in freq.items():
            heapq.heappush(heap, (-v, k))
        ans = []
        while heap:
            freq, num = heapq.heappop(heap)
            if not ans:
                ans.append(num)
                freq += 1
                if freq < 0:
                    heapq.heappush(heap, (freq, num))
            else:
                if num == ans[-1]:
                    nextFreq, nextNum = heapq.heappop(heap)
                    ans.append(nextNum)
                    nextFreq += 1
                    if nextFreq < 0:
                        heapq.heappush(heap, (nextFreq, nextNum))
                    heapq.heappush(heap, (freq, num))
                else:
                    ans.append(num)
                    freq += 1
                    if freq < 0:
                        heapq.heappush(heap, (freq, num))
        return ans

from collections import Counter
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        if barcodes is None or len(barcodes) == 0:
            return []
        if len(barcodes) == 1:
            return barcodes

        counter = Counter(barcodes)
        num_occurrences = sorted(counter, key = lambda x: counter.get(x), reverse=True)
        elements = dict()

        for elem in num_occurrences:
            elements[elem] = counter[elem]

        output = [None] * len(barcodes)
        item_index = 0
        index = 0
        value = num_occurrences[0]
        value_index= 0
        for i in range(len(barcodes)):
            while output[index] is not None or output[index - 1] == value:
                index += 1
                index %= len(barcodes)
            output[index] = value
            item_index += 1
            index += 1
            index %= len(barcodes)
            if elements[value] == 1:
                value_index += 1
                if value_index >= len(num_occurrences):
                    return output
                value = num_occurrences[value_index]
            else:
                elements[value] -= 1

        return output

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        # Get the counts of all of our barcode elements.
        cnts = collections.Counter(barcodes)
\t\t# Put the -'ve counts along with themselves into a min heap.
\t\t# For those new to this we use -'ve because this is a min heap, so largest cnt pop'd first.
        heap = [(-v, k) for k,v in cnts.items()]
        heapq.heapify(heap)
        res = []
        # While we have elements on our heap.
        while heap:
\t\t    # pop the top element.
            cnt1, num1 = heapq.heappop(heap)
\t\t\t# If the top element was the last we used, we need something different.
            if res and res[-1] == num1:
\t\t\t    # pop the next highest cnt element. 
                cnt, num = heapq.heappop(heap)
                res.append(num)
                cnt += 1
\t\t\t\t# If there's still elements left we put them back on the heap.
                if cnt != 0:
                    heapq.heappush(heap, (cnt, num))
\t\t\t\t# We can also add the first that we popped, and push it back on the heap as well.
                res.append(num1)
                cnt1 += 1
                if cnt1 != 0:
                    heapq.heappush(heap, (cnt1, num1))
\t\t\t# else we just add the highest cnt element and put the remaining back on.
            else:
                res.append(num1)
                cnt1 += 1
                if cnt1 != 0:
                    heapq.heappush(heap, (cnt1, num1))
            
        return res
    
# Run time O(NlogN), space O(N)

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        if barcodes is None or len(barcodes) ==0:
            return []
        
        n = len(barcodes)
        dict_t ={}
        
        for i in range(n):
            temp = barcodes[i]
            dict_t[temp] = dict_t.get(temp, 0)+1 
            
        hp =[]
        
        for key, value in dict_t.items():
            heapq.heappush(hp, (-value, key))
        
        result =[]
        
        count1 = 0 
        count2 = 0 
        while hp:
            count1, key1 = heapq.heappop(hp)
            if hp:
                count2, key2 = heapq.heappop(hp)
            
            if count1 < 0 and count2 < 0:
                result.append(key1)
                result.append(key2)
                count1 += 1 
                count2 += 1
            elif count1 <0 and count2 ==0:
                result.append(key1)
                count1 +=1 
                
            if count1 <0:
                heapq.heappush(hp, (count1, key1))
            if count2 <0:
                heapq.heappush(hp, (count2, key2))
        
        return result

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        # Construct max heap
        
        hash_map = dict()
        heap = list()
        result = [0] * len(barcodes)
        index = 0
        
        for bar_code in barcodes:
            hash_map[bar_code] = hash_map.get(bar_code,0)+1
        
        # {1 : 3, 2 : 3}
        print(hash_map)
        for code,freq in hash_map.items():
            heap.append((-freq, code))
        
        heapq.heapify(heap)
        
        while heap:
            freq, code = heapq.heappop(heap)
            freq = abs(freq)
            while freq > 0:
                if index >= len(barcodes):
                    index = 1
                result[index] = code
                index += 2
                freq -= 1
        return result