LeetCode 1054: Distant Barcodes

Problem Restatement

We are given an array of barcodes.

We need to rearrange the barcodes so that no two adjacent barcodes are equal.

It is guaranteed that a valid rearrangement always exists.

The official constraints state that 1 <= barcodes.length <= 10000 and 1 <= barcodes[i] <= 10000.

Input and Output

Function shape:

def rearrangeBarcodes(barcodes: list[int]) -> list[int]:
    ...

Key Insight

Always place the most frequent remaining barcode next (as long as it’s different from the last placed). Use a max heap.

If the most frequent barcode equals the last placed, temporarily use the second most frequent.

Algorithm

1. Count frequencies using a Counter.
2. Build a max heap of (-count, barcode).
3. While the heap is non-empty:
   • Pop the most frequent barcode.
   • If it equals the last placed barcode, pop the second most frequent and place it, then push the first back.
   • Otherwise place it.
4. Return the result.

Correctness

This is the “task scheduler” greedy approach. The most frequent element is placed as often as possible, always separated by other elements. Since a valid arrangement is guaranteed, the greedy always succeeds.

Edge Cases

• Duplicates usually matter; store counts when a set would lose necessary multiplicity.
• Update the frequency structure in the same order the invariant assumes.
• Check empty or one-element inputs if the problem allows them.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

import heapq
from collections import Counter

class Solution:
    def rearrangeBarcodes(self, barcodes: list[int]) -> list[int]:
        freq = Counter(barcodes)
        heap = [(-cnt, val) for val, cnt in freq.items()]
        heapq.heapify(heap)

        result = []
        while heap:
            cnt1, val1 = heapq.heappop(heap)
            if not result or result[-1] != val1:
                result.append(val1)
                if cnt1 + 1 < 0:
                    heapq.heappush(heap, (cnt1 + 1, val1))
            else:
                if not heap:
                    break
                cnt2, val2 = heapq.heappop(heap)
                result.append(val2)
                if cnt2 + 1 < 0:
                    heapq.heappush(heap, (cnt2 + 1, val2))
                heapq.heappush(heap, (cnt1, val1))

        return result

Testing

def run_tests():
    s = Solution()

    result = s.rearrangeBarcodes([1,1,1,2,2,2])
    for i in range(len(result) - 1):
        assert result[i] != result[i+1]

    result = s.rearrangeBarcodes([1,1,1,1,2,2,3,3])
    for i in range(len(result) - 1):
        assert result[i] != result[i+1]

    print("all tests passed")

run_tests()