MediumArrayHash TableGreedySortingHeap (Priority Queue)Counting

Distant Barcodes

1 approach, code in every language

In a warehouse, a row of barcodes is given as an integer array where barcodes[i] is the i-th barcode value. Rearrange the barcodes so that no two adjacent barcodes are equal.

A valid answer is guaranteed to exist. Return any arrangement that satisfies the rule.

Example 1

Input: barcodes = [1,1,1,2,2,2]

Output: [2,1,2,1,2,1]

Alternating the two values keeps equal barcodes from touching.

Example 2

Input: barcodes = [1,1,1,1,2,2,3,3]

Output: [1,3,1,3,1,2,1,2]

The value 1 is most frequent, so it takes alternating slots first, then the rest fill in without repeats.

Constraints

1 <= barcodes.length <= 10^4
1 <= barcodes[i] <= 10^4
A valid answer always exists.

Sort by Count then Interleave

Order values by descending frequency and drop them into even indices first, then odd indices.

Loading animation…

Intuition

Because a valid layout is guaranteed, the most frequent value can appear at most ceil(n / 2) times, so it fits neatly into alternating slots. If we lay out values starting with the most frequent one at indices 0, 2, 4, ... and wrap to 1, 3, 5, ... after passing the end, every copy of a given value lands exactly two positions apart. That two-position gap means equal values can never become neighbours. Sorting the distinct values by descending count ensures the hardest-to-place value is committed to its safe alternating slots before anything else competes for space.

Algorithm walkthrough

1Count how many times each barcode value appears.
2Collect the distinct values and sort them by descending frequency.
3Create a result array and start an index at 0, walking the even positions.
4For each value in sorted order, place all of its copies at the current index, stepping by two.
5When the index runs past the end, reset it to 1 to continue through the odd positions.
6Return the filled array; equal values are always two indices apart, so none are adjacent.

Implementation

from typing import List
from collections import Counter

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counts = Counter(barcodes)
        n = len(barcodes)
        order = sorted(counts.keys(), key=lambda x: -counts[x])
        result = [0] * n
        idx = 0
        for val in order:
            for _ in range(counts[val]):
                if idx >= n:
                    idx = 1
                result[idx] = val
                idx += 2
        return result

Time

O(N + U log U)

Space

O(N)

Counting the N barcodes is linear, and sorting the U distinct values costs O(U log U). The result array and count map use O(N) extra space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free