LeetCode Q 1054 - Distant Barcodes

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

Solution

Use a map to count the times of different barcodes appear.
Use a priority queue which stores pairs of barcode and its appearance times, and the priority queue is sorted according to appearance times in an DESC order.
While the pq is not empty, do the iteration. Each time we pull two elements from the pq, add these two barcode to the result array, then update their appearance times by minus one. If the appearance time is still bigger than zero, we offer this barcode pair to the pq again.

Code:

public int[] rearrangeBarcodes(int[] barcodes) {
  Map<Integer, Integer> map = new HashMap<>();
  
  for (int bc: barcodes) 
    map.put(bc, map.getOrDefault(bc, 0) + 1);

  Queue<int[]> pq = new PriorityQueue<>((a, b) -> (b[1] - a[1]));

  for (int key: map.keySet())
    pq.offer(new int[]{key, map.get(key)});

  int[] res = new int[barcodes.length]; int index = 0;

  while (!pq.isEmpty()) {
    
    List<Integer> temp = new ArrayList<>();
    
    for (int k = 0; k < 2 && !pq.isEmpty(); k++) {
      int[] curr = pq.poll();
      res[index++] = curr[0];
      map.put(curr[0], map.get(curr[0]) - 1);
      temp.add(curr[0]);
    }

    for (int n: temp) {
      if (map.get(n) > 0) 
        pq.offer(new int[]{n, map.get(n)});
    }

    if (pq.isEmpty()) break;
  }

  return res;
}

Reprint policy