Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  }
  

• 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;
      }
  };
  

• 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
  
  

• 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
  }
  

• 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;
  }
  
  

All Problems

All Solutions