# Distant Barcodes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/distant-barcodes)
Canonical: https://scaleengineer.com/dsa/problems/distant-barcodes
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
---
## Problem
In a warehouse, there is a row of barcodes, where the `ith` barcode is `barcodes[i]`.

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.

**Example 1:**

**Input:** barcodes = [1,1,1,2,2,2]
**Output:** [2,1,2,1,2,1]

**Example 2:**

**Input:** barcodes = [1,1,1,1,2,2,3,3]
**Output:** [1,3,1,3,1,2,1,2]

**Constraints:**

* `1 <= barcodes.length <= 10000`
* `1 <= barcodes[i] <= 10000`

# Approaches
## Greedy Approach with Max Heap
This approach uses a greedy strategy. At each step, we want to place the barcode that is currently most frequent, but we must ensure it's not the same as the one just placed. A max heap (implemented with a `PriorityQueue`) is the ideal data structure to efficiently retrieve the most frequent barcode at any given time.
**Time:** O(N log K), where N is the number of barcodes and K is the number of unique barcodes. Counting frequencies is O(N). Building the heap of K unique items is O(K log K). The main loop runs N times, and each iteration involves heap operations (poll and add) which take O(log K) time, leading to a total of O(N log K). · **Space:** O(K), where K is the number of unique barcodes. This is for the frequency map and the priority queue. If the output array is considered, the space complexity is O(N).
**Pros:** It's a classic and intuitive greedy algorithm for this type of rearrangement problem.; Correctly handles all cases, as guaranteed by the problem statement.
**Cons:** Slightly less efficient than the sorting-based approach due to the overhead of O(N) heap operations.; The logic of holding back the previously used element can be slightly more complex to reason about compared to a direct placement strategy.
### Explanation
The core idea is to always pick the most frequent available barcode to place next in our result array. However, we can't pick the same barcode twice in a row. To handle this, we can use a max heap to store barcodes ordered by frequency.

1.  **Count Frequencies:** First, we iterate through the input `barcodes` and count the occurrences of each number, storing them in a hash map.
2.  **Build Max Heap:** We then populate a max heap with all the unique barcodes, using their frequency as the priority. The element with the highest frequency will be at the top.
3.  **Construct Result:** We build the result array by repeatedly extracting the most frequent element from the heap. After placing a barcode, we can't immediately put it back into the heap if its count is still positive. Instead, we hold onto it, extract the *next* most frequent barcode, place it, and only then do we add the previous barcode back to the heap. This ensures that two identical barcodes are separated by at least one other barcode.

```java
class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        if (barcodes.length <= 1) {
            return barcodes;
        }
        Map<Integer, Integer> counts = new HashMap<>();
        for (int b : barcodes) {
            counts.put(b, counts.getOrDefault(b, 0) + 1);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            pq.add(new int[]{entry.getValue(), entry.getKey()});
        }

        int[] result = new int[barcodes.length];
        int index = 0;
        int[] prev = null;

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            result[index++] = current[1];
            current[0]--;

            if (prev != null && prev[0] > 0) {
                pq.add(prev);
            }
            prev = current;
        }
        return result;
    }
}
```
### Algorithm
- Create a `HashMap<Integer, Integer>` to store the frequency of each barcode.
- Iterate through the input `barcodes` array and populate the frequency map.
- Create a `PriorityQueue<int[]>` to act as a max heap. The priority will be based on the frequency. The `int[]` will store `{frequency, barcode}`.
- Populate the max heap with all unique barcodes and their counts from the frequency map.
- Create a result array `int[] result` of the same size as `barcodes`.
- Initialize an index `i = 0` for the result array.
- To ensure no two adjacent elements are the same, we keep track of the previously placed element. Initialize a variable `int[] prev = null`.
- Loop while the max heap is not empty:
  - Poll the element with the highest frequency, `current`, from the heap.
  - Place its barcode value into `result[i++]`.
  - Decrement the frequency of `current`.
  - If `prev` is not null and its frequency is still greater than 0, add `prev` back to the heap. This one-turn delay prevents the same element from being picked consecutively.
  - Update `prev` to be `current` for the next iteration.
- Return the `result` array.

## Greedy with Sorting and Interleaved Placement
This approach is also greedy but employs a more direct placement strategy. Instead of using a heap to decide which barcode to place next, we sort all barcodes by their frequency once. Then, we fill the result array by placing elements in an interleaved fashion—first at all even indices (0, 2, 4, ...), and then at all odd indices (1, 3, 5, ...). This simple yet effective strategy guarantees a valid arrangement.
**Time:** O(N + K log K), where N is the number of barcodes and K is the number of unique barcodes. Counting frequencies is O(N). Sorting the K unique keys takes O(K log K). Finally, filling the result array is a single pass, taking O(N). The total is dominated by O(N + K log K). · **Space:** O(K), where K is the number of unique barcodes. This space is used for the frequency map and the list of keys for sorting. The O(N) space for the output array is standard.
**Pros:** Generally more efficient than the heap-based approach, as it avoids O(N) heap operations.; The placement logic is very simple and deterministic.; The time complexity O(N + K log K) is better than O(N log K) when K is much smaller than N.
**Cons:** Requires sorting, which has a non-linear time complexity component (K log K).
### Explanation
The key insight is that the most frequent element is the most constrained. By placing it first and giving it maximum separation, we make the problem easier for the remaining elements. The maximum possible separation is achieved by placing elements at every other position.

1.  **Count and Sort:** We begin by counting the frequency of each barcode. Then, we create a list of the unique barcodes and sort them in descending order of frequency.
2.  **Interleaved Placement:** We create an empty result array. We then iterate through our frequency-sorted list of barcodes. For each barcode, we place it as many times as it appears. We start placing at index 0, then 2, 4, and so on. Once we've used all the even-indexed slots, we wrap around and start filling the odd-indexed slots (1, 3, 5, ...).

This works because the problem guarantees a solution exists, which implies the count of the most frequent element is at most `(N + 1) / 2`. This is exactly the number of even-indexed positions in an array of length N, so the most frequent element will fit perfectly into these slots without wrapping around to an adjacent odd slot.

```java
class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int n = barcodes.length;
        if (n <= 1) {
            return barcodes;
        }
        Map<Integer, Integer> counts = new HashMap<>();
        for (int b : barcodes) {
            counts.put(b, counts.getOrDefault(b, 0) + 1);
        }

        List<Integer> sortedKeys = new ArrayList<>(counts.keySet());
        // Sort keys by frequency in descending order
        sortedKeys.sort((a, b) -> counts.get(b) - counts.get(a));

        int[] result = new int[n];
        int index = 0;
        for (int key : sortedKeys) {
            int count = counts.get(key);
            for (int i = 0; i < count; i++) {
                result[index] = key;
                index += 2;
                if (index >= n) {
                    index = 1;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- First, count the frequency of each barcode using a hash map.
- Create a list of the unique barcode numbers.
- Sort this list of unique barcodes in descending order based on their frequencies.
- Create a result array `int[] result` of size N.
- Initialize a placement index `idx = 0`.
- Iterate through the sorted list of unique barcodes:
  - For each `barcode`, retrieve its `count`.
  - Place this `barcode` into the `result` array `count` times.
  - After each placement at `result[idx]`, update the index by `idx += 2`.
  - If the index `idx` goes past the end of the array, reset it to `1` to start filling the odd positions.
- This two-pass filling strategy (first even indices, then odd indices) ensures that the most frequent elements are maximally spaced out.
- Return the `result` array.

# Solutions
### Java

```java
class Solution {
public
  int[] rearrangeBarcodes(int[] barcodes) {
    int n = barcodes.length;
    Integer[] t = new Integer[n];
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      t[i] = barcodes[i];
      mx = Math.max(mx, barcodes[i]);
    }
    int[] cnt = new int[mx + 1];
    for (int x : barcodes) {
      ++cnt[x];
    }
    Arrays.sort(t, (a, b)->cnt[a] == cnt[b] ? a - b : cnt[b] - cnt[a]);
    int[] ans = new int[n];
    for (int k = 0, j = 0; k < 2; ++k) {
      for (int i = k; i < n; i += 2) {
        ans[i] = t[j++];
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> rearrangeBarcodes(vector<int> &barcodes) {
    int mx = *max_element(barcodes.begin(), barcodes.end());
    int cnt[mx + 1];
    memset(cnt, 0, sizeof(cnt));
    for (int x : barcodes) {
      ++cnt[x];
    }
    sort(barcodes.begin(), barcodes.end(), [&](int a, int b) {
      return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
    });
    int n = barcodes.size();
    vector<int> ans(n);
    for (int k = 0, j = 0; k < 2; ++k) {
      for (int i = k; i < n; i += 2) {
        ans[i] = barcodes[j++];
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]: cnt = Counter(barcodes) barcodes . sort(key=lambda x: (- cnt[x], x)) n = len(barcodes) ans = [0] * len(barcodes) ans[:: 2] = barcodes[: (n + 1) // 2] ans[1:: 2] = barcodes[(n + 1) // 2:] return ans

```