Distant Barcodes

Description

In a warehouse, there is a row of barcodes, where the i-th 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: [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

Example 2:

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

 

Note:

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

 

Solution(javascript)

const rearrangeBarcodes = (barcodes = []) => {
  const map = barcodes.reduce((acc, code) => {
    acc[code] = (acc[code] || 0) + 1
    return acc
  }, {})
  const keys = Object.keys(map).sort((a, b) => map[a] - map[b])
  const result = []
  let key = keys.pop()
  for (let i = 0; i < barcodes.length; i += 2) {
    if (map[key] <= 0) {
      key = keys.pop()
    }
    map[key] -= 1
    result[i] = Number(key)
  }
  for (let i = 1; i < barcodes.length; i += 2) {
    if (map[key] <= 0) {
      key = keys.pop()
    }
    map[key] -= 1
    result[i] = Number(key)
  }

  return result
}