All O`one Data Structure

Problem Statement

The task involves designing an efficient data structure named AllOne that manages a collection of strings and efficiently tracks their occurrence counts. This data structure should offer the ability to increment or decrement the count of any given string and must also provide quick access to the string with the highest and lowest counts respectively. Specifically, the functions required in this data structure include:

• AllOne(): A constructor to initiate the data structure.
• inc(String key): Increases the count of a specified string key by 1. If key is not present, it is added to the data structure with an initial count of 1.
• dec(String key): Decreases the count of a specified string key by 1 and removes the string entirely if its count reaches 0. It is ensured that the key exists in the data structure before its count is decremented.
• getMaxKey(): Retrieves a string that has the maximum count so far. Returns an empty string if the data structure is empty.
• getMinKey(): Retrieves a string that has the minimum count so far. Returns an empty string if the data structure is empty.

In addition, every operation in the data structure (inc, dec, getMaxKey, getMinKey) should operate in average O(1) time complexity, pointing towards the requirement for optimized data management and access strategies.

Examples

Example 1

Input ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []] Output [null, null, null, "hello", "hello", null, "hello", "leet"] Explanation AllOne allOne = new AllOne(); allOne.inc("hello"); allOne.inc("hello"); allOne.getMaxKey(); // return "hello" allOne.getMinKey(); // return "hello" allOne.inc("leet"); allOne.getMaxKey(); // return "hello" allOne.getMinKey(); // return "leet"

Constraints

• 1 <= key.length <= 10
• key consists of lowercase English letters.
• It is guaranteed that for each call to dec, key is existing in the data structure.
• At most 5 * 104 calls will be made to inc, dec, getMaxKey, and getMinKey.

Approach and Intuition

Given the requirements of the AllOne data structure, a combination of multiple data organization strategies can be employed to ensure optimal performance as described in the constraints. Here is an intuitive approach based on the operations described:

1. Handling the Counts: A hash map (countMap) can be employed where keys are the strings and values are their respective counts. This allows O(1) time complexity for increment (inc) and decrement (dec) operations simply by checking and updating the count directly via the hash key.

2. Tracking Minimum and Maximum: To retrieve the minimum and maximum count strings efficiently:

   • Maintain two additional hash maps: one (maxFreqMap) to store strings with the maximum count and another (minFreqMap) for those with the minimum count. Updating these maps on every inc and dec operation ensures constant time access to minimum and maximum count strings.
   • Alternatively, a more evolved approach involves using a doubly linked list (DLL) alongside the primary hash map (countMap). This list maintains nodes in sorted order of counts, where each node contains strings with the same count. This allows efficient movement of strings between different count nodes and quick updates to min and max references.

3. Ensuring O(1) Operations: Using the hash maps for direct access to counts and doubly linked lists to maintain order without needing to rebuild or rescan array-like structures ensures all operations meet the required O(1) time complexity on average.

4. Example Execution:

   • Initializing the AllOne: Start with an empty countMap, maxFreqMap, and minFreqMap.
   • On calling inc("hello") twice, the count for "hello" becomes 2. "hello" updates both the maximum and minimum as it is the only string.
   • When inc("leet") is called, it is added with a count of 1. Now, "leet" becomes the new minimum, while "hello" remains the maximum.

Solutions

class FrequencyNode {
public:
    int frequency;
    FrequencyNode* previous;
    FrequencyNode* next;
    unordered_set<string> itemKeys;
    
    FrequencyNode(int frequency) : frequency(frequency), previous(nullptr), next(nullptr) {}
};
    
class MaxMinCounter {
private:
    FrequencyNode* dummyHead;
    FrequencyNode* dummyTail;
    unordered_map<string, FrequencyNode*> keyToNodeMap;
    
public:
    MaxMinCounter() {
        dummyHead = new FrequencyNode(0);
        dummyTail = new FrequencyNode(0);
        dummyHead->next = dummyTail;
        dummyTail->previous = dummyHead;
    }
    
    void increase(string key) {
        if (keyToNodeMap.count(key)) {
            FrequencyNode* currentNode = keyToNodeMap[key];
            int currentFreq = currentNode->frequency;
            currentNode->itemKeys.erase(key);
    
            FrequencyNode* nextNode = currentNode->next;
            if (nextNode == dummyTail || nextNode->frequency != currentFreq + 1) {
                FrequencyNode* newNode = new FrequencyNode(currentFreq + 1);
                newNode->itemKeys.insert(key);
                newNode->previous = currentNode;
                newNode->next = nextNode;
                currentNode->next = newNode;
                nextNode->previous = newNode;
                keyToNodeMap[key] = newNode;
            } else {
                nextNode->itemKeys.insert(key);
                keyToNodeMap[key] = nextNode;
            }
    
            if (currentNode->itemKeys.empty()) {
                deleteNode(currentNode);
            }
        } else {
            FrequencyNode* firstNode = dummyHead->next;
            if (firstNode == dummyTail || firstNode->frequency > 1) {
                FrequencyNode* newNode = new FrequencyNode(1);
                newNode->itemKeys.insert(key);
                newNode->previous = dummyHead;
                newNode->next = firstNode;
                dummyHead->next = newNode;
                firstNode->previous = newNode;
                keyToNodeMap[key] = newNode;
            } else {
                firstNode->itemKeys.insert(key);
                keyToNodeMap[key] = firstNode;
            }
        }
    }
    
    void decrease(string key) {
        if (!keyToNodeMap.count(key)) {
            return;
        }
    
        FrequencyNode* currentNode = keyToNodeMap[key];
        currentNode->itemKeys.erase(key);
        int currentFreq = currentNode->frequency;
    
        if (currentFreq == 1) {
            keyToNodeMap.erase(key);
        } else {
            FrequencyNode* prevNode = currentNode->previous;
            if (prevNode == dummyHead || prevNode->frequency != currentFreq - 1) {
                FrequencyNode* newNode = new FrequencyNode(currentFreq - 1);
                newNode->itemKeys.insert(key);
                newNode->previous = prevNode;
                newNode->next = currentNode;
                prevNode->next = newNode;
                currentNode->previous = newNode;
                keyToNodeMap[key] = newNode;
            } else {
                prevNode->itemKeys.insert(key);
                keyToNodeMap[key] = prevNode;
            }
        }
    
        if (currentNode->itemKeys.empty()) {
            deleteNode(currentNode);
        }
    }
    
    string getMaximumKey() {
        if (dummyTail->previous == dummyHead) {
            return "";
        }
        return *dummyTail->previous->itemKeys.begin();
    }
    
    string getMinimumKey() {
        if (dummyHead->next == dummyTail) {
            return "";
        }
        return *dummyHead->next->itemKeys.begin();
    }
    
private:
    void deleteNode(FrequencyNode* node) {
        FrequencyNode* prevNode = node->previous;
        FrequencyNode* nextNode = node->next;
        prevNode->next = nextNode;
        nextNode->previous = prevNode;
        delete node;
    }
};