Distant Barcodes

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

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

---

This question is almost exactly the same as Reorganize String.

The only difference is in this problem, it is guaranteed that an answer exists so we won't have to check for invalid test cases.  That makes it a tiny bit easier for us.

This problem is also very similar to Task Scheduler and Sort Characters By Frequency.

With the given constraints, we are going to want to have a somewhat greedy approach.  Greedy approaches typically are to sort the given requirements and then continuously try to fit in either the cheapest or most expensive task at a time so that we can conserve the most resources.

In this case, the resources we are going to want to conserve are non-adjacent numbers.

What we can do is use a hashmap to count the frequency of each number, throw the frequency along with the number into a max heap, and from there, continuously pop and push each number/frequency until we have run out of our resources.  If there are even many numbers, the heap will be empty by the end of this.  If there are odd many numbers, then we will need to pop the last number from the heap.

---

Let's start by initializing our heap, output array, and seen hashmap.

        heap, seen = [], {}
        output = []

 

Next, we will go through each number in the array and count its frequency using our hashmap.

        for num in barcodes:

 

If the number isn't in the hashmap already, we will put it there with an initial count of negative one.

            if num not in seen:
                seen[num] = -1

 

If it is in the hashmap, we will decrement the count by one.

            else:
                seen[num] -= 1

 

To create a makeshift max-heap from a min-heap, we are making the heap input, the frequency, negative so that the largest frequency in the heap becomes the smallest when negative.

After we have counted frequencies, we will go through each num in the hashmap and push its frequency and itself into the heap.  It is important the frequency is first because the heap sorts on the first value inside the tuple.

        for num in seen:
            heapq.heappush(heap, (seen[num], num))

 

Next, we will make a loop that will run until the heap size is greater than one.

The size has to be greater than one because if it wasn't and we tried to pop two items off, we'd get an index out of bounds error.

        while len(heap) > 1:

 

Within each iteration, we will pop the most and second-most frequent numbers off of the heap then append them out of the output.

Popping two numbers at a time ensures that the most frequent element won't keep getting placed back next to itself.

            most_frequent, num_one = heapq.heappop(heap)
            less_frequent, num_two = heapq.heappop(heap)
            output.append(num_one)
            output.append(num_two)

 

Then, if the frequency of each number plus one is less than zero, then we still have an inventory of the number and will need to keep appending it to the output within a later iteration.

            if most_frequent + 1 < 0:
                heapq.heappush(heap, (most_frequent + 1, num_one))
            if less_frequent + 1 < 0:
                heapq.heappush(heap, (less_frequent + 1, num_two))    

 

Once we have broken from the loop, we will need to check if there is another number in the frequency.  If there is, we will pop it and append it to the output.

        if heap:
            frequncy, num = heapq.heappop(heap)
            output.append(num)

 

When we have reordered the barcodes, we will return them.

        return output

---