432. All O`one Data Structure

Description

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.

 

Solutions

Solution: Doubly-Linked List

• Time complexity: O(1)
• Space complexity: O(n)

 

JavaScript

class Node {
  constructor(count) {
    this.count = count;
    this.keys = new Set();
    this.prev = null;
    this.next = null;
  }
}

const AllOne = function () {
  this.keyMap = new Map();
  this.countMap = new Map();
  this.head = new Node(0);
  this.tail = new Node(0);
  this.head.next = this.tail;
  this.tail.prev = this.head;
};

AllOne.prototype.addNode = function (prevNode, node) {
  const nextNode = prevNode.next;

  prevNode.next = node;
  node.prev = prevNode;
  node.next = nextNode;
  nextNode.prev = node;
};

AllOne.prototype.removeNode = function (node) {
  const { prev: prevNode, next: nextNode } = node;

  prevNode.next = nextNode;
  nextNode.prev = prevNode;
};

AllOne.prototype.addKeyToNode = function (prevNode, count, key) {
  if (!this.countMap.has(count)) {
    const newNode = new Node(count);

    this.countMap.set(count, newNode);
    this.addNode(prevNode, newNode);
  }
  this.countMap.get(count).keys.add(key);
};

AllOne.prototype.deleteKeyFromNode = function (node, key) {
  node.keys.delete(key);
  if (node.keys.size) return;
  this.removeNode(node);
  this.countMap.delete(node.count);
};

/**
 * @param {string} key
 * @return {void}
 */
AllOne.prototype.inc = function (key) {
  if (this.keyMap.has(key)) {
    const count = this.keyMap.get(key);
    const node = this.countMap.get(count);

    this.keyMap.set(key, count + 1);
    this.addKeyToNode(node, count + 1, key);
    this.deleteKeyFromNode(node, key);
    return;
  }
  this.keyMap.set(key, 1);
  this.addKeyToNode(this.head, 1, key);
};

/**
 * @param {string} key
 * @return {void}
 */
AllOne.prototype.dec = function (key) {
  if (!this.keyMap.has(key)) return;
  const count = this.keyMap.get(key);
  const node = this.countMap.get(count);

  if (count > 1) {
    this.keyMap.set(key, count - 1);
    this.addKeyToNode(node.prev, count - 1, key);
  } else this.keyMap.delete(key);
  this.deleteKeyFromNode(node, key);
};

/**
 * @return {string}
 */
AllOne.prototype.getMaxKey = function () {
  if (this.tail.prev === this.head) return '';
  return this.tail.prev.keys.values().next().value;
};

/**
 * @return {string}
 */
AllOne.prototype.getMinKey = function () {
  if (this.head.next === this.tail) return '';
  return this.head.next.keys.values().next().value;
};

/**
 * Your AllOne object will be instantiated and called as such:
 * var obj = new AllOne()
 * obj.inc(key)
 * obj.dec(key)
 * var param_3 = obj.getMaxKey()
 * var param_4 = obj.getMinKey()
 */