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

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;
    }
}