## 1054. Distant Barcodes

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`

## Rust Solution

``````struct Solution;
use std::collections::HashMap;

impl Solution {
fn rearrange_barcodes(barcodes: Vec<i32>) -> Vec<i32> {
let n = barcodes.len();
if n == 1 {
return barcodes;
}
let mut hm: HashMap<i32, usize> = HashMap::new();
let mut max: (usize, i32) = (0, 0);
for barcode in barcodes {
let count = hm.entry(barcode).or_default();
*count += 1;
if *count > max.0 {
max = (*count, barcode);
}
}
let mut stack = vec![];
for (k, v) in hm {
if k != max.1 {
for _ in 0..v {
stack.push(k);
}
}
}
for _ in 0..max.0 {
stack.push(max.1);
}
let mut res = vec![0; n];
let m = if n % 2 == 0 { n / 2 } else { (n + 1) / 2 };
for i in 0..m {
res[i * 2] = stack.pop().unwrap();
}
let mut i = 1;
while let Some(top) = stack.pop() {
res[i] = top;
i += 2;
}
res
}
}

#[test]
fn test() {
let barcodes = vec![1, 1, 1, 2, 2, 2];
let res = vec![1, 2, 1, 2, 1, 2];
assert_eq!(Solution::rearrange_barcodes(barcodes), res);
let barcodes = vec![1, 1, 2];
let res = vec![1, 2, 1];
assert_eq!(Solution::rearrange_barcodes(barcodes), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.