Simple Java Solution with comments using a HashMap and a List


  • 0
    A
    public class LRUCache {
        private final int maxCapacity;
        private final Map<Integer, Integer> cache;
        private final List<Integer> lru; // list of LRU items - item at index 0 is ready to be invalidated
        
        public LRUCache(int capacity) {
            maxCapacity = capacity;
            cache = new HashMap<Integer, Integer>();
            lru = new ArrayList<Integer>();
        }
        
        public int get(int key) {
            if (!cache.containsKey(key)) {
                return -1;
            }
            
            // move the key to the end of the LRU list
            lru.remove(lru.indexOf(key));
            lru.add(key);
            
            return cache.get(key);
        }
        
        public void set(int key, int value) {
            int val = get(key); // this call also ensures the key gets moved to end of LRU list
            cache.put(key, value); // add or overwrite the value in the cache
                
            if (val == -1) {
                lru.add(key); // if the value wasn't in the cache, enqueue it
            
                if (cache.size() > maxCapacity) { // remove item at index 0 if we reached capacit
                    cache.remove(lru.get(0));
                    lru.remove(0);
                }
            }
        }
    }

  • 0
    W

    Seems like the underlying implementation of ArrayList does not support constant time access to the element. This solution is getting TLE.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.