Distant Barcodes

Intuition

Because a valid layout is guaranteed, the most frequent value can appear at most ceil(n / 2) times, so it fits neatly into alternating slots. If we lay out values starting with the most frequent one at indices 0, 2, 4, ... and wrap to 1, 3, 5, ... after passing the end, every copy of a given value lands exactly two positions apart. That two-position gap means equal values can never become neighbours. Sorting the distinct values by descending count ensures the hardest-to-place value is committed to its safe alternating slots before anything else competes for space.

Algorithm walkthrough

1. 1Count how many times each barcode value appears.
2. 2Collect the distinct values and sort them by descending frequency.
3. 3Create a result array and start an index at 0, walking the even positions.
4. 4For each value in sorted order, place all of its copies at the current index, stepping by two.
5. 5When the index runs past the end, reset it to 1 to continue through the odd positions.
6. 6Return the filled array; equal values are always two indices apart, so none are adjacent.

Implementation

from typing import List
from collections import Counter

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counts = Counter(barcodes)
        n = len(barcodes)
        order = sorted(counts.keys(), key=lambda x: -counts[x])
        result = [0] * n
        idx = 0
        for val in order:
            for _ in range(counts[val]):
                if idx >= n:
                    idx = 1
                result[idx] = val
                idx += 2
        return result