LeetCode 1054 · Greedy

Distant Barcodes, explained with a picture

Seating guests so no matching shirts sit together.

Greedy
▶ Watch it step by step

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 out

LeetCode 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.