Distant Barcodes: Frequency-Based Greedy Rearrangement

In a warehouse, there is a row of barcodes. The i-th barcode is barcodes[i]. Rearrange the barcodes so that no two adjacent barcodes are equal. It is guaranteed that an answer exists.

This is LeetCode 1054: Distant Barcodes, and it is a clean example of the frequency-based greedy rearrangement pattern. The same technique appears whenever you need to space out repeated elements so that identical values never sit next to each other.

Why this problem matters

Rearranging elements so no two adjacent ones are the same shows up in scheduling, task assignment, and resource allocation problems. The core challenge is always the same: the most frequent element is the bottleneck. If you can place the most frequent element safely, everything else falls into place.

This problem is a great entry point because the guarantee that an answer exists removes the need for impossibility checks. You can focus purely on the placement strategy. Once you have that down, you can extend it to problems like Reorganize String (LeetCode 767) and Task Scheduler (LeetCode 621), where you also need to handle the case when no valid arrangement exists.

The key insight

The element that appears most frequently is the hardest to place. If it appears k times, you need at least k non-adjacent slots to hold it. The trick is to fill even indices first (0, 2, 4, ...) with the most frequent elements, then fill odd indices (1, 3, 5, ...) with whatever remains.

Why does this work? Even indices are never adjacent to each other, and odd indices are never adjacent to each other. By placing the most frequent value across even indices first, you guarantee it never neighbors itself. Then you fill the odd indices with the remaining values. Since the answer is guaranteed to exist, the frequencies are always balanced enough for this greedy strategy to succeed.

The algorithm:

1. Count the frequency of each barcode value using a hash map.
2. Sort the values by frequency in descending order.
3. Place values into even indices first (0, 2, 4, ...), starting with the most frequent.
4. When even indices are full, continue placing into odd indices (1, 3, 5, ...).

The solution

from collections import Counter

def rearrange_barcodes(barcodes: list[int]) -> list[int]:
    count = Counter(barcodes)
    sorted_vals = sorted(count.keys(), key=lambda x: -count[x])

    result = [0] * len(barcodes)
    idx = 0

    for val in sorted_vals:
        for _ in range(count[val]):
            result[idx] = val
            idx += 2
            if idx >= len(barcodes):
                idx = 1

    return result

Let's walk through what each piece does.

The Counter builds a frequency map in O(n) time. For input [1, 1, 1, 1, 2, 2, 3], it produces {1: 4, 2: 2, 3: 1}.

The sorted call orders the unique values by descending frequency. This ensures the most frequent value gets placed first, which is critical. If you placed a less frequent value first, the most frequent one might end up squeezed into adjacent slots later.

The placement loop walks through even indices (0, 2, 4, 6, ...) and, once those run out, wraps around to odd indices (1, 3, 5, ...). The idx += 2 step skips one slot each time, and the if idx >= len(barcodes): idx = 1 line handles the transition from even to odd indices.

The result is a valid rearrangement where no two adjacent elements are the same.

Visual walkthrough

Let's trace through barcodes = [1, 1, 1, 1, 2, 2, 3] step by step. Watch how the most frequent value fills even indices first, then remaining values fill the gaps.

The final array [1, 2, 1, 2, 1, 3, 1] has no adjacent duplicates. Every pair of neighbors is different, which is exactly what the problem asks for.

Complexity analysis

Time is O(n log n) where n is the length of the barcodes array. Building the frequency map takes O(n). Sorting the unique values takes O(k log k) where k is the number of distinct values, and k is at most n. The placement loop is O(n). The sorting step dominates.

Space is O(n) for the result array and the frequency map. The sorted list of unique values uses O(k) additional space, which is bounded by O(n).

The building blocks

1. Frequency counting with a hash map

The pattern of counting occurrences to inform a greedy decision:

from collections import Counter

count = Counter(barcodes)

This is the foundation for any problem where the "most frequent" or "least frequent" element drives the strategy. You see it in Top K Frequent Elements, Reorganize String, Task Scheduler, and dozens of other problems. The frequency map tells you which element is the bottleneck, and the greedy algorithm uses that information to make optimal placement decisions.

2. Even-odd index interleaving

The pattern of filling alternating positions to guarantee separation:

idx = 0
for val in sorted_vals:
    for _ in range(count[val]):
        result[idx] = val
        idx += 2
        if idx >= len(barcodes):
            idx = 1

By jumping two indices at a time, you ensure that consecutive placements of the same value land in non-adjacent slots. The wrap-around from even to odd indices is the key detail. This same interleaving idea appears in problems like Sort Array By Parity and Wiggle Sort, where you need to separate elements into alternating positions based on some property.

3. Greedy "most constrained first" ordering

Sorting by frequency and placing the most frequent value first is an instance of the "most constrained first" heuristic. The value with the highest count has the fewest valid placements, so handling it first avoids dead ends. This principle shows up across greedy algorithms, from graph coloring to interval scheduling.

Edge cases

Before submitting, think through these scenarios:

• All elements the same: [1, 1, 1] has length 3 and value 1 appears 3 times. Since ceil(3/2) = 2, this exceeds the limit, but the problem guarantees an answer exists, so this input will not appear.
• Already valid: [1, 2, 1, 2] is already a valid arrangement. The algorithm still works and produces a valid (possibly different) output.
• Two elements alternating: [1, 2, 1, 2, 1] where one element appears one more time than the other. The most frequent fills even indices, the other fills odd indices.
• Single element: [5] has length 1. No adjacent pair exists, so any arrangement is valid. The algorithm returns [5].
• Large frequency gap: [1, 1, 1, 1, 1, 2, 3, 4, 5] where value 1 dominates. It fills indices 0, 2, 4, 6, 8 and the rest fill odd indices. This works because 5 occurrences fit in ceil(9/2) = 5 even slots.

From understanding to recall

You have seen how frequency counting drives the greedy placement: sort by count, fill even indices, then fill odd indices. The logic is simple and the code is short. But reproducing it under pressure is a different story.

The tricky part is not the concept. It is the details. Do you start idx at 0 or 1? Do you wrap to 1 when idx equals len(barcodes) or when it exceeds it? Do you sort ascending or descending? These small decisions are where mistakes happen in interviews, and they are exactly the kind of thing that spaced repetition drills into automatic recall.

Practice writing the frequency map, the sort-by-count step, and the even-odd placement loop from memory. After a few sessions, the pattern becomes muscle memory. You see "rearrange so no two adjacent are equal" in a problem statement, and the solution flows out without hesitation.

Related posts

• Reorganize String - The string version of this same pattern, rearranging characters so no two adjacent are equal using a max heap
• Task Scheduler - Greedy frequency counting to calculate minimum intervals, another problem where the most frequent element is the bottleneck
• Top K Frequent Elements - The frequency counting building block in isolation, foundational for problems like Distant Barcodes

CodeBricks breaks Distant Barcodes into its frequency counting and greedy placement building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy rearrangement problem shows up in your interview, you do not think about it. You just write it.