LFU (Least Frequently Used) Cache

/**
Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( capacity =2);

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4
*/
import java.util.*;


/**
Solution:
-we maintain three hashmaps
-one map for key, value pairs for the data itself
-another map for the key and the count/hits for the key
-another map for the key as the hits/counts and the values as the LinkedHashSet of the keys that were hit that many times. The LinkedHashSet ensures that the recently used item is at the end of this set
*/
class LFUCache {
    int cap;
    int min = -1;
    Map<Integer, Integer> vals;
    Map<Integer, Integer> cnts;
    Map<Integer, LinkedHashSet<Integer>> map;
   
    public LFUCache(int capacity) {
        cap = capacity;
        vals = new HashMap<>();
        cnts = new HashMap<>();
        map = new HashMap<>();
        map.put(1, new LinkedHashSet<>());
    }
   
    public int get(int key) {
        if (!vals.containsKey(key)) return -1;
        int cnt = cnts.get(key);
        cnts.put(key, cnt + 1);
        map.get(cnt).remove(key);
        if (cnt == min && map.get(cnt).size() == 0) min++;
        if (!map.containsKey(cnt + 1)) map.put(cnt + 1, new LinkedHashSet<>());
        map.get(cnt + 1).add(key);
        return vals.get(key);
    }
   
    public void put(int key, int value) {
        if (cap <= 0) return;
        if (vals.containsKey(key)) {
            vals.put(key, value);
            get(key);
            return;
        }
        if (vals.size() >= cap) {
            int r = map.get(min).iterator().next();
            map.get(min).remove(r);
            vals.remove(r);
            cnts.remove(r);//added by me
        }
        vals.put(key, value);
        cnts.put(key, 1);
        min = 1;
        map.get(1).add(key);
    }
}


public class LFUCacheDemo{
public static void main(String[] args){
LFUCache cache = new LFUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1));       // returns 1
cache.put(3, 3);    // evicts key 2
System.out.println(cache.get(2));       // returns -1 (not found)
System.out.println(cache.get(3));       // returns 3.
cache.put(4, 4);    // evicts key 1.
System.out.println(cache.get(1));       // returns -1 (not found)
System.out.println(cache.get(3));       // returns 3
System.out.println(cache.get(4));       // returns 4
}
}