Code Implementation

from collections import Counter
import heapq

class Solution:
    def rearrangeBarcodes(self, barcodes):
        count = Counter(barcodes)
        # Max heap: (-freq, barcode)
        heap = [(-freq, num) for num, freq in count.items()]
        heapq.heapify(heap)
        res = []
        prev_freq, prev_num = 0, None

        while heap:
            freq, num = heapq.heappop(heap)
            res.append(num)
            # If previous barcode still has count, push it back
            if prev_freq < 0:
                heapq.heappush(heap, (prev_freq, prev_num))
            # Prepare for next round
            prev_freq, prev_num = freq + 1, num  # decrease freq

        return res
      

#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int, int> count;
        for (int b : barcodes) count[b]++;
        // Max heap: pair<freq, barcode>
        priority_queue<pair<int, int>> heap;
        for (auto &p : count) heap.push({p.second, p.first});
        vector<int> res;
        pair<int, int> prev = {0, 0};
        while (!heap.empty()) {
            auto cur = heap.top(); heap.pop();
            res.push_back(cur.second);
            if (prev.first > 0) heap.push(prev);
            cur.first--;
            prev = cur;
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int b : barcodes) count.put(b, count.getOrDefault(b, 0) + 1);
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (Map.Entry<Integer, Integer> entry : count.entrySet())
            heap.add(new int[]{entry.getValue(), entry.getKey()});
        int n = barcodes.length;
        int[] res = new int[n];
        int idx = 0;
        int[] prev = new int[]{0, 0};
        while (!heap.isEmpty()) {
            int[] cur = heap.poll();
            res[idx++] = cur[1];
            if (prev[0] > 0) heap.add(prev);
            cur[0]--;
            prev = cur;
        }
        return res;
    }
}
      

/**
 * @param {number[]} barcodes
 * @return {number[]}
 */
var rearrangeBarcodes = function(barcodes) {
    const count = {};
    for (let b of barcodes) count[b] = (count[b] || 0) + 1;
    // Max heap using array and sort
    let heap = Object.entries(count).map(([num, freq]) => [parseInt(freq), parseInt(num)]);
    heap.sort((a, b) => b[0] - a[0]);
    const res = [];
    let prev = [0, 0];
    while (heap.length) {
        let cur = heap.shift();
        res.push(cur[1]);
        if (prev[0] > 0) heap.push(prev);
        cur[0]--;
        prev = cur;
        heap.sort((a, b) => b[0] - a[0]);
    }
    return res;
};
      

Problem Description

You are given an array of integers called barcodes, where each integer represents a barcode type. Your task is to rearrange the elements in barcodes such that no two adjacent elements are the same. You must use every element exactly once, and it is guaranteed that at least one valid arrangement exists for the given input.

• Input: barcodes (an array of integers)
• Output: Return a rearranged array where no two consecutive elements are equal.
• Constraints: You must use all elements and cannot skip or duplicate any. Only one valid solution needs to be returned.

Thought Process

At first glance, the problem might look like a permutation or backtracking problem, where we try all possible arrangements and check if any two adjacent elements are the same. However, this would be very inefficient, especially for large inputs.

By observing the problem, we realize that the main challenge is to distribute the most frequent barcodes as evenly as possible to avoid having them adjacent. If we always place the most frequent barcode next to a different one, we can avoid adjacent duplicates.

This leads us to consider using a greedy approach: always pick the barcode with the highest remaining count, but never place the same barcode as the previous one.

To efficiently get the most frequent barcode at each step, we can use a max-heap (priority queue). Each time, we pick the most frequent barcode that is different from the last placed one. If we just used a regular queue or array, finding the max each time would be slow.

Solution Approach

The solution uses a greedy algorithm with a max-heap (priority queue) to always place the most frequent available barcode, ensuring no two adjacent elements are the same.

1. Count Frequencies:
   • Use a hash map (dictionary) to count how many times each barcode appears.
2. Build a Max-Heap:
   • Insert each barcode and its frequency as a pair into a max-heap (priority queue). This allows us to always pick the barcode with the highest remaining count efficiently.
3. Greedy Placement:
   • At each step, pop the most frequent barcode from the heap.
   • If this barcode is the same as the one we just placed, pick the next most frequent one instead (if available).
   • After placing a barcode, decrease its frequency and, if it still has remaining occurrences, push it back into the heap for future use.
   • To avoid consecutive duplicates, keep track of the previously used barcode and only re-insert it into the heap after using a different barcode.
4. Continue Until Done:
   • Repeat the process until all barcodes have been placed.

This approach guarantees that no two adjacent barcodes are the same, and it uses every element exactly once.

Example Walkthrough

Let's consider the input barcodes = [1,1,1,2,2,3].

1. Count Frequencies:
   • 1 appears 3 times
   • 2 appears 2 times
   • 3 appears 1 time
2. Build Heap:
   • Heap contains: [(3,1), (2,2), (1,3)]
3. First Iteration:
   • Pop (3,1): Place 1
   • Decrease count: (2,1) is stored for later
4. Second Iteration:
   • Pop (2,2): Place 2
   • Push back (2,1) since it's not the same as last placed
   • Heap now: [(2,1), (1,3), (1,2)]
5. Third Iteration:
   • Pop (2,1): Place 1
   • Decrease count: (1,1) saved
   • Push back (1,2)
6. Continue:
   • Next: Pop (1,3): Place 3
   • Push back (1,1)
   • Then: Pop (1,1): Place 1
   • Push back (1,2)
   • Finally: Pop (1,2): Place 2
7. Result:
   • One possible output: [1,2,1,3,1,2]
   • No two adjacent elements are the same, and all barcodes are used.

Time and Space Complexity

• Brute-force Approach:
  • Would try all possible permutations, which is O(n!) time and O(n) space for each permutation. Not feasible for large n.
• Optimized Heap Approach:
  • Counting frequencies: O(n)
  • Building the heap: O(k), where k is the number of unique barcodes (k ≤ n)
  • Each heap operation (push/pop) is O(log k), and we do this n times, so total heap operations: O(n log k)
  • Space: O(n) for the result plus O(k) for the heap and frequency map
• Overall: O(n log k) time and O(n) space

Summary

The Distant Barcodes problem is efficiently solved by using a greedy approach with a max-heap. By always choosing the most frequent barcode that is not the same as the previous one, we avoid adjacent duplicates and ensure all elements are used. This method is both elegant and efficient, avoiding the need for brute-force permutation checks and leveraging priority queues for optimal selection at each step.