All O`one Data Structure


public class AllOne {class Tuple{
    String key;
    int val;
    Tuple(String s, int v){

Map<String, Integer> map; //store key-> index of the following list
List<Tuple> list; //store all (key,value) in reversing sorted value order [(a,3),(b,3),(c,2),(d,1)]
Map<Integer, Integer> indexMap; //start index for each value, using above example (3->0),(2->2),(1,3)

/** Initialize your data structure here. */
public AllOne() {
    map = new HashMap<>();
    list = new ArrayList<>();
    indexMap = new HashMap<>();

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
public void inc(String key) {
        //swap curr with the first element which val equals curr.val
        int i = map.get(key);
        Tuple curr = list.get(i);
        int first=indexMap.get(curr.val);
        Tuple exchange =list.get(first);
        list.set(i, exchange);
        list.set(first, curr);
        map.put(key, first);
        map.put(exchange.key, i);
        //update curr val index
        indexMap.put(curr.val, first+1);
        //increase val, if it is a new val, put 0 in index map
        if(!indexMap.containsKey(curr.val)) indexMap.put(curr.val, 0);
        //if a new key, add to the last of list
        Tuple t = new Tuple(key, 1);
        map.put(key, list.size()-1);

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
public void dec(String key) {
        int i=map.get(key);
        Tuple curr = list.get(i);
            Tuple last = list.get(list.size()-1);
            list.set(i, last);
            map.put(last.key, i);
            //swap curr with the last element which val equals curr.val
            int index = indexMap.get(curr.val-1)-1;
            Tuple exchange = list.get(index);
            list.set(i, exchange);
            list.set(index, curr);
            map.put(key, index);
            map.put(exchange.key, i);
            if(index==0) indexMap.remove(curr.val);
            indexMap.put(curr.val, index);

/** Returns one of the keys with maximal value. */
public String getMaxKey() {
    if(!list.isEmpty()) return list.get(0).key;
    return "";

/** Returns one of the keys with Minimal value. */
public String getMinKey() {
    if(!list.isEmpty()) return list.get(list.size()-1).key;
    return "";

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