> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/distant-barcodes.md).

# Distant Barcodes

In a warehouse, there is a row of barcodes, where the `i`-th 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: [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]
```

**Example 2:**

```
Input: [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,2,1,2,1]
```

**Note:**

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

```java
class Solution {
    // It is guaranteed an answer exists.
    public int[] rearrangeBarcodes(int[] barcodes) {
        // map of barcode -> frequency
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = 0;
        // O(n)
        for (int barcode : barcodes) {
            map.put(barcode, map.getOrDefault(barcode, 0) + 1);
            max = Math.max(map.get(barcode), max);
        }
        // List of frequency -> barcodes
        List<Integer>[] freq = new ArrayList[max + 1];
        // frequency is index
        // O(n)
        for (int barcode : map.keySet()) {
            if (freq[map.get(barcode)] == null)
                freq[map.get(barcode)] = new ArrayList<>();
            freq[map.get(barcode)].add(barcode);
        }
        int[] ans = new int[barcodes.length];
        int index = 0;
        // O(2n) at worst case, because number of elements
        // in total frquency ArrayLists will be 'n'
        for (int i = max; i >= 1; i--) {
            if (freq[i] != null) {
                for (int barcode : freq[i]) {
                    for (int count = i; count > 0; count--) {
                        if (index >= ans.length)
                            index = 1;
                        ans[index] = barcode;
                        index += 2;
                    }
                }
            }
        }
        return ans;
    }
}
```