Skip to content

1054. Distant Barcodes

Description

In a warehouse, there is a row of barcodes, where the ith barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= barcodes.length <= 10000
  • 1 <= barcodes[i] <= 10000

Solutions

Solution 1: Counting + Sorting

Thinking

Adjacent values must differ. When the mode appears at most \(\lceil n/2\rceil\) times a layout exists. Spreading high-frequency values onto even indices, then filling odd indices, keeps them apart.

Sort by frequency descending and value ascending so equal numbers stay together and frequent ones come first. Write the first half to even slots and the rest to odd slots.

The mode occupies every other even index and never sits next to itself.

First, we use a hash table or array \(cnt\) to count the number of occurrences of each number in the array \(barcodes\). Then, we sort the numbers in \(barcodes\) according to their occurrence times in \(cnt\) from large to small. If the occurrence times are the same, we sort them from small to large (to ensure the same numbers are adjacent).

Next, we create an answer array \(ans\) of length \(n\). We traverse the sorted \(barcodes\), and sequentially fill the elements into the even index positions \(0, 2, 4, \cdots\) of the answer array. Then, we fill the remaining elements into the odd index positions \(1, 3, 5, \cdots\) of the answer array.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(M)\). Where \(n\) and \(M\) are the length of the array \(barcodes\) and the maximum value in the array \(barcodes\), respectively.

1
2
3
4
5
6
7
8
9
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        cnt = Counter(barcodes)
        barcodes.sort(key=lambda x: (-cnt[x], x))
        n = len(barcodes)
        ans = [0] * len(barcodes)
        ans[::2] = barcodes[: (n + 1) // 2]
        ans[1::2] = barcodes[(n + 1) // 2 :]
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int n = barcodes.length;
        Integer[] t = new Integer[n];
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            t[i] = barcodes[i];
            mx = Math.max(mx, barcodes[i]);
        }
        int[] cnt = new int[mx + 1];
        for (int x : barcodes) {
            ++cnt[x];
        }
        Arrays.sort(t, (a, b) -> cnt[a] == cnt[b] ? a - b : cnt[b] - cnt[a]);
        int[] ans = new int[n];
        for (int k = 0, j = 0; k < 2; ++k) {
            for (int i = k; i < n; i += 2) {
                ans[i] = t[j++];
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int mx = *max_element(barcodes.begin(), barcodes.end());
        int cnt[mx + 1];
        memset(cnt, 0, sizeof(cnt));
        for (int x : barcodes) {
            ++cnt[x];
        }
        sort(barcodes.begin(), barcodes.end(), [&](int a, int b) {
            return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
        });
        int n = barcodes.size();
        vector<int> ans(n);
        for (int k = 0, j = 0; k < 2; ++k) {
            for (int i = k; i < n; i += 2) {
                ans[i] = barcodes[j++];
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func rearrangeBarcodes(barcodes []int) []int {
    mx := slices.Max(barcodes)
    cnt := make([]int, mx+1)
    for _, x := range barcodes {
        cnt[x]++
    }
    sort.Slice(barcodes, func(i, j int) bool {
        a, b := barcodes[i], barcodes[j]
        if cnt[a] == cnt[b] {
            return a < b
        }
        return cnt[a] > cnt[b]
    })
    n := len(barcodes)
    ans := make([]int, n)
    for k, j := 0, 0; k < 2; k++ {
        for i := k; i < n; i, j = i+2, j+1 {
            ans[i] = barcodes[j]
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function rearrangeBarcodes(barcodes: number[]): number[] {
    const mx = Math.max(...barcodes);
    const cnt = Array(mx + 1).fill(0);
    for (const x of barcodes) {
        ++cnt[x];
    }
    barcodes.sort((a, b) => (cnt[a] === cnt[b] ? a - b : cnt[b] - cnt[a]));
    const n = barcodes.length;
    const ans = Array(n);
    for (let k = 0, j = 0; k < 2; ++k) {
        for (let i = k; i < n; i += 2, ++j) {
            ans[i] = barcodes[j];
        }
    }
    return ans;
}

Comments