LeetCode 1054: Distant Barcodes Solution

Master LeetCode problem 1054 (Distant Barcodes), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1054. Distant Barcodes

Medium

Array Hash Table Greedy Sorting Heap (Priority Queue)Counting

Problem Explanation

Explanation

To solve this problem, we can use a greedy approach. We first count the frequency of each barcode and then place the barcodes with higher frequency first, alternating with barcodes of lower frequency. This way, we can ensure that no two adjacent barcodes are the same.

Count the frequency of each barcode.
Create a priority queue (max heap) to store barcodes based on their frequencies.
Iterate through the priority queue and place the barcodes in alternate positions in the result array.
If the frequency of a barcode becomes 0, remove it from the priority queue.
Repeat the process until all barcodes are placed.

Time Complexity: O(n log n) - where n is the number of barcodes.

Space Complexity: O(n) - to store the frequency of each barcode and the priority queue.

Solution Code

import java.util.*;

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int barcode : barcodes) {
            countMap.put(barcode, countMap.getOrDefault(barcode, 0) + 1);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> countMap.get(b) - countMap.get(a));
        pq.addAll(countMap.keySet());

        int[] result = new int[barcodes.length];
        int index = 0;

        while (!pq.isEmpty()) {
            int barcode = pq.poll();
            int count = countMap.get(barcode);

            while (count > 0) {
                result[index] = barcode;
                index += 2;
                if (index >= barcodes.length) {
                    index = 1;
                }
                count--;
            }

            if (countMap.get(barcode) > 0) {
                pq.offer(barcode);
            }
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1054 (Distant Barcodes)?

This page provides optimized solutions for LeetCode problem 1054 (Distant Barcodes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1054 (Distant Barcodes)?

The time complexity for LeetCode 1054 (Distant Barcodes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1054 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1054 in Java, C++, or Python.

Back to LeetCode Solutions