Distant Barcodes - Video Solutions

Problem Overview: You receive an array of barcodes where each value represents a product type. Rearrange the array so that no two adjacent elements are equal. The challenge is handling high-frequency values without placing the same barcode next to itself.

Approach 1: Greedy Priority Queue (Max Heap) (Time: O(n log k), Space: O(k))

Count how often each barcode appears using a frequency map, then push the counts into a max heap. Always pick the two most frequent barcodes, place them next in the result, and decrease their counts before pushing them back if they still have remaining frequency. This greedy strategy works because using the most frequent elements first prevents them from clustering later in the array. The heap ensures efficient access to the highest remaining counts. This approach combines hash table counting with a priority queue, making it reliable when the number of distinct barcodes is small compared to the array size.

Approach 2: Index Filling with Frequency Sorting (Time: O(n), Space: O(k))

Instead of dynamically selecting elements, precompute the frequency of each barcode and sort them by count. Fill the result array by placing the most frequent value at even indices first (0, 2, 4, ...). Once even positions are filled, continue with odd indices (1, 3, 5, ...). Separating placements this way guarantees identical barcodes stay at least one position apart. The key insight: the most frequent element must be spaced out early before other values fill the gaps. With counting and direct index placement, the algorithm avoids heap operations and achieves near linear performance. This technique relies on simple array traversal and a greedy placement rule.

Recommended for interviews: The priority queue solution is the most intuitive and commonly discussed in interviews. It clearly demonstrates greedy reasoning and correct handling of frequency constraints. The index-filling approach is more optimal and elegant once you recognize the spacing trick, but it requires stronger intuition about frequency distribution. Explaining the heap-based method first shows solid problem-solving structure, then presenting the index strategy highlights deeper optimization skills.