{x}
blog image

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

1054. Distant Barcodes

Problem Description

Rearrange a given array of barcodes barcodes such that no two adjacent barcodes are the same. The solution should be efficient and handle various input sizes.

Solution: Counting Sort and Alternating Placement

This solution uses a two-step approach:

  1. Counting and Sorting: We first count the occurrences of each barcode using a hash map (or an array if the barcode values are within a known range). Then, we sort the barcodes based on their frequency in descending order. If two barcodes have the same frequency, we sort them in ascending order to maintain stability.

  2. Alternating Placement: We create a result array ans of the same size as barcodes. We iterate through the sorted barcodes and place them alternately in even and odd indices of ans. This ensures that no two identical barcodes are adjacent.

Detailed Explanation with Code Examples

The code efficiently handles the problem by prioritizing the most frequent barcodes. By placing them in every other position, it maximizes the distance between identical barcodes. The sorting step uses a custom comparison function to handle frequency ties.

Time and Space Complexity Analysis

  • Time Complexity: O(N log N), dominated by the sorting step. Counting the frequencies is O(N).

  • Space Complexity: O(M), where M is the range of barcode values. In the worst case, this could be equal to N, but in many cases, it's much smaller than N.

Code Implementation (Python)

from collections import Counter
 
def rearrangeBarcodes(barcodes):
    """
    Rearranges barcodes such that no adjacent barcodes are the same.
 
    Args:
      barcodes: A list of integers representing the barcodes.
 
    Returns:
      A list of integers representing the rearranged barcodes.
    """
    count = Counter(barcodes)  # Count the frequency of each barcode
    sorted_barcodes = sorted(count.items(), key=lambda item: (-item[1], item[0])) #Sort by frequency (descending), then value (ascending)
 
    result = [0] * len(barcodes)
    even_index = 0
    odd_index = 1
    for barcode, frequency in sorted_barcodes:
        for _ in range(frequency):
            if even_index < len(barcodes):
                result[even_index] = barcode
                even_index += 2
            else:
                result[odd_index] = barcode
                odd_index += 2
    return result
 
#Example usage
barcodes = [1,1,1,2,2,2]
print(rearrangeBarcodes(barcodes)) # Output: [2, 1, 2, 1, 2, 1] (or a similar valid arrangement)
 
barcodes = [1,1,1,1,2,2,3,3]
print(rearrangeBarcodes(barcodes)) #Output: [1, 3, 1, 3, 1, 2, 1, 2] (or a similar valid arrangement)

Code Implementation (Java)

import java.util.*;
import java.util.Map.Entry;
 
class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int barcode : barcodes) {
            count.put(barcode, count.getOrDefault(barcode, 0) + 1);
        }
 
        List<Entry<Integer, Integer>> sortedBarcodes = new ArrayList<>(count.entrySet());
        sortedBarcodes.sort((a, b) -> b.getValue() - a.getValue()); //Sort by frequency (descending)
 
        int[] result = new int[barcodes.length];
        int evenIndex = 0;
        int oddIndex = 1;
        for (Entry<Integer, Integer> entry : sortedBarcodes) {
            int barcode = entry.getKey();
            int frequency = entry.getValue();
            for (int i = 0; i < frequency; i++) {
                if (evenIndex < barcodes.length) {
                    result[evenIndex] = barcode;
                    evenIndex += 2;
                } else {
                    result[oddIndex] = barcode;
                    oddIndex += 2;
                }
            }
        }
        return result;
    }
}

The Java and other language implementations follow a similar logic, adapting the data structures and syntax accordingly. The core algorithm remains the same: counting, sorting, and alternating placement.