Untitled
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