Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

1054. Distant Barcodes

Time: $O(n)$

Space: $O(n)$

			


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 = max_element(begin(count), end(count));
    const int maxNum = maxIt - begin(count);

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




			


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




			


class Solution:
  def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
    ans = [0] * len(barcodes)
    count = 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