We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Distant Barcodes

Number: 1140

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of barcodes, rearrange them so that no two adjacent barcodes are equal. It is guaranteed that a valid rearrangement exists. For example, given [1,1,1,2,2,2], one possible output is [2,1,2,1,2,1].

Key Insights

  • Count the frequency of each barcode.
  • Sort the barcodes by their frequency in descending order.
  • Place the most frequent barcodes at alternate positions (starting with even indices) to ensure that no two identical barcodes are adjacent.
  • This greedy placement is valid because the problem guarantees an answer exists.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the frequency counts (n being the number of barcodes).
Space Complexity: O(n) for storing counts and the result array.

Solution

We first count how often each barcode appears. Next, we sort the barcodes based on the frequency count in descending order. This allows us to begin arranging with the most frequent barcodes first. We create an answer array and fill it by placing barcodes at even index positions (0, 2, 4, …). Once the even positions are filled, we resume from the first odd index. This method guarantees that two identical barcodes never become neighbors, since the most frequent ones are separated by at least one other barcode.

This approach uses:

  • A hash table (or map) for counting frequencies.
  • An array (or list) for storing and sorting the frequency counts.
  • A greedy strategy for placement.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java.

# Python solution with line-by-line comments
def rearrangeBarcodes(barcodes):
    from collections import Counter
    n = len(barcodes)
    # Count frequency of each barcode
    count = Counter(barcodes)
    # Sort barcodes by frequency in descending order
    sorted_barcodes = sorted(count.items(), key=lambda x: -x[1])
    # Initialize result array with zeros
    result = [0] * n
    index = 0
    # Place each barcode into the result array at alternate positions
    for barcode, freq in sorted_barcodes:
        for _ in range(freq):
            if index >= n:
                # When even positions are filled, start from first odd index
                index = 1
            result[index] = barcode
            index += 2
    return result

# Example testing
print(rearrangeBarcodes([1, 1, 1, 2, 2, 2]))
← Back to All Questions