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.

Description Hints 1 Solution Video 6:51

1054. Distant Barcodes

Medium49.3% acceptance2 companies

In a warehouse, there is a row of barcodes, where the i^th 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 <= 10000
1 <= barcodes[i] <= 10000

Asked at 2 companies

Amazon Meta

Topics

Hints open one at a time

Hint 1

We want to always choose the most common or second most common element to write next. What data structure allows us to query this effectively?

6:51

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,1,1,2,2,2]

Input

[1,1,1,1,2,2,3,3]

Your code is saved on this device.Solution