Algorithm
Problem Name: 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 <= 100001 <= barcodes[i] <= 10000
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const rearrangeBarcodes = function(barcodes) {
const hash = {}
let maxFreq = 0, max = 0
for(const e of barcodes) {
if(hash[e] == null) hash[e] = 0
hash[e]++
if(hash[e] > maxFreq) {
maxFreq = hash[e]
max = e
}
}
const n = barcodes.length
const entries = Object.entries(hash)
const res = Array(n)
let idx = 0
while(maxFreq) {
res[idx] = max
idx += 2
maxFreq--
}
for(let [v, f] of entries) {
if(+v === max) continue
while(f) {
if(idx >= n) idx = 1
res[idx] = +v
idx += 2
f--
}
}
return res
};
Input
barcodes = [1,1,1,2,2,2]
Output
[2,1,2,1,2,1]
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
cnt = collections.Counter(barcodes).most_common()[::-1]
ref = [val for val, t in cnt for _ in range(t)]
for i in range(0, len(barcodes), 2):
barcodes[i] = ref.pop()
for i in range(1, len(barcodes), 2):
barcodes[i] = ref.pop()
return barcodes
Input
barcodes = [1,1,1,2,2,2]
Output
[2,1,2,1,2,1]