The problem
Rearrange barcodes so that no two neighbours are equal (a valid answer always exists).
Input: [1, 1, 1, 2, 2, 3] Output: [1, 2, 1, 2, 1, 3]
Picture it
Picture seating guests in matching shirts so no two neighbours match. Seat the most common colour first in every other seat (0, 2, 4, …), then keep filling even seats and wrap around to the odd seats.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Sort by frequency and fill even indices, then odd. O(n log n).
Python solution
def rearrange_barcodes(codes):
count = Counter(codes)
order = sorted(codes, key=lambda x: (-count[x], x)) # most common first
out = [None] * len(codes)
i = 0
for x in order:
out[i] = x
i += 2 # every other seat
if i >= len(codes):
i = 1 # then fill the gaps
return outLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.