# All One Data Structure LeetCode Solution

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

## 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”

## All One Data Structure LeetCode Solution C++

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

class AllOne {
public:
list <Entry> data;
unordered_map <string, list<Entry>::iterator> 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()->cnt == 1) {
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->cnt+1, key));
}
else if (entry->cnt+1 == next(entry)->cnt) {
pos[key] = next(entry);
}
else {
pos[key] = data.insert(next(entry), Entry(entry->cnt+1, key));
}
entry->remove(key);
if (entry->empty()) data.erase(entry);
}
}

void dec(string key) {
auto entry = pos[key];
if (entry->cnt > 1) {
if (entry == data.begin()) {
pos[key] = data.insert(data.begin(), Entry(entry->cnt-1, key));
}
else if (entry->cnt-1 == prev(entry)->cnt) {
pos[key] = prev(entry);
}
else {
pos[key] = data.insert(entry, Entry(entry->cnt-1, key));
}
}
else pos.erase(key);
entry->remove(key);
if (entry->empty()) data.erase(entry);
}
string getMaxKey() {
if (data.empty()) return "";
return prev(data.end())->getAnyKey();
}
string getMinKey() {
if (data.empty()) return "";
return data.begin()->getAnyKey();
}
};Code language: PHP (php)

## All One Data Structure LeetCode Solution Java

class AllOne {
Map<String, Integer> map;
Map<Integer, Set<String>> valueMap;

public AllOne() {
map = new HashMap<>();
valueMap = new HashMap<>();
}

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<String>());
}
if(minMax.isEmpty() || minMax.getFirst() < count) {
}
if(!minMax.isEmpty() && minMax.getLast() > 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() && minMax.getFirst() == count) {
minMax.removeFirst();
}
if(!minMax.isEmpty() && minMax.getLast() == count) {
minMax.removeLast();
}
}
}
}Code language: JavaScript (javascript)

## 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 && this.minCount == count)
newMinCount = newMinCount + 1;

let set = this.freqSetMap.get(count + 1) || new Set();
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();
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();
this.freqSetMap.set(count - 1, set);
this.keyFreqMap.set(key, count - 1);
}
if (existing_set.size == 0 && this.maxCount == count) this.maxCount -= 1;
if (existing_set.size == 0 && this.minCount == count) {
let min = this.maxCount;
for (let key of this.freqSetMap.keys()) {
min = Math.min(min, key);
}
if (this.freqSetMap.size > 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;
};Code language: JavaScript (javascript)

## 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

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
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()