432. All O`one Data Structure

Design a data structure to store the strings’ count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

• AllOne() Initializes the object of the data structure.
• inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
• dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
• getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
• getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Note that each function must run in O(1) average time complexity.

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 01:

#include <list>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;

struct Node {
    int count;
    unordered_set<string> keys;
};

class AllOne {
public:
    // Increment the count of the given key
    void inc(string key) {
        if (const auto keyIterator = keyToNode.find(key); keyIterator == keyToNode.end()) {
            addNewKey(key);
        } else {
            incrementExistingKey(keyIterator, key);
        }
    }

    // Decrement the count of the given key
    void dec(string key) {
        const auto keyIterator = keyToNode.find(key);
        decrementExistingKey(keyIterator, key);
    }

    // Return the key with the maximum count
    string getMaxKey() {
        return nodeList.empty() ? "" : *nodeList.back().keys.begin();
    }

    // Return the key with the minimum count
    string getMinKey() {
        return nodeList.empty() ? "" : *nodeList.front().keys.begin();
    }

private:
    list<Node> nodeList;  // List of nodes sorted by count
    unordered_map<string, list<Node>::iterator> keyToNode;

    // Add a new key with count 1
    void addNewKey(const string& key) {
        if (nodeList.empty() || nodeList.front().count > 1) {
            nodeList.push_front({1, {key}});
        } else {
            nodeList.front().keys.insert(key);
        }
        keyToNode[key] = nodeList.begin();
    }

    // Increment the count of an existing key
    void incrementExistingKey(
        unordered_map<string, list<Node>::iterator>::iterator keyIterator,
        const string& key) {
        const auto currentNode = keyIterator->second;
        auto nextNode = next(currentNode);
        const int newCount = currentNode->count + 1;

        if (nextNode == nodeList.end() || nextNode->count > newCount) {
            nextNode = nodeList.insert(nextNode, {newCount, {key}});
        } else {
            nextNode->keys.insert(key);
        }

        keyToNode[key] = nextNode;
        removeKeyFromNode(currentNode, key);
    }

    // Decrement the count of an existing key
    void decrementExistingKey(
        unordered_map<string, list<Node>::iterator>::iterator keyIterator,
        const string& key) {
        const auto currentNode = keyIterator->second;

        if (currentNode->count == 1) {
            keyToNode.erase(keyIterator);
            removeKeyFromNode(currentNode, key);
            return;
        }

        auto previousNode = prev(currentNode);
        const int newCount = currentNode->count - 1;

        if (currentNode == nodeList.begin() || previousNode->count < newCount) {
            previousNode = nodeList.insert(currentNode, {newCount, {key}});
        } else {
            previousNode->keys.insert(key);
        }

        keyToNode[key] = previousNode;
        removeKeyFromNode(currentNode, key);
    }

    // Remove the key from the node, and erase the node if empty
    void removeKeyFromNode(list<Node>::iterator node, const string& key) {
        node->keys.erase(key);
        if (node->keys.empty()) {
            nodeList.erase(node);
        }
    }
};

class Node:
    def __init__(self, count):
        self.count = count
        self.keys = set()

class AllOne:
    def __init__(self):
        self.nodeList = []  # List of nodes sorted by count
        self.keyToNode = {}  # Map from key to corresponding node

    # Increment the count of the given key
    def inc(self, key):
        if key not in self.keyToNode:
            self.addNewKey(key)
        else:
            self.incrementExistingKey(key)

    # Decrement the count of the given key
    def dec(self, key):
        if key in self.keyToNode:
            self.decrementExistingKey(key)

    # Return the key with the maximum count
    def getMaxKey(self):
        return next(iter(self.nodeList[-1].keys)) if self.nodeList else ""

    # Return the key with the minimum count
    def getMinKey(self):
        return next(iter(self.nodeList[0].keys)) if self.nodeList else ""

    # Add a new key with count 1
    def addNewKey(self, key):
        if not self.nodeList or self.nodeList[0].count > 1:
            newNode = Node(1)
            newNode.keys.add(key)
            self.nodeList.insert(0, newNode)
        else:
            self.nodeList[0].keys.add(key)
        self.keyToNode[key] = self.nodeList[0]

    # Increment the count of an existing key
    def incrementExistingKey(self, key):
        currentNode = self.keyToNode[key]
        newCount = currentNode.count + 1

        nextNode = None
        # Check if the next node exists and has the correct count
        if self.nodeList.index(currentNode) + 1 < len(self.nodeList) and \
                self.nodeList[self.nodeList.index(currentNode) + 1].count == newCount:
            nextNode = self.nodeList[self.nodeList.index(currentNode) + 1]
        else:
            nextNode = Node(newCount)
            self.nodeList.insert(self.nodeList.index(currentNode) + 1, nextNode)

        nextNode.keys.add(key)
        self.keyToNode[key] = nextNode
        self.removeKeyFromNode(currentNode, key)

    # Decrement the count of an existing key
    def decrementExistingKey(self, key):
        currentNode = self.keyToNode[key]
        newCount = currentNode.count - 1

        if newCount == 0:
            del self.keyToNode[key]
            self.removeKeyFromNode(currentNode, key)
            return

        prevNode = None
        # Check if the previous node exists and has the correct count
        if self.nodeList.index(currentNode) > 0 and \
                self.nodeList[self.nodeList.index(currentNode) - 1].count == newCount:
            prevNode = self.nodeList[self.nodeList.index(currentNode) - 1]
        else:
            prevNode = Node(newCount)
            self.nodeList.insert(self.nodeList.index(currentNode), prevNode)

        prevNode.keys.add(key)
        self.keyToNode[key] = prevNode
        self.removeKeyFromNode(currentNode, key)

    # Remove the key from the node, and erase the node if empty
    def removeKeyFromNode(self, node, key):
        node.keys.remove(key)
        if not node.keys:
            self.nodeList.remove(node)

Time Complexity

• Increment Operation (inc):
  The time complexity of the inc operation primarily depends on updating the nodeList and the keyToNode map. In the worst case:
  Finding the current node for the key in the keyToNode map takes \(O(1)\).
  Inserting a new node in the nodeList (in case of a new count) also takes \(O(1)\) because list insertion is \(O(1)\).
  Erasing the key from the current node’s unordered_set and possibly removing the node if it’s empty takes \(O(1)\).
  Therefore, the overall time complexity for inc is \(O(1)\) in the amortized case.
• Decrement Operation (dec):
  Similar to the inc operation, the dec operation:
  Finds the current node in \(O(1)\).
  Inserts or updates the previous node (if applicable) in \(O(1)\).
  Removes the key from the current node’s unordered_set and possibly removes the node, which also takes \(O(1)\).
  Therefore, the overall time complexity for dec is also \(O(1)\) in the amortized case.
• Get Maximum and Minimum Keys (getMaxKey and getMinKey):
  Both operations simply return the first key in the unordered_set from the first or last node in the list. These operations take constant time, \(O(1)\).
• Overall Time Complexity:
  All operations (inc, dec, getMaxKey, getMinKey) have a time complexity of \(O(1)\) in the amortized case.

Space Complexity

• Auxiliary Space:
  The space complexity is determined by:
  The unordered_map keyToNode that maps each key to its respective node, which takes \(O(n)\) space where \(n\) is the number of unique keys.
  The list nodeList that stores nodes, each containing an integer count and a set of keys with that count. The total space used by the list and the sets is proportional to the number of unique keys, so it also takes \(O(n)\) space.
• Overall Space Complexity:
  The overall space complexity is \(O(n)\), where \(n\) is the number of unique keys.