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 <= 10000
  • 1 <= 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
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
barcodes = [1,1,1,2,2,2]

Output

x
+
cmd
[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
Copy The Code & Try With Live Editor

Input

x
+
cmd
barcodes = [1,1,1,2,2,2]

Output

x
+
cmd
[2,1,2,1,2,1]
Advertisements

Demonstration


Previous
#1053 Leetcode Previous Permutation With One Swap Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1061 Leetcode Lexicographically Smallest Equivalent String Solution in C, C++, Java, JavaScript, Python, C# Leetcode