In a warehouse, there is a row of barcodes, where the ith 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: barcodes = [1,1,1,2,2,2] Output: [2,1,2,1,2,1]
Example 2:
Input: barcodes = [1,1,1,1,2,2,3,3] Output: [1,3,1,3,1,2,1,2]
Constraints:
1 <= barcodes.length <= 100001 <= barcodes[i] <= 10000Problem 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.
This approach leverages a priority queue to ensure that the most frequent barcodes are spaced apart. By sorting the barcodes by frequency, we can fill in the positions, alternating between the most available barcodes to handle the adjacency constraint efficiently.
This Python implementation uses the collections.Counter to count the frequencies of each barcode type. A max heap (priority queue) is utilized to always extract the barcode with the highest frequency first, and we keep track of the last processed barcode to avoid immediate reuse.
Time Complexity: O(n log k), where n is the number of barcodes and k is the number of unique barcodes.
Space Complexity: O(n + k), for the heap and Counter storage.
In this approach, the barcodes are first sorted by frequency, then they are placed alternately in even and odd indices within the result array. This method efficiently arranges the barcodes such that no two adjacent barcodes are equal.
This C++ implementation first counts the occurrences of each barcode type. It sorts the barcodes based on frequency and then arranges them by filling even indices first, followed by odd indices. This ensures an alternating pattern that prevents adjacent duplicates.
C++
JavaScript
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), for storing results and map.
First, we use a hash table or array cnt to count the number of occurrences of each number in the array barcodes. Then, we sort the numbers in barcodes according to their occurrence times in cnt from large to small. If the occurrence times are the same, we sort them from small to large (to ensure the same numbers are adjacent).
Next, we create an answer array ans of length n. We traverse the sorted barcodes, and sequentially fill the elements into the even index positions 0, 2, 4, cdots of the answer array. Then, we fill the remaining elements into the odd index positions 1, 3, 5, cdots of the answer array.
The time complexity is O(n times log n), and the space complexity is O(M). Where n and M are the length of the array barcodes and the maximum value in the array barcodes, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy PriorityQueue Approach | Time Complexity: O(n log k), where n is the number of barcodes and k is the number of unique barcodes. |
| Index Filling Approach | Time Complexity: O(n log n), due to sorting. |
| Counting + Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Priority Queue (Max Heap) | O(n log k) | O(k) | General solution when using frequency counts and dynamic selection of the most frequent elements |
| Index Filling with Frequency Ordering | O(n) | O(k) | When you want the most optimal approach and can precompute frequencies before placement |
LeetCode 1054. Distant Barcodes Explanation and Solution • happygirlzt • 1,669 views views
Watch 9 more video solutions →Practice Distant Barcodes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor