Welcome to Subscribe On Youtube

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;
    }
};
  • 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;
        }
    }
    
    ############
    
    class Solution {
        public int[] rearrangeBarcodes(int[] barcodes) {
            Map<Integer, Integer> cnt = new HashMap<>();
            for (int v : barcodes) {
                cnt.put(v, cnt.getOrDefault(v, 0) + 1);
            }
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
            for (var e : cnt.entrySet()) {
                pq.offer(new int[] {e.getKey(), e.getValue()});
            }
            Deque<int[]> q = new ArrayDeque<>();
            int[] ans = new int[barcodes.length];
            int i = 0;
            while (!pq.isEmpty()) {
                var p = pq.poll();
                ans[i++] = p[0];
                p[1]--;
                q.offer(p);
                while (q.size() > 1) {
                    p = q.pollFirst();
                    if (p[1] > 0) {
                        pq.offer(p);
                    }
                }
            }
            return ans;
        }
    }
    
  • // 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;
        }
    };
    
  • class Solution:
        def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
            cnt = Counter(barcodes)
            h = [(-v, k) for k, v in cnt.items()]
            heapify(h)
            q = deque()
            ans = []
            while h:
                v, k = heappop(h)
                ans.append(k)
                q.append((v + 1, k))
                while len(q) > 1:
                    p = q.popleft()
                    if p[0]:
                        heappush(h, p)
            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
            
    
    
  • func rearrangeBarcodes(barcodes []int) []int {
    	cnt := map[int]int{}
    	for _, v := range barcodes {
    		cnt[v]++
    	}
    	pq := hp{}
    	for k, v := range cnt {
    		heap.Push(&pq, pair{v, k})
    	}
    	ans := []int{}
    	q := []pair{}
    	for len(pq) > 0 {
    		p := heap.Pop(&pq).(pair)
    		v, k := p.v, p.k
    		ans = append(ans, k)
    		q = append(q, pair{v - 1, k})
    		for len(q) > 1 {
    			p = q[0]
    			q = q[1:]
    			if p.v > 0 {
    				heap.Push(&pq, p)
    			}
    		}
    	}
    	return ans
    }
    
    type pair struct {
    	v int
    	k int
    }
    
    type hp []pair
    
    func (h hp) Len() int { return len(h) }
    func (h hp) Less(i, j int) bool {
    	a, b := h[i], h[j]
    	return a.v > b.v
    }
    func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
    func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
    func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
    
  • function rearrangeBarcodes(barcodes: number[]): number[] {
        const mx = Math.max(...barcodes);
        const cnt = Array(mx + 1).fill(0);
        for (const x of barcodes) {
            ++cnt[x];
        }
        barcodes.sort((a, b) => (cnt[a] === cnt[b] ? a - b : cnt[b] - cnt[a]));
        const n = barcodes.length;
        const ans = Array(n);
        for (let k = 0, j = 0; k < 2; ++k) {
            for (let i = k; i < n; i += 2, ++j) {
                ans[i] = barcodes[j];
            }
        }
        return ans;
    }
    
    

All Problems

All Solutions