Linear time algo using list and a map


  • 0
    M
    class LRUCache {
        
        private int initialCapacity;
    
        private Map<Integer, Integer> keyValStore;
        private List<Integer> keyIndices;
        
        public LRUCache(int initialCapacity) {
            this.initialCapacity = initialCapacity;
            keyIndices = new ArrayList<>();
            keyValStore = new HashMap<>();
        }
        
        public int get(int key) {
            if(!keyValStore.containsKey(key)){
                return -1;
            }
            else{
                int keyIndex = keyIndices.indexOf((Integer)key);
                keyIndices.remove(keyIndex);
                keyIndices.add(key);
                return keyValStore.get(key);
            }
        }
        
        public void put(int key, int value) {
            if(initialCapacity > 0){
                int keyIndex = keyIndices.indexOf((Integer)key);
                if(keyIndex != -1){
                    keyIndices.remove(keyIndex);
                    keyIndices.add(key);
                }
                else{
                    keyIndices.remove((Integer)key);
                    keyIndices.add(key);
                    --initialCapacity;
                }
                
            }
            else{
                if(keyValStore.containsKey(key)){
                    Integer keyOb = key;
            		keyIndices.remove(keyOb);
            		keyIndices.add(key);
            		keyValStore.put(key,value);
            		return;
            	}
                Integer lastUsedKey = null;
                if(keyIndices.size()>0){
                    lastUsedKey = keyIndices.get(0);
                }
                if(lastUsedKey != null){
                    keyIndices.remove(lastUsedKey);
                }
                keyIndices.add(key);
                keyValStore.remove(lastUsedKey);
            }
            keyValStore.put(key, value);
        }
    }
    

Log in to reply
 

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