Java O(1) Solution Using Two HashMap and One DoubleLinkedList


  • 6
    public class LFUCache {
        class Node {
            int key, val, cnt;
            Node prev, next;
            Node(int key, int val) {
                this.key = key;
                this.val = val;
                cnt = 1;
            }
        }
        
        class DLList {
            Node head, tail;
            int size;
            DLList() {
                head = new Node(0, 0);
                tail = new Node(0, 0);
                head.next = tail;
                tail.prev = head;
            }
            
            void add(Node node) {
                head.next.prev = node;
                node.next = head.next;
                node.prev = head;
                head.next = node;
                size++;
            }
            
            void remove(Node node) {
                node.prev.next = node.next;
                node.next.prev = node.prev;
                size--;
            }
            
            Node removeLast() {
                if (size > 0) {
                    Node node = tail.prev;
                    remove(node);
                    return node;
                }
                else return null;
            }
        }
        
        int capacity, size, min;
        Map<Integer, Node> nodeMap;
        Map<Integer, DLList> countMap;
        public LFUCache(int capacity) {
            this.capacity = capacity;
            nodeMap = new HashMap<>();
            countMap = new HashMap<>();
        }
        
        public int get(int key) {
            Node node = nodeMap.get(key);
            if (node == null) return -1;
            update(node);
            return node.val;
        }
        
        public void put(int key, int value) {
            if (capacity == 0) return;
            Node node;
            if (nodeMap.containsKey(key)) {
                node = nodeMap.get(key);
                node.val = value;
                update(node);
            }
            else {
                node = new Node(key, value);
                nodeMap.put(key, node);
                if (size == capacity) {
                    DLList lastList = countMap.get(min);
                    nodeMap.remove(lastList.removeLast().key);
                    size--;
                }
                size++;
                min = 1;
                DLList newList = countMap.getOrDefault(node.cnt, new DLList());
                newList.add(node);
                countMap.put(node.cnt, newList);
            }
        }
        
        private void update(Node node) {
            DLList oldList = countMap.get(node.cnt);
            oldList.remove(node);
            if (node.cnt == min && oldList.size == 0) min++; 
            node.cnt++;
            DLList newList = countMap.getOrDefault(node.cnt, new DLList());
            newList.add(node);
            countMap.put(node.cnt, newList);
        }
    }
    

  • 1
    S

    Great solution. Easy to understand :)


  • 0
    S

    One doubt, can you let me know the space complexity ?


  • 1

    @sghosh9ncsu.edu The space complexity is O(N) where N is the capacity of LFU. The nodeMap contains all nodes in LFU so it uses O(N) space. The countMap contains all Double Linked List, therefore, it also contains all nodes in LFU. So the total space of this two maps is 2 * N, which is O(N).


  • 1
    P

    @sghosh9ncsu.edu Yes, it is really an awesome solution!


  • 0
    M

    Enjoy this solution a lot as there is no fancy crazy data structure! Thanks.


  • 0
    P
    This post is deleted!

Log in to reply
 

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