Readable efficient code with O(1) time complexity


  • 0
    S

    My solution using Dicitonary(HashTable) and Doubly Linked List with fewer lines of code requires O(1) time complexity for both set and get operations. (Implemented in C# and readable)

    Lets create a wrapper class for holding the elements.

    class Node
        {
            public int Key;
            public int Value;
            public Node(int k, int v)
            {
                Key = k;
                Value = v;
            }
        }
    
    

    Now, lets create a dicitonary to hold the elements so that it can be used for fast loolups.
    Key : Key
    Value : Instance of wrapper class Node

    Dictionary<int, LinkedListNode<Node>> map = new Dictionary<int, LinkedListNode<Node>>();
    
    

    Also, a Doubly Linked List to keep track of inserted elements.

    LinkedList<Node> list = new LinkedList<Node>();
    

    Finally, count to keep count of number of elements in the list and size to store the capacity.

    Set(key, value)
    Case 1:
    Check if the dictionary contains the key. If yes, remove that node from the linked list and insert it to the end.
    Update the key in the dictionary to hold the newly inserted reference and return.

    if(map.ContainsKey(key))
            {
                list.Remove(map[key]);
                list.AddLast(new Node(key, value));
                map[key] = list.Last;
                return;
            }
    
    

    Case 2:
    If count == size
    Remove the first node from the linked list and remove its entry from the dicitonary adn decrement the count.
    Create a new node instance and insert it to the end of the linked list. Update the dictionary entry and increment the count.

    if(count == size)
            {
                LinkedListNode<Node> head = list.First;
                list.RemoveFirst();
                map.Remove(head.Value.Key);
                count--;
            }
            list.AddLast(new Node(key, value));
            map[key] = list.Last;
            count++;
    

    Case 3:
    If count < size
    Create a new node instance and insert it to the end of the linked list. Add to the dictionary and increment the count.

            list.AddLast(new Node(key, value));
            map[key] = list.Last;
            count++;
    

    Get(key)
    If the dictionary contains the key, remove its corressponding node from the linked list and insert it to the end.
    Update its dictionary entry to point to the newly created node instance.
    Else return -1

      if(map.ContainsKey(key))
            {
                int value = map[key].Value.Value;
                list.Remove(map[key]);
                list.AddLast(new Node(key, value));
                map[key] = list.Last;
                return value;
            }
            return -1;
    

    Final code

    public class LRUCache {
        
        class Node
        {
            public int Key;
            public int Value;
            public Node(int k, int v)
            {
                Key = k;
                Value = v;
            }
        }
        
        Dictionary<int, LinkedListNode<Node>> map = new Dictionary<int, LinkedListNode<Node>>();
        LinkedList<Node> list = new LinkedList<Node>();
        int count, size; 
        
        public LRUCache(int capacity) {
            size = capacity;    
        }
    
        public int Get(int key) {
            if(map.ContainsKey(key))
            {
                int value = map[key].Value.Value;
                list.Remove(map[key]);
                list.AddLast(new Node(key, value));
                map[key] = list.Last;
                return value;
            }
            return -1;
        }
    
        public void Set(int key, int value) {
            if(map.ContainsKey(key))
            {
                list.Remove(map[key]);
                list.AddLast(new Node(key, value));
                map[key] = list.Last;
                return;
            }
            if(count == size)
            {
                LinkedListNode<Node> head = list.First;
                list.RemoveFirst();
                map.Remove(head.Value.Key);
                count--;
            }
            list.AddLast(new Node(key, value));
            map[key] = list.Last;
            count++; 
        }
    }
    

Log in to reply
 

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