##### 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;
}