In this Leetcode All O'one Data Structure problem solution 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.

  1. 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.
  2. 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.
  3. getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
  4. getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Leetcode All O'one Data Structure problem solution


Problem solution in Python.

class Node:
    def __init__(self, val = 0):
        self.val = val
        self.elements = set()
        self.prev = None
        self.next = None

class AllOne:

    def __init__(self):
        self.dummy_head = Node(0)
        self.dummy_tail = Node(0)
        self.dummy_head.next = self.dummy_tail
        self.dummy_tail.prev = self.dummy_head
        self.freq_node = {}
        self.count = {}
        
    def insert_after(self, node, prev):
        prev.next.prev = node
        node.next = prev.next
        prev.next = node
        node.prev = prev
        
    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        
    def add_key_to_freq(self, freq, key):
        if freq in self.freq_node:
            self.freq_node[freq].elements.add(key)
        else:
            new_node = Node(freq)
            new_node.elements.add(key)
            self.freq_node[freq] = new_node
            if freq == 1:
                self.insert_after(new_node, self.dummy_head)
            # either node corresponding to freq - 1 or freq + 1 exist, because we are doing inc/dec 
            else:
                if freq - 1 in self.freq_node:                
                    self.insert_after(new_node, self.freq_node[freq - 1])
                else: # self.freq + 1 in self.freq_node
                    self.insert_after(new_node, self.freq_node[freq + 1].prev)
    
    def remove_key_from_freq(self, freq, key):
        orig_node = self.freq_node[freq] 
        orig_node.elements.remove(key)
        if not orig_node.elements:
            self.remove(orig_node)
            self.freq_node.pop(freq)
            
    def inc(self, key: str) -> None:
        if key not in self.count:
            self.count[key] = 1
            self.add_key_to_freq(1, key)
        else:
            v = self.count[key]
            self.count[key] += 1
            self.add_key_to_freq(v + 1, key)
            self.remove_key_from_freq(v, key)

    def dec(self, key: str) -> None:
        v = self.count[key]
        if v > 1:
            self.count[key] -= 1
            self.add_key_to_freq(v - 1, key)
        else:
            self.count.pop(key)
        self.remove_key_from_freq(v, key)
        

    def getMaxKey(self) -> str:
        if self.dummy_head.next == self.dummy_tail:
            return ""
        for s in self.dummy_tail.prev.elements:
            return s

    def getMinKey(self) -> str:
        if self.dummy_head.next == self.dummy_tail:
            return ""
        for s in self.dummy_head.next.elements:
            return s



Problem solution in Java.

class AllOne {

    class Node {
        Set<String> keys;
        int val;
        Node prev = null;
        Node next = null;
        
        Node(int val) {
            this.val = val;
            this.keys = new HashSet<>();
        }
        
        Node(String key, int val) {
            this(val);
            this.keys.add(key);
        }
    }
    
    Map<String, Node> map;
    Node head;
    Node tail;
    
    /** Initialize your data structure here. */
    public AllOne() {
        this.map = new HashMap<>();
        this.head = new Node(-1);
        this.tail = new Node(-1);
        this.head.prev = tail;
        this.tail.next = head;
    }
    
    private void deleteNode(Node node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.next = null;
        node.prev = null;
    }
    
    private void removeKeyFromNode(String key, Node node) {
        node.keys.remove(key);
        if (node.keys.isEmpty()) {
            deleteNode(node);
        }
    }
    
    private void insertNext(Node node, Node newNode) {
        node.next.prev = newNode;
        newNode.next = node.next;
        node.next = newNode;
        newNode.prev = node;
    }

    public void inc(String key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            if (node.val + 1 == node.next.val) {
                node.next.keys.add(key);
                map.put(key, node.next);
            } else {
                Node newNode = new Node(key, node.val + 1);
                insertNext(node, newNode);
                map.put(key, newNode);
            }
            removeKeyFromNode(key, node);
        } else {
            if (tail.next.val == 1) {
                tail.next.keys.add(key);
                map.put(key, tail.next);
            } else {
                Node newNode = new Node(key, 1);
                insertNext(tail, newNode);
                map.put(key, newNode);
            }
        }
    }

    public void dec(String key) {
        if (!map.containsKey(key)) {
            return;
        }
        
        Node node = map.get(key);
        if (node.val == 1) {
            map.remove(key);
        } else if (node.val - 1 == node.prev.val) {
            node.prev.keys.add(key);
            map.put(key, node.prev);
        } else {
            Node newNode = new Node(key, node.val - 1);
            map.put(key, newNode);
            insertNext(node.prev, newNode);
        }
        removeKeyFromNode(key, node);
    }

    public String getMaxKey() {
        return head.prev.keys.isEmpty() ? "" : head.prev.keys.iterator().next();
    }

    public String getMinKey() {
        return tail.next.keys.isEmpty() ? "" : tail.next.keys.iterator().next();
    }
}


Problem solution in C++.

class AllOne {
public:

unordered_map<string, int> m;
string max, min;

AllOne() {
    
}

void inc(string key) {
    m[key]++;
    max = min = "";
}

void dec(string key) {
    m[key]--;
    if(m[key] == 0)
        m.erase(key);
    max = min = "";
}

string getMaxKey() {
    
    if(max.size())
        return max;
    
    m[max] = INT_MIN;
    
    for(auto i : m)
        if(i.second > m[max])
            max = i.first;
    
    return max;
}

string getMinKey() {
    
    if(min.size())
        return min;
    
    m[min] = INT_MAX;
    
    for(auto i : m)
        if(i.second < m[min])
            min = i.first;
    
    return min;
}
};