Distant Barcodes solution and explanation
9 more videos on this problem
LeetCode 1054. Distant Barcodes Explanation and Solutionhappygirlzt · 6:51 · 1K views
Leetcode 1054 | Distant BarcodesTech Traversal · 14:07 · 1K views
LeetCode 1054. Distant Barcodes 中文解释 Chinese Versionhappygirlzt · 7:44 · 277 views
【每日一题】1054. Distant Barcodes, 7/30/2020Huifeng Guan · 18:55 · 274 views
1054. Distant Barcodes (Leetcode Medium)Programming Live with Larry · 10:53 · 245 views
Leetcode 1054. Distant Barcodes (greedy)LetsCode · 4:04 · 98 views
米开：LeetCode 1054. Distant BarcodesM.C米开朗基罗 · 4:05 · 96 views
猩猩的乐园 LeetCode 1054 Distant Barcodes猩猩的乐园 · 6:39 · 76 views
LeetCode 1054: Distant BarcodesAlitaCode · 30:40 · 9 views
LeetCode 1054: Distant BarcodesAlitaCode · 31:24 · 8 views
The problem
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] <= 10000
Approach overview
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.
Approach 1: Greedy PriorityQueue Approach
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.
from collections import Counter
import heapq
def rearrangeBarcodes(barcodes):
counter = Counter(barcodes)
maxHeap = [(-count, num) for num, count in counter.items()]
heapq.heapify(maxHeap)
prev_count, prev_num = 0, 0
result = []
while maxHeap:
count, num = heapq.heappop(maxHeap)
result.append(num)
if prev_count < 0:
heapq.heappush(maxHeap, (prev_count, prev_num))
prev_count, prev_num = count + 1, num
return result
barcodes = [1,1,1,2,2,2]
print(rearrangeBarcodes(barcodes)) # Output: [2, 1, 2, 1, 2, 1]import java.util.*;
public class BarcodeRearranger {
public int[] rearrangeBarcodes(int[] barcodes) {
Map<Integer, Integer> count = new HashMap<>();
for (int b : barcodes)
count.put(b, count.getOrDefault(b, 0) + 1);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (int key : count.keySet())
pq.add(new int[]{key, count.get(key)});
int[] result = new int[barcodes.length];
int index = 0;
while (!pq.isEmpty()) {
int[] first = pq.poll();
if (index > 0 && result[index - 1] == first[0]) {
int[] second = pq.poll();
result[index++] = second[0];
second[1]--;
if (second[1] > 0)
pq.add(second);
pq.add(first);
} else {
result[index++] = first[0];
first[1]--;
if (first[1] > 0)
pq.add(first);
}
}
return result;
}
public static void main(String[] args) {
BarcodeRearranger rearranger = new BarcodeRearranger();
int[] barcodes = {1, 1, 1, 2, 2, 2};
System.out.println(Arrays.toString(rearranger.rearrangeBarcodes(barcodes))); // Output: [2, 1, 2, 1, 2, 1]
}
}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.
Approach 2: Index Filling Approach
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.
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
unordered_map<int, int> count;
for (int b : barcodes)
++count[b];
sort(barcodes.begin(), barcodes.end(), [&](int a, int b) {
return count[a] == count[b] ? a < b : count[a] > count[b];
});
vector<int> result(barcodes.size());
int idx = 0;
for (int b : barcodes) {
result[idx] = b;
idx += 2;
if (idx >= barcodes.size())
idx = 1;
}
return result;
}
#include <iostream>
int main() {
vector<int> barcodes = {1,1,1,2,2,2};
vector<int> result = rearrangeBarcodes(barcodes);
for (int b : result) cout << b << " "; // Output: 2 1 2 1 2 1
return 0;
}function rearrangeBarcodes(barcodes) {
const count = {};
for (const b of barcodes) {
count[b] = count[b] + 1 || 1;
}
barcodes.sort((a, b) => count[b] - count[a] || a - b);
const result = Array(barcodes.length);
let index = 0;
for (const b of barcodes) {
result[index] = b;
index += 2;
if (index >= barcodes.length) {
index = 1;
}
}
return result;
}
let barcodes = [1, 1, 1, 2, 2, 2];
console.log(rearrangeBarcodes(barcodes)); // Output: [2, 1, 2, 1, 2, 1]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.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), for storing results and map.
Approach 3: Counting + Sorting
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.
function rearrangeBarcodes(barcodes: number[]): number[] {
const mx = Math.max(...barcodes);
const cnt = Array(mx + 1).fill(0);
for (const x of barcodes) {
++cnt[x];
}
barcodes.sort((a, b) => (cnt[a] === cnt[b] ? a - b : cnt[b] - cnt[a]));
const n = barcodes.length;
const ans = Array(n);
for (let k = 0, j = 0; k < 2; ++k) {
for (let i = k; i < n; i += 2, ++j) {
ans[i] = barcodes[j];
}
}
return ans;
}func rearrangeBarcodes(barcodes []int) []int {
mx := slices.Max(barcodes)
cnt := make([]int, mx+1)
for _, x := range barcodes {
cnt[x]++
}
sort.Slice(barcodes, func(i, j int) bool {
a, b := barcodes[i], barcodes[j]
if cnt[a] == cnt[b] {
return a < b
}
return cnt[a] > cnt[b]
})
n := len(barcodes)
ans := make([]int, n)
for k, j := 0, 0; k < 2; k++ {
for i := k; i < n; i, j = i+2, j+1 {
ans[i] = barcodes[j]
}
}
return ans
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Distant Barcodes easy or hard?
Distant Barcodes is considered a Medium-level problem. The difficulty comes from recognizing that the most frequent element must be distributed early to avoid adjacency conflicts. Once you identify the greedy strategy using a heap or index spacing, the implementation becomes straightforward.
Distant Barcodes Python/Java solution
Python and Java implementations typically use a priority queue to store pairs of (frequency, value). The algorithm repeatedly pops the two most frequent entries, appends them to the result, decreases their counts, and pushes them back if more remain. Both languages provide efficient heap libraries that support this approach.
How to solve Distant Barcodes in O(n)?
Compute the frequency of each barcode and sort or track the most frequent value. Place that value in even indices of the result array first (0, 2, 4, ...). After even slots are filled, continue placing remaining values in odd positions. This spacing guarantees no adjacent duplicates and runs in linear time with counting.
What is the best approach for Distant Barcodes?
The greedy max heap approach is the most commonly used solution. Count frequencies, push them into a max heap, and repeatedly place the two most frequent barcodes next to each other. This guarantees adjacent elements differ while maintaining valid counts. The time complexity is O(n log k) where k is the number of distinct barcodes.
Is Distant Barcodes asked at Google/Amazon/Meta?
Rearrangement and frequency-based greedy problems similar to Distant Barcodes frequently appear in interviews at companies like Amazon, Google, and Meta. Variants include reorganizing strings or scheduling tasks with cooldown constraints. Interviewers use these problems to evaluate greedy reasoning and data structure selection.
What data structure is used in Distant Barcodes?
The main data structures are a hash map for counting frequencies and a max heap (priority queue) for selecting the most frequent barcode each step. The optimized approach replaces the heap with direct array index placement after computing frequencies.
What is the time complexity of Distant Barcodes?
The heap-based greedy solution runs in O(n log k) time because each placement involves heap operations on the k distinct barcode values. The index-filling counting approach can achieve O(n) time by directly placing the most frequent elements at even indices and filling remaining positions afterward.