<p>In a warehouse, there is a row of barcodes, where the <code>i<sup>th</sup></code> barcode is <code>barcodes[i]</code>.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> barcodes = [1,1,1,2,2,2]
<strong>Output:</strong> [2,1,2,1,2,1]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> barcodes = [1,1,1,1,2,2,3,3]
<strong>Output:</strong> [1,3,1,3,1,2,1,2]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= barcodes.length &lt;= 10000</code></li>
	<li><code>1 &lt;= barcodes[i] &lt;= 10000</code></li>
</ul>

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        """
        Observation: the most frequent element must be able to be placed on the even indices of the array
        """

        freq_map = defaultdict(int)
        max_freq = 0
        for code in barcodes:
            freq_map[code] += 1
            if freq_map[code] > freq_map[max_freq]:
                max_freq = code
        
        res = [0] * len(barcodes)
        i = 0
        for v in range(freq_map[max_freq]):
            res[i] = max_freq
            i += 2
        
        del freq_map[max_freq]

        # Once we've filled up the array with the max frequency element, it doesn't matter what we put in between
        for k, v in freq_map.items():
            for _ in range(v):
                if i >= len(barcodes):
                    i = 1
                res[i] = k
                i += 2

        return res

        
18700