Last updated on October 9th, 2024 at 05:52 pm

Here, We see All One Data Structure LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Design

Companies

Uber

Level of Question

Hard

All One Data Structure LeetCode Solution

Problem Statement

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”

1. All One Data Structure LeetCode Solution C++

class Entry {
public:
    int cnt;
    unordered_set &lt;string&gt; keys;
    Entry(int _cnt, string &amp;key) {
        cnt = _cnt;
        keys.insert(key);
    }
    void add(string &amp;key) {
        keys.insert(key);
    }
    void remove(string &amp;key) {
        keys.erase(key); 
    }
    bool empty() {
        return keys.empty(); 
    }
    string getAnyKey() {
        return *(keys.begin()); 
    }
};

class AllOne {
public:
    list &lt;Entry&gt; data;
    unordered_map &lt;string, list&lt;Entry&gt;::iterator&gt; pos;
    AllOne() {
    }
    void inc(string key) {
        if (data.empty()) {
            data.push_back(Entry(1, key));
            pos[key] = data.begin(); 
            return;
        }
        if (pos.find(key) == pos.end()) {
            if (data.begin()-&gt;cnt == 1) {
                data.begin()-&gt;add(key);
                pos[key] = data.begin(); 
            }
            else {
                pos[key] = data.insert(data.begin(), Entry(1, key)); 
            }
        }
        else {
            auto entry = pos[key]; 
            if (entry == prev(data.end())) {
                pos[key] = data.insert(data.end(), Entry(entry-&gt;cnt+1, key)); 
            }
            else if (entry-&gt;cnt+1 == next(entry)-&gt;cnt) {
                next(entry)-&gt;add(key);
                pos[key] = next(entry); 
            }
            else {
                pos[key] = data.insert(next(entry), Entry(entry-&gt;cnt+1, key)); 
            }
            entry-&gt;remove(key);
            if (entry-&gt;empty()) data.erase(entry); 
        }  
    }
    
    void dec(string key) {
        auto entry = pos[key]; 
        if (entry-&gt;cnt &gt; 1) {
            if (entry == data.begin()) {
                pos[key] = data.insert(data.begin(), Entry(entry-&gt;cnt-1, key)); 
            }
            else if (entry-&gt;cnt-1 == prev(entry)-&gt;cnt) {
                prev(entry)-&gt;add(key);
                pos[key] = prev(entry); 
            }
            else {
                pos[key] = data.insert(entry, Entry(entry-&gt;cnt-1, key)); 
            }
        }
        else pos.erase(key); 
        entry-&gt;remove(key);
        if (entry-&gt;empty()) data.erase(entry); 
    }
    string getMaxKey() {
        if (data.empty()) return ""; 
        return prev(data.end())-&gt;getAnyKey(); 
    }
    string getMinKey() {
        if (data.empty()) return ""; 
        return data.begin()-&gt;getAnyKey(); 
    }
};

2. All One Data Structure LeetCode Solution Java

class AllOne {
    Map&lt;String, Integer&gt; map;
    Map&lt;Integer, Set&lt;String&gt;&gt; valueMap;
    LinkedList&lt;Integer&gt; minMax;

    public AllOne() {
        map = new HashMap&lt;&gt;();
        valueMap = new HashMap&lt;&gt;();
        minMax = new LinkedList&lt;Integer&gt;();
    }
    
    public void inc(String key) {
        if(!map.containsKey(key)) {
            map.put(key, 1);
            putInValueMap(1, key);
        } else {
            int val = map.get(key);
            removeFromValueMap(val, key);
            map.put(key, val + 1);
            putInValueMap(val + 1, key);
        }
    }

    public void dec(String key) {
        if(!map.containsKey(key)) {
            return;
        }
        int val = map.get(key);
        if(val == 1) {
            map.remove(key);
            removeFromValueMap(1, key);
        } else {
            removeFromValueMap(val, key);
            map.put(key, val - 1);
            putInValueMap(val - 1, key);
        }
        
    }
    
    public String getMaxKey() {
        if(minMax.isEmpty()) {
            return "";
        }
        return valueMap.get(minMax.getFirst()).iterator().next();
    }
    public String getMinKey() {
        if(minMax.isEmpty()) {
            return "";
        }
        return valueMap.get(minMax.getLast()).iterator().next();
    }
    
    private void putInValueMap(int count, String node) {
        if(!valueMap.containsKey(count)) {
            valueMap.put(count, new HashSet&lt;String&gt;());
        }
        valueMap.get(count).add(node);
        if(minMax.isEmpty() || minMax.getFirst() &lt; count) {
            minMax.addFirst(count);
        }
        if(!minMax.isEmpty() &amp;&amp; minMax.getLast() &gt; count) {
            minMax.addLast(count);
        }
    }
    
    private void removeFromValueMap(int count, String node) {
        if(!valueMap.containsKey(count)) {
            return;
        }
        valueMap.get(count).remove(node);
        if(valueMap.get(count).size() == 0) {
            valueMap.remove(count);
            if(!minMax.isEmpty() &amp;&amp; minMax.getFirst() == count) {
                minMax.removeFirst();
            }
            if(!minMax.isEmpty() &amp;&amp; minMax.getLast() == count) {
                minMax.removeLast();
            }
        }
    }
}

3. All One Data Structure LeetCode Solution JavaScript

var AllOne = function () {
  this.minCount = 0;
  this.maxCount = 0;
  this.keyFreqMap = new Map();
  this.freqSetMap = new Map();
};

AllOne.prototype.inc = function (key) {
  let count = this.keyFreqMap.get(key);
  let newMaxCount = count;
  let newMinCount = this.minCount;
  if (count) {
    let existing_set = this.freqSetMap.get(count);
    existing_set.delete(key);
    if (existing_set.size == 0) {
      this.freqSetMap.delete(count);
    } else {
      this.freqSetMap.set(count, existing_set);
    }
    if (existing_set.size == 0 &amp;&amp; this.minCount == count)
      newMinCount = newMinCount + 1;

    let set = this.freqSetMap.get(count + 1) || new Set();
    set.add(key);
    this.freqSetMap.set(count + 1, set);

    this.keyFreqMap.set(key, count + 1);
    newMaxCount = count + 1;
  } else {
    this.keyFreqMap.set(key, 1);
    let existing_set = this.freqSetMap.get(1) || new Set();
    existing_set.add(key);
    this.freqSetMap.set(1, existing_set);
    newMinCount = 1;
    newMaxCount = 1;
  }
  this.minCount = newMinCount;
  this.maxCount = Math.max(this.maxCount, newMaxCount);
  return null;
};

AllOne.prototype.dec = function (key) {
  let count = this.keyFreqMap.get(key);
  if (count) {
    let existing_set = this.freqSetMap.get(count);
    existing_set.delete(key);
    if (existing_set.size == 0) {
      this.freqSetMap.delete(count);
    } else {
      this.freqSetMap.set(count, existing_set);
    }
    if (count == 1) {
      this.keyFreqMap.delete(key);
    } else {
      let set = this.freqSetMap.get(count - 1) || new Set();
      set.add(key);
      this.freqSetMap.set(count - 1, set);
      this.keyFreqMap.set(key, count - 1);
    }
    if (existing_set.size == 0 &amp;&amp; this.maxCount == count) this.maxCount -= 1;
    if (existing_set.size == 0 &amp;&amp; this.minCount == count) {
      let min = this.maxCount;
      for (let key of this.freqSetMap.keys()) {
        min = Math.min(min, key);
      }
      if (this.freqSetMap.size &gt; 0) this.minCount = min;
    }
  }
  return null;
};

AllOne.prototype.getMaxKey = function () {
  let set = this.freqSetMap.get(this.maxCount) || new Set();
  let firstElement = "";
  for (let val of set) {
    firstElement = val;
    break;
  }
  return firstElement;
};

AllOne.prototype.getMinKey = function () {
  let set = this.freqSetMap.get(this.minCount) || new Set();
  let firstElement = "";

  for (let val of set) {
    firstElement = val;
    break;
  }
  return firstElement;
};

4. All One Data Structure LeetCode Solution Python

class Block(object):
    def __init__(self, val=0):
        self.val = val
        self.keys = set()
        self.before = None
        self.after = None

    def remove(self):
        self.before.after = self.after
        self.after.before = self.before
        self.before, self.after = None, None

    def insert_after(self, new_block):
        old_after = self.after
        self.after = new_block
        new_block.before = self
        new_block.after = old_after
        old_after.before = new_block


class AllOne(object):
    def __init__(self):
        self.begin = Block() 
        self.end = Block()
        self.begin.after = self.end
        self.end.before = self.begin
        self.mapping = {} 

    def inc(self, key):
        if not key in self.mapping:
            current_block = self.begin
        else:
            current_block = self.mapping[key]
            current_block.keys.remove(key)

        if current_block.val + 1 != current_block.after.val:
            new_block = Block(current_block.val + 1)
            current_block.insert_after(new_block)
        else:
            new_block = current_block.after

        new_block.keys.add(key)
        self.mapping[key] = new_block

        if not current_block.keys and current_block.val != 0:
            current_block.remove()

    def dec(self, key):
        if not key in self.mapping:
            return

        current_block = self.mapping[key]
        del self.mapping[key]
        current_block.keys.remove(key)

        if current_block.val != 1:
            if current_block.val - 1 != current_block.before.val:
                new_block = Block(current_block.val - 1)
                current_block.before.insert_after(new_block)
            else:
                new_block = current_block.before
            new_block.keys.add(key)
            self.mapping[key] = new_block

        if not current_block.keys:
            current_block.remove()

    def getMaxKey(self):
        if self.end.before.val == 0:
            return ""
        key = self.end.before.keys.pop()
        self.end.before.keys.add(key)
        return key

    def getMinKey(self):
        if self.begin.after.val == 0:
            return ""
        key = self.begin.after.keys.pop()
        self.begin.after.keys.add(key)
        return key