Distant Barcodes - Leetcode Solution

The Distant Barcodes problem on LeetCode asks us to rearrange a list of barcodes such that no two adjacent barcodes are the same. We are given an array of n integers, where each integer represents the number of times a particular barcode occurs in the list.

Our task is to return a new array with the rearranged barcodes. If there are multiple valid solutions, then we can return any of them.

To solve this problem, we can use a heap data structure to keep track of the counts of each barcode. We can iterate over the array, adding each barcode and its frequency to the heap.

After building the heap, we can start constructing the new array by repeatedly populating it with the two most frequent barcodes. We can do this by first getting the most frequent barcode, adding it to the new array, and then decreasing its frequency in the heap. We can then get the next most frequent barcode, add it to the new array, and decrease its frequency in the heap.

We can continue this process until we have added all the barcodes to the new array. If there are still barcodes remaining in the heap after we have added all the counts from the original array, we can continue adding them to the new array until the heap is empty.

Here's the Python code for the solution:

import heapq

def rearrangeBarcodes(barcodes):
    # build a dictionary of barcode counts
    barcode_counts = {}
    for barcode in barcodes:
        barcode_counts[barcode] = barcode_counts.get(barcode, 0) + 1
        
    # build a heap of barcode frequencies
    heap = []
    for barcode, count in barcode_counts.items():
        heapq.heappush(heap, (-count, barcode))
        
    # construct the new array by alternating the two most frequent barcodes
    new_barcodes = []
    while heap:
        count1, barcode1 = heapq.heappop(heap)
        new_barcodes.append(barcode1)
        count1 += 1
        
        if heap:
            count2, barcode2 = heapq.heappop(heap)
            new_barcodes.append(barcode2)
            count2 += 1
            
            if count2 < 0:
                heapq.heappush(heap, (count2, barcode2))
                
        if count1 < 0:
            heapq.heappush(heap, (count1, barcode1))
                
    return new_barcodes

The time complexity of this solution is O(n log n), where n is the length of the input array. This is because we use a heap, which has a log n insertion time complexity for each element. The space complexity is also O(n), since we use a dictionary to keep track of the barcode counts and a heap to keep track of the frequencies.

1