Distant Barcodes

medium greedy sorting counting

Problem

In a warehouse, there is a row of barcodes given as an array. Rearrange the barcodes so that no two adjacent barcodes are equal. Return any valid arrangement; the input guarantees that at least one exists.

Inputbarcodes = [1, 1, 1, 1, 2, 2, 3]

Output[1, 2, 1, 2, 1, 3, 1]

The most frequent value 1 lands on every even index, so no two equal values touch.

barcodes (comma-separated)

def rearrange_barcodes(barcodes):
    from collections import Counter
    freq = Counter(barcodes)
    order = sorted(barcodes, key=lambda x: (-freq[x], x))
    n = len(barcodes)
    res = [0] * n
    pos = 0
    for x in order:
        res[pos] = x
        pos += 2
        if pos >= n:
            pos = 1
    return res

function rearrangeBarcodes(barcodes) {
  const freq = new Map();
  for (const x of barcodes) freq.set(x, (freq.get(x) || 0) + 1);
  const order = [...barcodes].sort((a, b) =>
    freq.get(b) - freq.get(a) || a - b);
  const n = barcodes.length;
  const res = new Array(n);
  let pos = 0;
  for (const x of order) {
    res[pos] = x;
    pos += 2;
    if (pos >= n) pos = 1;
  }
  return res;
}

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : barcodes) freq.merge(x, 1, Integer::sum);
        Integer[] order = new Integer[barcodes.length];
        for (int i = 0; i < barcodes.length; i++) order[i] = barcodes[i];
        Arrays.sort(order, (a, b) ->
            freq.get(b).equals(freq.get(a)) ? a - b : freq.get(b) - freq.get(a));
        int n = barcodes.length, pos = 0;
        int[] res = new int[n];
        for (int x : order) {
            res[pos] = x;
            pos += 2;
            if (pos >= n) pos = 1;
        }
        return res;
    }
}

vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    unordered_map<int, int> freq;
    for (int x : barcodes) freq[x]++;
    vector<int> order = barcodes;
    sort(order.begin(), order.end(), [&](int a, int b) {
        if (freq[a] != freq[b]) return freq[a] > freq[b];
        return a < b;
    });
    int n = barcodes.size(), pos = 0;
    vector<int> res(n);
    for (int x : order) {
        res[pos] = x;
        pos += 2;
        if (pos >= n) pos = 1;
    }
    return res;
}

Explanation

To stop equal barcodes from touching, the dangerous values are the most frequent ones, so we deal with them first. The trick is to fill an answer array at even slots first, then odd slots, placing the most common value before any other.

We count each value with a Counter and build order: all barcodes sorted by descending frequency (ties broken by value). This groups copies of the same value together, with the biggest group at the front.

We then drop them into res at positions 0, 2, 4, ..., and once we run off the end we continue at 1, 3, 5, .... Because consecutive same-value items land two apart (or wrap to the odd slots), no two identical values ever sit next to each other.

This works because a valid arrangement is guaranteed to exist, which means no value appears more than half-plus-a-bit of the time; spacing the biggest group across the even slots first leaves room for everything else.

Example: barcodes=[1,1,1,1,2,2,3]. The fours 1s go to slots 0,2,4,6, then 2,2,3 fill slots 1,3,5, producing something like [1,2,1,2,1,3,1] with no neighbors equal.

Time: O(n log n) Space: O(n)