Formatted question description: https://leetcode.ca/all/1054.html

1054. Distant Barcodes (Medium)

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. 1 <= barcodes.length <= 10000
  2. 1 <= barcodes[i] <= 10000
 

Related Topics:
Heap, Sort

Solution 1. Greedy + Heap

// OJ: https://leetcode.com/problems/distant-barcodes/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& A) {
        unordered_map<int, int> cnt;
        for (int n : A) cnt[n]++;
        auto cmp = [&](int a, int b) { return cnt[a] < cnt[b]; };
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
        for (auto &p : cnt) q.push(p.first);
        int prev = 0;
        vector<int> ans;
        while (q.size()) {
            int n = q.top();
            q.pop();
            ans.push_back(n);
            if (prev) q.push(prev);
            if (--cnt[n]) prev = n;
            else prev = 0;
        }
        return ans;
    }
};

Solution 2. Interleaving Placement

// OJ: https://leetcode.com/problems/distant-barcodes/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& A) {
        unordered_map<int, int> cnt;
        set<pair<int, int>> s;
        for (int n : A) cnt[n]++;
        for (auto &p : cnt) s.emplace(p.second, p.first);
        int j = 0, N = A.size();
        vector<int> ans(N);
        for (auto it = s.rbegin(); it != s.rend(); ++it) {
            for (int c = 0; c < it->first; ++c, j += 2) {
                if (j >= N) j = 1;
                ans[j] = it->second;
            }
        }
        return ans;
    }
};

Solution 3.

Just fill the most frequent number first. The others can be filled irrespective of their frequency.

// OJ: https://leetcode.com/problems/distant-barcodes/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& A) {
        short cnt[10001] = {}, maxCnt = 0, num = 0, j = 0;
        for (int n : A) {
            maxCnt = max(maxCnt, ++cnt[n]);
            if (maxCnt == cnt[n]) num = n;
        }
        for (int i = 0; i <= 10000; ++i) {
            int n = i ? i : num;
            while (cnt[n]-- > 0) {
                A[j] = n;
                j = (j + 2) % A.size();
                if (j == 0) j = 1;
            }
        }
        return A;
    }
};

Java

  • class Solution {
        public int[] rearrangeBarcodes(int[] barcodes) {
            int[] counts = new int[10001];
            int maxCount = 0;
            int length = barcodes.length;
            for (int i = 0; i < length; i++) {
                int num = barcodes[i];
                counts[num]++;
                maxCount = Math.max(maxCount, counts[num]);
            }
            int[] rearrangeBarcodes = new int[length];
            int evenIndex = 0, oddIndex = 1;
            int maxPossible = length / 2 + 1;
            for (int i = 1; i <= 10000; i++) {
                while (counts[i] > 0 && counts[i] < maxPossible && oddIndex < length) {
                    rearrangeBarcodes[oddIndex] = i;
                    counts[i]--;
                    oddIndex += 2;
                }
                while (counts[i] > 0) {
                    rearrangeBarcodes[evenIndex] = i;
                    counts[i]--;
                    evenIndex += 2;
                }
            }
            return rearrangeBarcodes;
        }
    }
    
  • // OJ: https://leetcode.com/problems/distant-barcodes/
    // Time: O(NlogN)
    // Space: O(N)
    class Solution {
    public:
        vector<int> rearrangeBarcodes(vector<int>& A) {
            unordered_map<int, int> cnt;
            for (int n : A) cnt[n]++;
            auto cmp = [&](int a, int b) { return cnt[a] < cnt[b]; };
            priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
            for (auto &p : cnt) q.push(p.first);
            int prev = 0;
            vector<int> ans;
            while (q.size()) {
                int n = q.top();
                q.pop();
                ans.push_back(n);
                if (prev) q.push(prev);
                if (--cnt[n]) prev = n;
                else prev = 0;
            }
            return ans;
        }
    };
    
  • # 1054. Distant Barcodes
    # https://leetcode.com/problems/distant-barcodes/
    
    class Solution:
        def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
            counter = collections.Counter(barcodes)
            count = sorted([(counter[x], x) for x in counter], key = lambda x : -x[0])
            i = 0
            n = len(barcodes)
            res = [None] * n
            
            for cnt,key in count:
                for _ in range(cnt):
                    if i >= n: i = 1
                    res[i] = key
                    i += 2
            
            return res
            
    
    

All Problems

All Solutions