1054. Distant Barcodes

📝 Problem Details

• Title: 1054. Distant Barcodes
• Link: https://leetcode.com/problems/distant-barcodes/
• Difficulty: Medium
• Tags/Categories: Hashmap Priority-Queue Arrays

💭What Were My Initial Thoughts?

- create a frequency map for all integers in the barcodes array 
- and then sequentially search each element into the array until there is no more available element for that particular value
- however this doesnt take into account the fact that if an element has a higher frequency than others, it will have adjacent elements at the end of this new array. 
- maybe this solution involves a greedy approach, where we greedily choose the element from the hashmap with the highest frequency, that is not equal to the last element in our new array

🤔What Did I Struggle With?

~

💡 Explanation of Solution

- create a frequency map for the occurrence of integers in the barcodes array
- create a priority queue to store a pairs of integers (representing the value and freq)
	- insert each element in the map into the priority queue

- initialize a pair to store the last used element
- while the q is not empty
	- get the top element, pop it from the queue
	- push the value into the result 
	- reduce the frequency by 1
	- if the frequency of the last used element is > 0 , push that element into the queue
	- prev now is equal to the top variable

- return the result

⌛ Complexity Analysis

Time Complexity: O(n log n) where n log n is the initialization of elements into the priority queue, and reinsertion of them upon decrement of frequency

Space Complexity: O(n) for the use of auxillary space in the priority queue and frequency map

💻 Implementation of Solution

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        vector<int> result;
 
        // Create a hashmap of frequencies
        unordered_map<int, int> map;
        for (int barcode : barcodes) {
            map[barcode]++;
        }
 
        // Push each element into a priority queue
        priority_queue<pair<int, int>> q; // Max-heap with <frequency, barcode>
        for (const auto& item : map) {
            q.push({item.second, item.first}); // frequency first for ordering
        }
 
        // Rearrange barcodes
        pair<int, int> prev = {0, 0}; // To store the last used element
        while (!q.empty()) {
            auto topFreq = q.top();
            q.pop();
 
            // Add the most frequent element to the result
            result.push_back(topFreq.second);
            topFreq.first--;
 
            // Push the previously used element back into the queue (if it has remaining frequency)
            if (prev.first > 0) {
                q.push(prev);
            }
 
            // Update `prev` to the current element
            prev = topFreq;
        }
 
        return result;
    }
};