<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 {
public:
    // Solution 0: T: O(N), S: O(N) just consider maxTimes val, rest's order doesn't matter
    // cnt times, assign most freq to each alternative even pos first then odd pos
    vector<int> rearrangeBarcodes(vector<int>& b) { // pos in b, even pos first
        int pos = 0, maxTime = 0, maxVal = 0, m[10001] = {}; // <val, times>
        for(int x : b) 
            if(++m[x]>maxTime) maxTime = m[x], maxVal = x;
        for(int i=0; i<10001; ++i){ // i from 0, to insert maxVal first; Since val [1-10000]
            int k = !i ? maxVal : i; // !i put maxVal first;
            for(; m[k]-->0; pos+=2){
                if(pos>=b.size()) pos = 1; // set from even to odd pos
                b[pos] = k;
            }
        }
        return b;
    }
    
    // // Solution 1: T: O(N), S: O(N) just consider maxTimes val, rest's order doesn't matter
    // // cnt times, assign most freq to each alternative even pos first then odd pos
    // vector<int> rearrangeBarcodes(vector<int>& b) { // pos in b, even pos first
    //     int pos = 0, maxTime = 0, maxVal = 0;
    //     unordered_map<int,int> m; // <val, times>
    //     for(int x : b) 
    //         if(++m[x]>maxTime) maxTime = m[x], maxVal = x;
    //     for(int i=0; i<maxTime; ++i, pos+=2){ // insert maxVal with maxTime first
    //         if(pos>=b.size()) pos = 1; // set from even to odd pos
    //         b[pos] = maxVal;
    //     }
    //     m.erase(maxVal); // m[maxVal] = 0;
    //     for(const auto&[val, times] : m)
    //         for(int i=0; i<times; ++i, pos+=2){
    //             if(pos>=b.size()) pos = 1; // set from even to odd pos
    //             b[pos] = val;
    //         }
    //     return b;
    // }
    
    // // Solution 2: T: O(NlgN), S: O(N)
    // // cnt times, assign most freq to each alternative pos (even pos first then odd pos)
    // vector<int> rearrangeBarcodes(vector<int>& b, int pos = 0) { // pos in b, even pos first
    //     unordered_map<int,int> m; // <val, times>
    //     for(int x : b) ++m[x];
    //     set<pair<int,int>, greater<pair<int,int> > > st; // maxTimes <times, val>
    //     for(const auto&[val, times] : m) st.emplace(times, val);
    //     for(const auto&[times, val] : st)
    //         for(int i=0; i<times; ++i, pos+=2){
    //             if(pos>=b.size()) pos = 1; // set from even to odd pos
    //             b[pos] = val;
    //         }
    //     return b;
    // }
    
    // // https://leetcode.com/problems/reorganize-string/
    // // Solution 3: similar as Reorganize String T: O(N^2), S: O(N)
    // vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    //     unordered_map<int,int> m, valid; // m <val, times>, valid <val, nextValidPos>
    //     for(int x : barcodes) ++m[x];
    //     for(int i=0, k=1; i<barcodes.size(); ++i){
    //         int c = 0, maxVal = 0;
    //         for(const auto&[ch, cnt] : m)
    //             if(maxVal<cnt && i>=valid[ch]) maxVal = cnt, c = ch;
    //         // if(!c) return {};  // no valid result
    //         --m[c];
    //         valid[c] = i+k+1;
    //         barcodes[i] = c;
    //     }
    //     return barcodes;
    // }
    
    // vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    //     int m[10001] = {}, valid[10001] = {}; // m <val, times>, valid <val, nextValidPos>
    //     for(int x : barcodes) ++m[x];
    //     for(int i=0, k=1; i<barcodes.size(); ++i){
    //         int c = 0, maxVal = 0;
    //         for(int ch=0; ch<10001; ++ch)
    //             if(maxVal<m[ch] && i>=valid[ch]) maxVal = m[ch], c = ch;
    //         // if(!c) return {}; // optional no valid result
    //         --m[c];
    //         valid[c] = i+k+1;
    //         barcodes[i] = c;
    //     }
    //     return barcodes;
    // }
};
39300