TLE Please Help


  • 0
    E

    Am I doing something in O(n) time? My best guess is .offer() that takes O(N) time..? Any help is appreciated, thanks!

    public class LRUCache {
        
        private HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        private Queue<Integer> lru = new LinkedList<Integer>();
        int limit;
        
        public LRUCache(int capacity) {
            limit = capacity;
            
        }
        
        public int get(int key) {
            if(!map.containsKey(key)) return -1;
            
            return map.get(key);
            
        }
        
        public void set(int key, int value) {
            if(map.containsKey(key)) return;
            
            if(lru.size() == limit) {
                int removeKey = lru.poll();
                map.remove(removeKey);
                System.out.println(removeKey);
            }
            
            lru.offer(key);
            map.put(key, value);
            
        }
    }

  • 1
    Z

    Because the complexity of size method of list is O(N).

    Check this:

    https://gcc.gnu.org/onlinedocs/gcc-4.9.2/libstdc++/manual/manual/containers.html#sequences.list.size


Log in to reply
 

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