Algorithm

Problem Name: 432. All O`one Data Structure

Problem Link: https://leetcode.com/problems/all-oone-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.

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const AllOne = function() {
  this.map = new Map()
}

AllOne.prototype.inc = function(key) {
  let curCount
  if (this.map.has(key)) {
    curCount = this.map.get(key) + 1
  } else {
    curCount = 1
  }
  this.map.set(key, curCount)
}

AllOne.prototype.dec = function(key) {
  if (this.map.has(key)) {
    if (this.map.get(key) > 1) {
      this.map.set(key, this.map.get(key) - 1)
    } else this.map.delete(key)
  } else {
    return
  }
}

AllOne.prototype.getMaxKey = function() {
  let max = -Infinity,
    maxStr = ''
  for (let k of this.map) {
    if (k[1] > max) {
      max = k[1]
      maxStr = k[0]
    }
  }
  return maxStr
}

AllOne.prototype.getMinKey = function() {
  let min = Infinity,
    minStr = ''
  for (let k of this.map) {
    if (k[1] < min) {
      min = k[1]
      minStr = k[0]
    }
  }
  return minStr
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []]

Output

x
–
+
cmd
null, null, null, "hello", "hello", null, "hello", "leet"]

#2 Code Example with Python Programming

Code - Python Programming


class Node:
    def __init__(self, key, value):
        self.val = value
        self.key = key
        self.next = None
        self.pre = None
class AllOne:

    def __init__(self):
        self.first = {}
        self.last = {}
        self.keys = {}
        self.head = Node(-1, -1)
        self.tail = Node(-1, -1)
        self.head.next = self.tail
        self.tail.pre = self.head
        
    def add(self, prev, node):
        node.pre = prev
        node.next = prev.next
        node.pre.next = node.next.pre = node
        
    def remove(self, node):
        node.pre.next = node.next
        node.next.pre = node.pre
        
    def process(self, node):
        if self.last[node.val] == node and node.pre.val != node.val:
            self.first.pop(node.val)
            self.last.pop(node.val)
        elif self.first[node.val] == node:
            self.first[node.val] = node.next
        elif self.last[node.val] == node:
            self.last[node.val] = node.pre
            
    def process2(self, node, prev, key, d):
        if key in self.keys:
            if node.val + d in self.last:
                self.add(self.last[node.val + d], node)
            elif node.val in self.last:
                self.add(self.last[node.val], node)
            else:
                self.add(prev, node)
        elif 1 in self.last:
            node = Node(key, 0)
            self.add(self.last[1], node)
        else:
            node = Node(key, 0)
            self.add(self.head, node)
        node.val += d
        self.last[node.val] = node
        if node.val not in self.first:
            self.first[node.val] = node
        if key not in self.keys:
            self.keys[key] = node
                
    def inc(self, key):
        if key in self.keys:
            node = self.keys[key]
            prev = node.pre
            self.process(node)
            self.remove(node)
            self.process2(node, prev, key, 1)
        else:
            self.process2(None, None, key, 1)
            
    def dec(self, key):
        if key in self.keys:
            node = self.keys[key]
            prev = node.pre
            self.process(node)
            self.remove(node)
            if node.val != 1:
                self.process2(node, prev, key, -1)
            else:
                self.keys.pop(key)
            
    def getMaxKey(self):
        return self.tail.pre.key if self.tail.pre != self.head else ""
    def getMinKey(self):
        return self.head.next.key if self.head.next != self.tail else ""
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []]

Output

x
–
+
cmd
null, null, null, "hello", "hello", null, "hello", "leet"]

#3 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
    public class _0432_AllOOneDataStructure
    {
        private Node head, tail;
        private Dictionary < string, Node> map;

        public _0432_AllOOneDataStructure()
        {
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;

            map = new Dictionary < string, Node>();
        }

        public void Inc(string key)
        {
            Node node = null;
            if (map.ContainsKey(key))
                node = map[key];
            else
                node = head;

            var next = node.next;
            if (next.val != node.val + 1)
            {
                next = new Node(node.val + 1);
                AddNode(node, next);
            }
            RemoveKey(key, node);
            AddKey(key, next);
        }

        public void Dec(string key)
        {
            if (!map.ContainsKey(key)) return;

            var node = map[key];
            if (node.val == 1)
            {
                map.Remove(key);
                RemoveKey(key, node);
                return;
            }

            var prev = node.prev;
            if (prev.val != node.val - 1)
            {
                prev = new Node(node.val - 1);
                AddNode(node.prev, prev);
            }

            RemoveKey(key, node);
            AddKey(key, prev);
        }

        public string GetMaxKey()
        {
            if (tail.prev == head) return string.Empty;

            return tail.prev.keys.First();
        }

        public string GetMinKey()
        {
            if (head.next == tail) return string.Empty;

            return head.next.keys.First();
        }

        private void AddNode(Node node, Node next)
        {
            next.next = node.next;
            node.next.prev = next;

            next.prev = node;
            node.next = next;
        }

        private void RemoveNode(Node node)
        {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void AddKey(string key, Node node)
        {
            map.Add(key, node);
            node.keys.Add(key);
        }

        private void RemoveKey(string key, Node node)
        {
            if (node == head) return;
            node.keys.Remove(key);
            map.Remove(key);

            if (node.keys.Count == 0)
                RemoveNode(node);
        }

        public class Node
        {
            public HashSet < string> keys;
            public Node next, prev;
            public int val;

            public Node(int val = 0)
            {
                this.val = val;
                next = null;
                prev = null;
                keys = new HashSet < string>();
            }
        }
    }

}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []]

Output

x
–
+
cmd
null, null, null, "hello", "hello", null, "hello", "leet"]
Advertisements

Demonstration

Previous
#430 Leetcode Flatten a Multilevel Doubly Linked List Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#433 Leetcode Minimum Genetic Mutation Solution in C, C++, Java, JavaScript, Python, C# Leetcode