Problem Explanation

Given a list of barcodes, the problem requires rearranging the barcodes in such a way that no two adjacent barcodes are same. Here, we are assuming that the barcodes are represented by numbers. For example, if we have barcodes like [1,1,1,2,2,2], we have to rearrange them in such a way that no two adjacent barcodes are same. One possible answer would be [2,1,2,1,2,1].

Please note that multiple correct outputs might exist for the same input.

To solve this problem, we keep track of the frequency of each barcode in the list and then rearrange them in such a way that barcodes with higher frequency are distributed more evenly across the list.

Solution Approach

The solution to this problem uses a greedy approach. Firstly, it calculates the count of each barcode using an array where the index represents the barcode and the value at that index represents the count of that barcode.

Then it finds the barcode with the maximum count. This is done using the max_element function which returns an iterator pointing to the element with maximum value in the given range.

Once we have the barcode with maximum count, we start filling the resultant array in a way that these barcodes are as apart as possible. We start from index 0 and then place the maximum count barcode at every other index (i.e., at 2, 4, 6, and so on till the end of the array or till the count of that barcode is exhausted).

Then we fill the remaining positions in the array with the other barcodes. We start from the first barcode and place the barcodes at every other index in the array starting from 1 (i.e., at 1, 3, 5, 7, and so on).

Here is the pseudocode of the above approach:

1
2
3count ← Initialize array of size 10001 with all values as 0
4i ← 0
5
6for each barcode in the barcodes:
7    increment the count of barcode
8
9maxIt ← iterator pointing to barcode with maximum count
10maxNum ← barcode with maximum count
11
12fill the array ans with maxNum at every other index starting from 0 till end of array or count of maxNum is exhausted
13
14Then fill the array ans with remaining barcodes at every other index starting from 1 till end of array

This way, the barcodes with higher frequency are distributed more evenly across the array. In other words, the barcodes will be more distant from each other and thus, no two adjacent barcodes will be same.

Example

Let's illustrate this with an example.

Consider the barcodes [1,1,1,2,2,3,3].

Here, the barcode 1 appears three times, barcode 2 appears two times, barcode 3 appears two times.

So, the count array will look like this (other indexes are ignored as they are not present in the barcodes):

[..., 0, 3, 2, 2, ..., 0]

Here, the barcode with maximum count is 1. So, we start filling the array with barcode 1 at every other index starting from 0:

[1 _ 1 _ 1 _ _]

Then we fill the array with remaining barcodes:

[1,2,1,2,1,3,3]

The barcodes are now rearranged such that no two adjacent barcodes are same.

Solution

C++ Solution

1
2c++
3class Solution {
4public:
5    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
6        vector<int> ans(barcodes.size());
7        vector<int> count(10001);
8        int i = 0;
9        
10        for (const int b : barcodes);
11            ++count[b];
12        
13        auto maxIt = max_element(begin(count), end(count));
14        int maxNum = maxIt - begin(count);
15
16        auto fillAns = [&](int num) {
17            while (count[num]-- > 0) {
18                ans[i] = num;
19                i = i + 2 < barcodes.size() ? i + 2 : 1;
20            }
21        };
22        
23        fillAns(maxNum);
24        for (int num = 1; num < 10001; ++num);
25            fillAns(num);
26        
27        return ans;
28    }
29};

Here, lambda function fillAns is used to fill the array ans with the barcode num at every other index starting from current index i or 1 till the count of that barcode is exhausted.

The solution starts filling the array ans with the barcode with the highest count and then fills it with all other barcodes.

Python Solution

In Python, we can use the Counter function from the collections module to get the count of each barcode. Then we can use the heap data structure (with items as occurrences-barcodes pairs) to ensure that the barcode with highest frequency is always at the front of the heap. We can then pop the barcode from the heap, add to the result and push it back with reduced count (if count is still more than zero).

Here is the Python solution:

1
2python
3import heapq
4from collections import Counter
5
6class Solution:
7    def rearrangeBarcodes(self, barcodes):
8        barcode_count = Counter(barcodes)
9        heap = [(-freq, barcode) for barcode, freq in barcode_count.items()]
10        heapq.heapify(heap)
11
12        res = []
13        while len(heap) > 1:
14            freq1, barcode1 = heapq.heappop(heap)
15            freq2, barcode2 = heapq.heappop(heap)
16            res.extend([barcode1, barcode2])
17
18            if freq1 + 1: heapq.heappush(heap, (freq1+1, barcode1))
19            if freq2 + 1: heapq.heappush(heap, (freq2+1, barcode2))
20
21        return res + [heapq.heappop(heap)[1]] if heap else res

JavaScript Solution

1
2javascript
3var rearrangeBarcodes = function(barcodes) {
4    let res = Array(barcodes.length);
5    let count = Array(10001).fill(0);
6    let idx = 0;
7
8    for (let barcode of barcodes)
9        ++count[barcode];
10
11    for(let i = 1; i < 10001; ++i)
12        if(count[i] > count[idx])
13            idx = i;
14
15    let p = 0;
16    while(count[idx]-- > 0){
17        res[p] = idx;
18        p += 2;
19        if(p >= barcodes.length) p = 1;
20    }
21
22    for(let i = 1; i < 10001; ++i)
23        while(count[i]-- > 0) {
24            res[p] = i;
25            p += 2;
26            if(p >= barcodes.length) p = 1;
27        }
28
29    return res;
30};

Java Solution

In Java, we can use a PriorityQueue with a custom comparator to ensure that the barcode with highest frequency is always at the front of the PriorityQueue. We can then poll the barcode from the PriorityQueue, add to the result and offer it back with reduced count (if count is still more than zero).

Here is the Java solution:

1
2java
3class Solution {
4    public int[] rearrangeBarcodes(int[] barcodes) {
5        Map<Integer, Integer> count = new HashMap<>();
6        for (int barcode : barcodes) {
7            count.put(barcode, count.getOrDefault(barcode, 0) + 1);
8        }
9
10        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
11        for (int barcode : count.keySet()) {
12            pq.offer(new int[]{barcode, count.get(barcode)});
13        }
14
15        int[] res = new int[barcodes.length];
16        int idx = 0;
17        while (!pq.isEmpty()) {
18            int[] curr = pq.poll();
19            for (int i = 0; i < curr[1]; i++) {
20                if (idx >= barcodes.length) idx = 1;
21                res[idx] = curr[0];
22                idx += 2;
23            }
24        }
25
26        return res;
27    }
28}

In all solutions, the time complexity is O(n log n) where n is the length of the barcodes, as we need to sort the barcodes by their frequency. The space complexity is O(n) as we need to store the count of each barcode.