# 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

| Item | Meaning |
|---|---|
| Input | Array `barcodes` |
| Output | Rearranged array with no two adjacent equal elements |

Function shape:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log k)` | `n` placements, each `O(log k)` heap operations |
| Space | `O(n + k)` | Result array and heap |

## 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

```python
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

```python
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()
```

| Test | Verification | Why |
|---|---|---|
| `[1,1,1,2,2,2]` | No adjacent equal | Valid rearrangement exists |
| `[1,1,1,1,2,2,3,3]` | No adjacent equal | Most frequent placed greedily |