Abstract / Summary

Arrange the barcodes so that no two identical ones are next to each other or separated by just one barcode.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 49% (100k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The rearrangeBarcodes method receives a list of integers representing barcodes and returns a new ordering where identical values never appear consecutively. The algorithm relies on frequency counting and a max-heap to always select the most abundant barcode that does not violate the adjacency rule.

Key Steps

Frequency Counting

The first phase builds a mapping from each barcode value to its occurrence count.

freq = defaultdict(int)
for b in barcodes:
    freq[b] += 1

Building a Max-Heap

Each distinct barcode together with its negative frequency is pushed onto a heap. The negative sign turns Python’s min-heap into a max-heap, allowing the most frequent element to be retrieved efficiently.

next = []
for f in freq:
    heappush(next, (-freq[f], f))   # negate => max instead of min-heap

Result Initialization

A placeholder element is placed at the start of the result list. This simplifies the adjacency check for the first real barcode.

result = [ None ]   # placeholder

Main Loop - Selecting Two Candidates

While at least two distinct barcodes remain in the heap, the two entries with the highest remaining counts are removed. The algorithm then decides which one can be placed next without repeating the previous value. If the most recent entry in result matches the first candidate, the second candidate is chosen; otherwise the first candidate is used. After placement, the selected candidate’s count is incremented (remembering that the stored count is negative) and any candidate whose count is still non-zero is pushed back onto the heap.

while len(next) >= 2:
    one = heappop(next)
    two = heappop(next)

    if result[-1] == one[1]:
        two = (two[0] + 1, two[1])   # remember: inverted sign
        result.append(two[1])
    else:
        one = (one[0] + 1, one[1])
        result.append(one[1])

    if one[0] != 0:
        heappush(next, one)
    if two[0] != 0:
        heappush(next, two)

Final Assembly

When the loop exits, at most one barcode type remains in the heap. The placeholder is removed, and the final remaining barcode is appended to complete the sequence.

return result[1:] + [ next[0][1] ]   # remove placeholder, add last barcode

Edge Cases Handled

When the input contains only a single barcode value, the frequency map holds one entry, the heap contains a single tuple, and the main loop is bypassed because the condition len(next) >= 2 is false. The final return statement appends that sole barcode after discarding the placeholder, yielding a correct one-element result.

If the most frequent barcode appears consecutively in the original list, the adjacency check result[-1] == one[1] forces the algorithm to select the second most frequent barcode for the next position, guaranteeing that no two identical values become neighbors.

The placeholder None ensures that the first real barcode can be compared without a special-case branch; the comparison simply fails because None never equals a valid barcode value.

When the heap reduces to a single entry with a remaining count greater than one, the loop has already exhausted all other types, and the final concatenation adds the remaining barcode exactly once. The earlier decrements guarantee that any additional occurrences would have been placed earlier, so the final sequence respects the adjacency rule.

Performance Optimizations

The use of a heap provides logarithmic-time selection and reinsertion of the most frequent elements, avoiding linear scans of the frequency map at each step. Storing frequencies as negative integers eliminates the need for a custom comparator, leveraging the built-in heap implementation directly. Updating counts in place (one[0] + 1) and immediately pushing back only non-zero entries keeps the heap size minimal, reducing the number of heap operations. The placeholder technique eliminates conditional branching for the first insertion, streamlining the main loop’s logic. Together, these choices produce an efficient rearrangement process that scales well with the number of distinct barcode values.

Imagine you have a big bucket full of colorful toy blocks, and some colors appear much more often than others. The goal is to line them all up in a row, but there is a rule that no two blocks of the same color can touch each other.

To solve this, the code first looks at all the blocks and counts how many there are of each color. It uses a special tool called a heap that is like a smart basket which always keeps the colors with the most blocks sitting right on top so they are easy to grab.

The code picks the two most frequent colors from the basket. It checks which one is safe to place next in the line so that no color sits right next to its twin. After placing a block, it puts the remaining blocks of that color back into the basket if there are still any left. By always picking from the most common colors, it ensures that even the busiest colors get spread out safely across the line. This continues over and over until every single block is placed in a perfect row where every neighbor has a different color.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	Go		TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	Garvit244		Python
	gouthampradhan				Java
	halfrost					Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM						C#
	trung-hn		Python
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
Garvit244	Python
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality