Algorithm (Design)

1. First, we define a record type bucket which keeps tracks of the value and keys with that value. Then We keep track of 2 additional states:
   1. buckets: A list of bucket stored in a doubly linked list. We manually keep this list sorted by value in decresing order.
   2. buckets_map: A map between key and its corresponding bucket.
2. When increasing a key
   1. If key is not in buckets_map, we update the last bucket in the buckets list.
   2. Otherwise, we remove key from the bucket which holds key and insert it into the bucket whose value is value(key) + 1.
   3. Refresh the bucket and buckets_map to make sure states are correct and keys and values with empty buckets are removed.
3. The operation for decreasing key is exactly oppposite to that of increasing a key.
4. Under current setup and problem specification getMaxKey, getMinKey return a random key from head and tail of buckets.

Code (Cpp17)

class AllOne {
 private:
  struct bucket {
    int val;
    std::unordered_set<std::string> keys;
  };

 private:
  std::list<bucket> buckets_;
  std::unordered_map<std::string, std::list<bucket>::iterator> buckets_map_;

 private:
  std::list<bucket>::iterator bottom_bucket() { return std::prev(std::end(buckets_)); }
  std::list<bucket>::iterator top_bucket() { return std::begin(buckets_); }

  std::optional<std::list<bucket>::iterator> next_higher(std::list<bucket>::iterator it) {
    if (it == std::begin(buckets_))
      return std::nullopt;
    else
      return std::prev(it);
  }

  std::optional<std::list<bucket>::iterator> next_lower(std::list<bucket>::iterator it) {
    if (it == bottom_bucket())
      return std::nullopt;
    else
      return std::next(it);
  }

  void remove_key(std::list<bucket>::iterator bucket, const string & key) {
    bucket->keys.erase(key);
    if (bucket->keys.empty())
      buckets_.erase(bucket);
  }

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

  /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
  void inc(string key) {
    if (not buckets_map_.count(key)) {
      if (std::empty(buckets_) or bottom_bucket()->val != 1)
        buckets_map_[key] = (buckets_.emplace_back(bucket{1, {key}}),
                             bottom_bucket());
      else
        buckets_map_[key] = (bottom_bucket()->keys.insert(key),
                             bottom_bucket());
    }
    else {
      const auto [cur_bucket, next_higher_bucket] = pair{buckets_map_[key], next_higher(buckets_map_[key])};
      if (not next_higher_bucket)
        buckets_map_[key] = (buckets_.emplace_front(bucket{cur_bucket->val + 1, {key}}),
                             top_bucket());
      else if ((*next_higher_bucket)->val == cur_bucket->val + 1)
        buckets_map_[key] = (next_higher_bucket.value()->keys.insert(key),
                             next_higher_bucket.value());
      else if ((*next_higher_bucket)->val != cur_bucket->val + 1)
        buckets_map_[key] = buckets_.insert(cur_bucket, {cur_bucket->val + 1, {key}});
      remove_key(cur_bucket, key);
    }
  }

  /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
  void dec(string key) {
    if (not buckets_map_.count(key))
      return;
    else {
      const auto [cur_bucket, next_lower_bucket] = pair{buckets_map_[key], next_lower(buckets_map_[key])};
      if (cur_bucket->val == 1)
        buckets_map_.erase(key);
      else if (not next_lower_bucket)
        buckets_map_[key] = (buckets_.emplace_back(bucket{cur_bucket->val - 1, {key}}),
                             bottom_bucket());
      else if (next_lower_bucket.value()->val == cur_bucket->val - 1)
        buckets_map_[key] = (next_lower_bucket.value()->keys.insert(key),
                             next_lower_bucket.value());
      else if (next_lower_bucket.value()->val != cur_bucket->val - 1)
        buckets_map_[key] = buckets_.insert(next_lower_bucket.value(), {cur_bucket->val - 1, {key}});
      remove_key(cur_bucket, key);
    }
  }

  /** Returns one of the keys with maximal value. */
  string getMaxKey() {
    if (buckets_.empty())
      return {};
    else
      return *(std::begin(std::begin(buckets_)->keys));
  }

  /** Returns one of the keys with Minimal value. */
  string getMinKey() {
    if (buckets_.empty())
      return {};
    else
      return *(std::begin(std::rbegin(buckets_)->keys));
  }
};

/**
 * 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();
 */