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 <= barcodes.length <= 100001 <= barcodes[i] <= 10000
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; }