# Leetcode 432 Solution

https://leetcode.com/problems/all-oone-data-structure

## Solution

``````class AllOne {
struct Bucket
{
int val;
unordered_set<string> keys;
};

list<Bucket> l;
unordered_map<string, list<Bucket>::iterator> m;

public:
/** Initialize your data structure here. */
AllOne() {
}

void display()
{
for (auto it = l.begin(); it != l.end(); it++)
{
printf("%d:", it->val);
for (auto key : it->keys)
printf("%s ", key.c_str());
printf("\n");
}
printf("\n");
}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
void inc(string key) {
if (m.find(key) == m.end())
{
if (l.front().val != 1)
{
Bucket bucket;
bucket.val = 1;
l.push_front(bucket);
}

auto it = l.begin();
it->keys.insert(key);
m[key] = it;
}
else
{
auto it = m[key];
it->keys.erase(key);

auto next_it = it;
next_it++;
auto target_it = next_it;

if (next_it == l.end() || next_it->val > it->val + 1)
{
Bucket bucket;
bucket.val = it->val + 1;
target_it = l.insert(next_it, bucket);
}

target_it->keys.insert(key);
m[key] = target_it;

if (it->keys.empty())
l.erase(it);
}
}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(string key) {
if (m.find(key) == m.end())
return;

auto it = m[key];
it->keys.erase(key);

if (it->val == 1)
{
m.erase(key);
if (it->keys.empty())
l.erase(it);
return;
}

auto prev_it = it;
prev_it--;
auto target_it = prev_it;

if (it == l.begin() || prev_it->val < it->val - 1)
{
Bucket bucket;
bucket.val = it->val - 1;
target_it = l.insert(it, bucket);
}

target_it->keys.insert(key);
m[key] = target_it;

if (it->keys.empty())
l.erase(it);
}

/** Returns one of the keys with maximal value. */
string getMaxKey() {
if (l.empty())
return "";

return *l.back().keys.begin();
}

/** Returns one of the keys with Minimal value. */
string getMinKey() {
if (l.empty())
return "";

return *l.front().keys.begin();
}
};

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