1054. Distant Barcodes


Problem Description

In this problem, we are given a list of integers representing barcodes. The goal is to rearrange the barcodes so that no two consecutive barcodes are the same. Fortunately, the problem statement assures us that there is always a valid rearrangement that meets this condition. We need to find and return one such valid arrangement.

Intuition

To solve this problem, we should first think about the constraints: no two adjacent barcodes can be equal. A natural approach to prevent adjacent occurrences of the same barcode would be to arrange the barcodes in such a way that the most frequent ones are as spread out as possible. This way, we reduce the chance that they will end up next to each other.

We can do this by:

  1. Counting the frequency of each barcode using Counter from the collections module, which gives us a dictionary-like object mapping each unique barcode to its count of appearances.
  2. Sorting the barcodes based on their frequency. However, simply sorting them in non-ascending order of their frequency is not enough, as we need to make sure that once they are arranged, the condition is met. It's a good idea to also sort them by their value to have a deterministic result if frequencies are equal.
  3. Once sorted, the array is split into two: the first half will occupy even positions, and the second half will fill the odd positions in the result array. We do this because even-indexed places followed by odd-indexed ones are naturally never adjacent, which is ideal for our requirement to space out the frequent barcodes.
  4. Create a new array for the answer, filling it first with the elements at even indices and then at odd indices.

By doing this, we ensure that the most frequent elements are spread across half the array length, minimizing any chance they are adjacent to each other. The end result is a carefully structured sequence that satisfies the given condition of the problem.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Solution Approach

The solution approach follows a series of logical steps that strategically utilize Python language features and its standard library functionalities. Here's a breakdown of how the solution is implemented:

  1. Counting Frequencies: We use the Counter class from the collections module to count the frequency of each barcode in the given list. The Counter object, named cnt, will give us a mapping of each unique barcode value to its count of appearances.

    1cnt = Counter(barcodes)
  2. Sorting Based on Frequency: We then sort the original list of barcodes using the sort method, applying a custom sorting key. The sorting key is a lambda function that sorts primarily by frequency (-cnt[x], where negative is used for descending order) and secondarily by the barcode value (x) in natural ascending order in case of frequency ties.

    1barcodes.sort(key=lambda x: (-cnt[x], x))
  3. Structuring The Answer: With the barcodes now sorted, half of the array (rounded up in the case of odd-length arrays) can be placed at even indices and the remaining half at odd indices in a new array named ans. This is to ensure that we space out high-frequency barcodes, minimizing the risk of identical adjacent barcodes:

    • We first calculate the size of the array n and then create the answer array ans of that same size filled with zeros.

    • The clever part comes with Python's slice assignment:

      • ans[::2] is a way to refer to every second element of ans, starting from the first. We assign the first half of the barcodes to these positions.
      • ans[1::2] refers to every second element starting from the second, to which we assign the latter half of the barcodes.

    Here's how the code accomplishes that:

    1n = len(barcodes)
    2ans = [0] * n
    3ans[::2] = barcodes[: (n + 1) // 2]
    4ans[1::2] = barcodes[(n + 1) // 2 :]
  4. Returning the Result: The last line of the function simply returns the ans array, which is now a rearranged list of barcodes where no two adjacent barcodes are equal.

By using this approach, the algorithm effectively distributes barcodes of high frequency throughout the arrangement to satisfy the conditions of not having identical adjacent barcodes.

1class Solution:
2    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
3        cnt = Counter(barcodes)
4        barcodes.sort(key=lambda x: (-cnt[x], x))
5        n = len(barcodes)
6        ans = [0] * n
7        ans[::2] = barcodes[: (n + 1) // 2]
8        ans[1::2] = barcodes[(n + 1) // 2 :]
9        return ans
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we're given the following list of barcodes:

1barcodes = [1, 1, 1, 2, 2, 3]

Following the steps of the solution approach:

  1. Counting Frequencies: We use Counter to determine the number of occurrences of each barcode. In this example:

    1cnt = Counter([1, 1, 1, 2, 2, 3])  # Results in Counter({1: 3, 2: 2, 3: 1})
  2. Sorting Based on Frequency: Using the sorting key in sort, we arrange the barcodes first by decreasing frequency and then by their natural value:

    1sorted_barcodes = [1, 1, 1, 2, 2, 3]  # 1 is most common, then 2, and 3 is least common
  3. Structuring The Answer: The sorted list is now to be split across even and odd indices in a new array. The length of the barcodes list n is 6. The first half of the array (which is the first 3 elements, as (6 + 1) // 2 is 3) is placed at even indices:

    1ans = [0, 0, 0, 0, 0, 0]
    2ans[::2] = [1, 1, 1]

    And the latter half of the array (which is the last 3 elements) is placed at odd indices:

    1ans[1::2] = [2, 2, 3]

    So, ans becomes:

    1ans = [1, 2, 1, 2, 1, 3]
  4. Returning the Result: The final ans array is returned as the rearranged list of barcodes:

    1return [1, 2, 1, 2, 1, 3]

This rearranged array adheres to the condition that no two consecutive barcodes are the same. In this example, barcode 1, which occurred most frequently, is well spread out, followed by barcode 2, and barcode 3 is placed at the end to satisfy the condition.

Not Sure What to Study? Take the 2-min Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Python Solution

1from collections import Counter
2
3class Solution:
4    def rearrange_barcodes(self, barcodes: List[int]) -> List[int]:
5        # Count the frequency of each barcode
6        barcode_counts = Counter(barcodes)
7      
8        # Sort barcodes by decreasing frequency and then by value
9        # This is to prepare for the rearrangement ensuring no adjacent barcodes are same
10        barcodes.sort(key=lambda x: (-barcode_counts[x], x))
11      
12        # Get the total number of barcodes
13        total = len(barcodes)
14      
15        # Create a placeholder list for the answer
16        rearranged = [0] * total
17      
18        # Assign barcodes to even indices first (0, 2, 4, ...)
19        # We take the first half of the sorted barcodes
20        rearranged[::2] = barcodes[: (total + 1) // 2]
21      
22        # Then assign barcodes to the odd indices (1, 3, 5, ...)
23        # We take the second half of the sorted barcodes
24        rearranged[1::2] = barcodes[(total + 1) // 2 :]
25      
26        # Return the final arrangement of barcodes
27        return rearranged
28

Java Solution

1import java.util.Arrays; // Required for sorting the array
2
3public class Solution {
4    public int[] rearrangeBarcodes(int[] barcodes) {
5        // Determine the length of the barcodes array
6        int length = barcodes.length;
7        // Use wrapper class Integer for custom sorting
8        Integer[] tempBarcodes = new Integer[length];
9        // Variable to keep track of the maximum barcode value
10        int maxBarcode = 0;
11
12        // Copy barcodes to the temporary Integer array and find max value
13        for (int i = 0; i < length; ++i) {
14            tempBarcodes[i] = barcodes[i];
15            maxBarcode = Math.max(maxBarcode, barcodes[i]);
16        }
17
18        // Create and populate a count array for barcode frequencies
19        int[] count = new int[maxBarcode + 1];
20        for (int barcode : barcodes) {
21            ++count[barcode];
22        }
23
24        // Custom sort the array based on frequency (and then by value if frequencies are equal)
25        Arrays.sort(tempBarcodes, (a, b) -> count[a] == count[b] ? a - b : count[b] - count[a]);
26
27        // Create an array to hold the final rearranged barcodes
28        int[] rearranged = new int[length];
29
30        // Use two passes to distribute the barcodes ensuring no two adjacent barcodes are same
31        // Fill even indices first, then odd indices
32        for (int pass = 0, index = 0; pass < 2; ++pass) {
33            for (int i = pass; i < length; i += 2) {
34                rearranged[i] = tempBarcodes[index++];
35            }
36        }
37
38        // Return the rearranged barcodes
39        return rearranged;
40    }
41}
42

C++ Solution

1#include <vector>
2#include <algorithm>
3#include <cstring>
4
5class Solution {
6public:
7    // Rearranges barcodes in such a way that no two equal barcodes are adjacent
8    std::vector<int> rearrangeBarcodes(std::vector<int>& barcodes) {
9        // Find the highest value in barcodes to create an array large enough
10        int maxBarcodeValue = *std::max_element(barcodes.begin(), barcodes.end());
11      
12        // Create and initialize count array
13        int count[maxBarcodeValue + 1];
14        std::memset(count, 0, sizeof(count));
15      
16        // Count the occurrences of each barcode
17        for (int barcode : barcodes) {
18            ++count[barcode];
19        }
20
21        // Sort the barcodes based on the frequency of each barcode (descending), 
22        // and if frequencies are equal, sort by the barcode value (ascending)
23        std::sort(barcodes.begin(), barcodes.end(), [&](int a, int b) {
24            return count[a] > count[b] || (count[a] == count[b] && a < b);
25        });
26
27        int n = barcodes.size();
28        std::vector<int> result(n);
29
30        // Distribute the most frequent barcodes first, filling even positions, 
31        // then the rest in odd positions
32        int index = 0;
33        for (int i = 0; i < n; i += 2) {
34            result[i] = barcodes[index++];
35        }
36        for (int i = 1; i < n; i += 2) {
37            result[i] = barcodes[index++];
38        }
39
40        // Return the result vector with no two equal barcodes adjacent
41        return result;
42    }
43};
44

Typescript Solution

1function rearrangeBarcodes(barcodes: number[]): number[] {
2    // Find the maximum number value in the barcodes array
3    const maxBarcodeValue = Math.max(...barcodes);
4
5    // Initialize a count array with a length of the maximum number + 1, filled with zeroes
6    const count = Array(maxBarcodeValue + 1).fill(0);
7
8    // Count the occurrences of each barcode
9    for (const barcode of barcodes) {
10        count[barcode]++;
11    }
12
13    // Sort the barcodes array based on the frequency of each number and then by the number itself if frequencies are equal
14    barcodes.sort((a, b) => (count[a] === count[b] ? a - b : count[b] - count[a]));
15
16    // The length of the barcodes array
17    const totalBarcodes = barcodes.length;
18
19    // Initialize the answer array that will be rearranged
20    const rearranged = Array(totalBarcodes);
21
22    // Loop through the sorted barcodes to rearrange them such that no two equal barcodes are adjacent
23    let insertionIndex = 0;
24    for (let start = 0; start < 2; ++start) {
25        for (let i = start; i < totalBarcodes; i += 2) {
26            rearranged[i] = barcodes[insertionIndex];
27            insertionIndex++;
28        }
29    }
30
31    // Return the rearranged barcodes
32    return rearranged;
33}
34
Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by several operations:

  1. Counting elements with Counter(barcodes) takes O(n) time, where n is the number of elements in the barcodes list.

  2. Sorting the barcodes list with the custom sort key based on their count and value takes O(n log n) time.

  3. Slicing the list into two parts (for odd and even positions) is done in O(n) time.

  4. Assigning the sliced lists to ans using list slicing operations ans[::2] and ans[1::2] is done in O(n) time.

So, combining these operations, the overall time complexity of the code is O(n log n) due to the sort operation.

Space Complexity

The space complexity of the code is influenced by:

  1. The cnt object (counter of the elements), which takes O(unique) space, where unique is the number of unique elements in barcodes.

  2. The ans list, which is a new list of the same length as the input list, taking O(n) space.

Therefore, the total space complexity is O(n + unique), which simplifies to O(n) if we consider that the number of unique items is less than or equal to n.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫