All O(1) Data Structure

Design a data structure that supports inc(key), dec(key), getMaxKey(), getMinKey() all in O(1).

Example 1

inc("a"), inc("b"), inc("b"), inc("c"), inc("c"), inc("c"), getMaxKey()→"c", getMinKey()→"a"

Solution Approach

Use a doubly linked list of buckets sorted by count. Each bucket has a set of keys with that count. HashMap maps key→bucket. inc/dec move key between adjacent buckets.

DLL of Bucket(count, Set). Map keyToBucket.
inc(key): if bucket+1 exists after current, add key there; else create new bucket. Remove from old bucket.
dec(key): similarly move to bucket-1.
getMaxKey: return any key from tail.prev bucket.
getMinKey: return any key from head.next bucket.

Java

import java.util.*;

class AllOne {
    private static class Bucket {
        int count; Set<String> keys = new LinkedHashSet<>();
        Bucket prev, next;
        Bucket(int c) { count = c; }
    }
    Bucket head = new Bucket(0), tail = new Bucket(Integer.MAX_VALUE);
    Map<String, Bucket> map = new HashMap<>();

    public AllOne() { head.next=tail; tail.prev=head; }

    private void insertAfter(Bucket node, Bucket newNode) {
        newNode.prev=node; newNode.next=node.next;
        node.next.prev=newNode; node.next=newNode;
    }
    private void remove(Bucket node) {
        node.prev.next=node.next; node.next.prev=node.prev;
    }

    public void inc(String key) {
        if (!map.containsKey(key)) {
            if (head.next.count != 1) insertAfter(head, new Bucket(1));
            head.next.keys.add(key); map.put(key, head.next);
        } else {
            Bucket cur = map.get(key), next = cur.next;
            if (next == tail || next.count != cur.count+1) insertAfter(cur, new Bucket(cur.count+1));
            cur.next.keys.add(key); map.put(key, cur.next);
            cur.keys.remove(key); if (cur.keys.isEmpty()) remove(cur);
        }
    }
    public void dec(String key) {
        Bucket cur = map.get(key), prev = cur.prev;
        cur.keys.remove(key);
        if (cur.count-1 > 0) {
            if (prev == head || prev.count != cur.count-1) insertAfter(prev, new Bucket(cur.count-1));
            cur.prev.keys.add(key); map.put(key, cur.prev);
        } else { map.remove(key); }
        if (cur.keys.isEmpty()) remove(cur);
    }
    public String getMaxKey() { return tail.prev == head ? "" : tail.prev.keys.iterator().next(); }
    public String getMinKey() { return head.next == tail ? "" : head.next.keys.iterator().next(); }
}

Time Complexity: All operations O(1)
Space Complexity: O(N)