Skip to main content
Talentd

Distant Barcodes - Solution & Explanation

MediumArrayHash TableGreedySorting11 min readAsked at: Amazon, Meta
Practice this problem

Problem Statement

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 <= 10000
  • 1 <= 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.

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

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.

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.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), for storing results and map.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy PriorityQueue Approach

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.

Index Filling Approach

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), for storing results and map.

Counting + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 OrderingO(n)O(k)When you want the most optimal approach and can precompute frequencies before placement

Video Solution

LeetCode 1054. Distant Barcodes Explanation and Solution • happygirlzt • 1,680 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Distant Barcodes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays