Untitled

 avatar
unknown
plain_text
8 days ago
1.3 kB
1
Indexable
class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
           Map<Integer, Integer> freqMap = new HashMap<>();
        
        // Step 1: Count frequency of each barcode
        for (int barcode : barcodes) {
            freqMap.put(barcode, freqMap.getOrDefault(barcode, 0) + 1);
        }

        // Step 2: Use a max heap to get the most frequent barcode first
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            maxHeap.add(new int[]{entry.getKey(), entry.getValue()});
        }

        int n = barcodes.length;
        int[] result = new int[n];
        int index = 0;
        int[] prev = {-1, 0}; // To store last used barcode

        // Step 3: Arrange barcodes
        while (!maxHeap.isEmpty()) {
            int[] curr = maxHeap.poll(); // Most frequent barcode
            result[index++] = curr[0];   // Place it in result
            curr[1]--;                   // Decrease frequency

            // Push the previous element back if it still has occurrences left
            if (prev[1] > 0) {
                maxHeap.add(prev);
            }

            prev = curr; // Update prev to current
        }

        return result;
    }
}
Leave a Comment