Skip to content

1054. Distant Barcodes 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    vector<int> ans(barcodes.size());
    vector<int> count(10001);
    int i = 0;  // ans' index

    for (const int b : barcodes)
      ++count[b];

    const auto maxIt = ranges::max_element(count);
    const int maxNum = maxIt - count.begin();

    auto fillAns = [&](int num) {
      while (count[num]-- > 0) {
        ans[i] = num;
        i = i + 2 < barcodes.size() ? i + 2 : 1;
      }
    };

    fillAns(maxNum);
    for (int num = 1; num < 10001; ++num)
      fillAns(num);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public int[] rearrangeBarcodes(int[] barcodes) {
    int[] ans = new int[barcodes.length];
    int[] count = new int[10001];
    int maxCount = 0;
    int maxNum = 0;

    for (final int b : barcodes)
      ++count[b];

    for (int i = 1; i < 10001; ++i)
      if (count[i] > maxCount) {
        maxCount = count[i];
        maxNum = i;
      }

    fillAns(ans, count, maxNum, barcodes.length);
    for (int num = 1; num < 10001; ++num)
      fillAns(ans, count, num, barcodes.length);

    return ans;
  }

  private int i = 0; // ans' index

  private void fillAns(int[] ans, int[] count, int num, int n) {
    while (count[num]-- > 0) {
      ans[i] = num;
      i = i + 2 < n ? i + 2 : 1;
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def rearrangeBarcodes(self, barcodes: list[int]) -> list[int]:
    ans = [0] * len(barcodes)
    count = collections.Counter(barcodes)
    i = 0  # ans' index
    maxNum = max(count, key=count.get)

    def fillAns(num: int) -> None:
      nonlocal i
      while count[num]:
        ans[i] = num
        i = i + 2 if i + 2 < len(barcodes) else 1
        count[num] -= 1

    fillAns(maxNum)
    for num in count.keys():
      fillAns(num)

    return ans