My O(1) solution in java


  • 8
    M
    //Approach is to maintain a doubly link list  of key value pair (this will act as data structure for cache) and a Map which will store a reference to a node in the DLL corresponding to each key. 
    //In get operation, we will check for the key in the Map. If it is there , get reference to the Node from the Map and extract its value  and place it at the start of the list.Otherwise, return -1
    // For put operation, we need to put the the new node at the start of the list. If the capacity of cache is already met, remove the last node from the list(and its corresponding entry from the map).
    //Take care of the edge cases where cache capacity is only 1.
    
    
    
    
    public class LRUCache {
        //Node to store the key-value pairs.
         class Node
            {
                int key;
                int value;
                Node next;
                Node prev;
                public Node(int x , int y, Node n , Node p)
                {
                    key=x;
                    value=y;
                    next=n;
                    prev=p;
                }
                
            }
            
        // Doubly link list of type Node.    
        class DoublyLL
        {
           
            Node first;
            Node last;
            int size;
            int count;
            public DoublyLL(int c)
            {
                size=c;
                count=0;
                first=null;
                last=null;
                
            }
        }
        HashMap<Integer,Node> map;      //The map will store a reference to the Node in DLL corresponding to each key.
        DoublyLL dll;
        public LRUCache(int capacity) {
            
           
          dll=new DoublyLL(capacity);
            
            map=new HashMap <Integer,Node> ();
            
           
            
        }
        
        public int get(int key) {
            
            if(map.containsKey(key))
            {
                Node n=map.get(key);
                if(n.prev!=null)
                {
                if(dll.last==n)
                dll.last=n.prev;
                n.prev.next=n.next;
                if(n.next!=null)
                n.next.prev=n.prev;
                n.prev=null;
                n.next=dll.first;
                
                dll.first.prev=n;
                dll.first=n;
                }
                
               
                
                return n.value;
            }
            else
            {
                return -1;
            }
        }
       
        
        public void set(int key, int value) {
             Node n;
          
             if(!map.containsKey(key))
            {
                n=new Node(key,value,null,null);
                if(dll.size!=dll.count)
                {
                         n.next=dll.first;
                        if(dll.count!=0)
                        {
                            dll.first.prev=n;
                        }
                        else
                        {
                            dll.last=n;
                            
                        }
                       
                        dll.first=n;
                        dll.count++; 
                }
                else
                {
                
                    if(dll.count!=1)
                         {
                            map.remove(dll.last.key);
                            dll.last.prev.next=null;
                            dll.last=dll.last.prev;
                            dll.first.prev=n;
                            n.next=dll.first;
                            dll.first=n;
                             
                         }
                    else
                    {   map.remove(dll.first.key);
                        dll.first=n;
                        dll.last=n;
                    }
                
                }
                  map.put(key,n);
                 
            }
            else
            {
                n=map.get(key);
                n.value=value;
                if(n.prev!=null)
                {
                if(dll.last==n)
                dll.last=n.prev;
                n.prev.next=n.next;
                if(n.next!=null)
                n.next.prev=n.prev;
                n.prev=null;
                n.next=dll.first;
                
                dll.first.prev=n;
                dll.first=n;
                }
            }
                
             
        }
        
    }`

  • 0
    R

    I made some modification on your solution. Take a look.


  • 10
    R
    public class LRUCache {
    	// Node to store the key-value pairs.
    	private class Node {
    		int key;
    		int value;
    		Node next;
    		Node prev;
    
    		public Node(int key, int value) {
    			this.key = key;
    			this.value = value;
    			next = null;
    			prev = null;
    		}
    	}
    
    	// Doubly link list of type Node.
    	private class DoublyLL {
    
    		Node head;
    		Node last;
    		int capacity;
    		int count;
    
    		public DoublyLL(int c) {
    			this.capacity = c;
    			count = 0;
    			head = new Node(0, 0);// Their keys and value do not matter.
    			last = new Node(0, 0);
    			head.next = last;
    			last.prev = head;
    		}
    	}
    
    	HashMap<Integer, Node> map; // The map will store a reference to the Node in
    								// DLL corresponding to each key.
    	DoublyLL dll;
    
    	public LRUCache(int capacity) {
    		dll = new DoublyLL(capacity);
    		map = new HashMap<Integer, Node>();
    	}
    
    	public int get(int key) {
    
    		if (map.containsKey(key)) {
    			Node n = map.get(key);
    
    			if (n.prev != dll.head) {
    				detach(n);
    				attach(n);
    			}
    
    			return n.value;
    		} else
    			return -1;
    	}
    
    	public void set(int key, int value) {
    		Node n;
    
    		if (!map.containsKey(key)) {
    			n = new Node(key, value);
    			if (dll.capacity != dll.count)
    				dll.count++;
    			else {
    				map.remove(dll.last.prev.key);
    				detach(dll.last.prev);
    			}
    			attach(n);
    			map.put(key, n);
    
    		} else {
    			n = map.get(key);
    			n.value = value;
    			detach(n);
    			attach(n);
    		}
    	}
    
    	private void attach(Node node) {
    		node.prev = dll.head;
    		node.next = dll.head.next;
    		dll.head.next.prev = node;
    		dll.head.next = node;
    
    	}
    
    	private void detach(Node node) {
    		node.prev.next = node.next;
    		node.next.prev = node.prev;
    	}
    
    }

  • 0
    M

    Looks cleaner and compact.
    Good job !


  • 0
    U

    my java solution, may O(1)

    public class LRUCache {

    class Element {
        int key;
        int value;
        public Element(int k, int v) {
            key = k;
            value = v;
        }
    }
    
    LinkedList<Element> cache = new LinkedList<Element>();
    HashMap<Integer, Element> hash = new HashMap<Integer, Element>();
    int cap = 0;
    
    public LRUCache(int capacity) {
        cap = capacity;
    }
    
    public int get(int key) {
        
        Element e = hash.get(key);
        if (e == null) {
            return -1;
        }
        
        cache.remove(e);
        cache.add(e);
            
        return e.value;
    }
    
    public void set(int key, int value) {
        int val = get(key);
        
        if (val == -1) {  // not cached.
            if (cache.size() == cap) {
                Element e = cache.remove();
                hash.remove(e.key);
            }
        } else { // cached, update it.
            cache.removeLast();
        }
        Element e = new Element(key, value);
        cache.add(e);
        hash.remove(e.key);
        hash.put(e.key, e);
    }
    

    }


  • 0
    R

    Are you sure cache.remove() is O(1) time complexity?


  • 0
    U

    yes, because in Java, LinkedList implements deque. so ...


  • 0
    R

    What if the code needs to remove some element in the middle? If the capacity is 2, then it is fine.


  • 0
    U

    Remove a middle element in a LinkedList(with the parameter of this element), the time complixcity is O(1),because it is a doube-linked queue.


  • 0
    J

    It takes O(n) time to search the corresponding node, and O(1) time to remove the node as you say, so O(n) time in total.
    Refer to this method of LinkedList: Node<E> node(int index)


  • 0
    U

    I think it's O(1) time to find and remove the node, using the parameter of the node, not index. If it is implemented in double-linked list. And then the iterator can move next and also can move previous.


  • 0
    R

    How about finding the 3rd node?


  • 0
    U

    what I find is not the xrd node, but the node itself, so it is O(1).


  • 0
    J

    cache.remove(e);

    it will take o(n). As it has to scan the list to find e. Note the e is not the linked node itself, it doesn't has pre/next link, so a full scan can't be avoided. That's why other O(n) solution has to use a self implemented Double Linked List instead of JDK build in one.


  • 1
    J
    public class LRUCache {
    	static class Node{
    		Node next;
    		Node prev;
    		int key;
    		int val;
    		Node(){}
    		Node(int key, int val){this.key = key; this.val = val;}
    		
    		private void delete(){
    			prev.next = next;
    			if(next != null)
    				next.prev = prev;
    		}
    		
    		private void addAfter(Node preNode){
    			next = preNode.next;
    			if(next != null)
    				next.prev = this;
    			preNode.next = this;
    			prev = preNode;
    		}
    	}
    	
    	Node head = new Node();
    	Node tail = head;
    	
    	Map<Integer, Node> cache = new HashMap<Integer, Node>();
    	int capacity;
    	
    	public LRUCache(int capacity) {
    		this.capacity = capacity;
    	}
    
    	public int get(int key) {
    		Node n = cache.get(key);
    		if(n == null)
    			return -1;
    		moveToTail(n);
    		return n.val;
    	}
    
    	public void set(int key, int value) {
    		Node n = cache.get(key);
    		if(n != null){
    			n.val = value;
    			moveToTail(n);
    			return;
    		}
    
    		n = new Node(key, value);
    		cache.put(key, n);
    		addToTail(n);
    		
    		if(cache.size() > capacity){
    			n = head.next;
    			cache.remove(n.key);
    			n.delete();
    		}
    	}
    	
    	private void moveToTail(Node n){
    		if(n == tail)
    			return;
    		n.delete();
    		addToTail(n);
    	}
    	
    	private void addToTail(Node n){
    		n.addAfter(tail);
    		tail = n;		
    	}
    }

  • 0
    G

    LinkedList.remove() is a O(n) operation unless you have a pointer to the LinkedListNode itelf, which you don't because Java doesn't provide this feature like C# does. You only have the value of the linked list node you want to remove, which requires searching through the list to find the element to remove. If you want proof that its O(n), then run it on a large input size and you'll see.


  • 0
    U

    Sorry, I am wrong, all you guys are correct. Thank you.


  • 0
    D

    I think you have memory leak.
    When you call detach for a node, your original node continues to point to other nodes so the garbage collector is not going to collect it


  • 0
    R

    The garbage collector will label any unaccessible object from the stacks. So the original node will be cleaned.


Log in to reply
 

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