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.

C++

#include <unordered_map>
#include <unordered_set>
#include <string>

using namespace std;

class Node {
public:
    Node* prev;
    Node* next;
    int cnt;
    unordered_set<string> keys;

    Node() : cnt(0), prev(nullptr), next(nullptr) {}

    Node(string key, int cnt) : cnt(cnt), prev(nullptr), next(nullptr) {
        keys.insert(key);
    }

    Node* insert(Node* node) {
        node->prev = this;
        node->next = this->next;
        if (this->next) {
            this->next->prev = node;
        }
        this->next = node;
        return node;
    }

    void remove() {
        if (prev) prev->next = next;
        if (next) next->prev = prev;
    }
};

class AllOne {
private:
    Node* root;
    unordered_map<string, Node*> nodes;

public:
    AllOne() {
        root = new Node();
        root->next = root;
        root->prev = root;
    }

    void inc(string key) {
        if (nodes.find(key) == nodes.end()) {
            if (root->next == root || root->next->cnt > 1) {
                nodes[key] = root->insert(new Node(key, 1));
            } else {
                root->next->keys.insert(key);
                nodes[key] = root->next;
            }
        } else {
            Node* curr = nodes[key];
            Node* next = curr->next;
            if (next == root || next->cnt > curr->cnt + 1) {
                nodes[key] = curr->insert(new Node(key, curr->cnt + 1));
            } else {
                next->keys.insert(key);
                nodes[key] = next;
            }
            curr->keys.erase(key);
            if (curr->keys.empty()) {
                curr->remove();
                delete curr;
            }
        }
    }

    void dec(string key) {
        Node* curr = nodes[key];
        if (curr->cnt == 1) {
            nodes.erase(key);
        } else {
            Node* prev = curr->prev;
            if (prev == root || prev->cnt < curr->cnt - 1) {
                nodes[key] = prev->insert(new Node(key, curr->cnt - 1));
            } else {
                prev->keys.insert(key);
                nodes[key] = prev;
            }
        }
        curr->keys.erase(key);
        if (curr->keys.empty()) {
            curr->remove();
            delete curr;
        }
    }

    string getMaxKey() {
        return root->prev == root ? "" : *root->prev->keys.begin();
    }

    string getMinKey() {
        return root->next == root ? "" : *root->next->keys.begin();
    }
};




JAVA

class AllOne {
    Node root = new Node();
    Map<String, Node> nodes = new HashMap<>();

    public AllOne() {
        root.next = root;
        root.prev = root;
    }

    public void inc(String key) {
        if (!nodes.containsKey(key)) {
            if (root.next == root || root.next.cnt > 1) {
                nodes.put(key, root.insert(new Node(key, 1)));
            } else {
                root.next.keys.add(key);
                nodes.put(key, root.next);
            }
        } else {
            Node curr = nodes.get(key);
            Node next = curr.next;
            if (next == root || next.cnt > curr.cnt + 1) {
                nodes.put(key, curr.insert(new Node(key, curr.cnt + 1)));
            } else {
                next.keys.add(key);
                nodes.put(key, next);
            }
            curr.keys.remove(key);
            if (curr.keys.isEmpty()) {
                curr.remove();
            }
        }
    }

    public void dec(String key) {
        Node curr = nodes.get(key);
        if (curr.cnt == 1) {
            nodes.remove(key);
        } else {
            Node prev = curr.prev;
            if (prev == root || prev.cnt < curr.cnt - 1) {
                nodes.put(key, prev.insert(new Node(key, curr.cnt - 1)));
            } else {
                prev.keys.add(key);
                nodes.put(key, prev);
            }
        }

        curr.keys.remove(key);
        if (curr.keys.isEmpty()) {
            curr.remove();
        }
    }

    public String getMaxKey() {
        return root.prev.keys.iterator().next();
    }

    public String getMinKey() {
        return root.next.keys.iterator().next();
    }
}

class Node {
    Node prev;
    Node next;
    int cnt;
    Set<String> keys = new HashSet<>();

    public Node() {
        this("", 0);
    }

    public Node(String key, int cnt) {
        this.cnt = cnt;
        keys.add(key);
    }

    public Node insert(Node node) {
        node.prev = this;
        node.next = this.next;
        node.prev.next = node;
        node.next.prev = node;
        return node;
    }

    public void remove() {
        this.prev.next = this.next;
        this.next.prev = this.prev;
    }
}