98ms, Java solution using HashMap and DoubleLinkedList


  • 0
    N
    
    public class AllOne {
    
        /** Initialize your data structure here. */
        class LinkedNode{
            LinkedNode left, right;
            String key;
            int val;
            public LinkedNode(String key, int val){ this.key = key; this.val = val;}
        }
        
        LinkedNode head, tail;
        Map<String, LinkedNode> maps;
        
        public AllOne() {
            head = new LinkedNode("", Integer.MAX_VALUE);
            tail = new LinkedNode("", Integer.MIN_VALUE);
            head.right = tail;
            tail.left = head;
            maps = new HashMap<>();
        }
        
        private void moveToHead(LinkedNode node){
            while(node.val>node.left.val){
                LinkedNode leftNode = node.left;
                
                node.left = leftNode.left;
                leftNode.right = node.right;
                
                node.left.right = node;
                leftNode.right.left = leftNode;
                
                node.right = leftNode;
                leftNode.left = node;
            }
        }
        
        private void addToHead(LinkedNode node){
            head.right.left = node;
            node.right = head.right;
            
            node.left = head;
            head.right = node;
        }
        
        private void moveToTail(LinkedNode node){
            while(node.val<node.right.val){
                LinkedNode rightNode = node.right;
                
                node.right = rightNode.right;
                rightNode.left = node.left;
                
                node.right.left = node;
                rightNode.left.right = rightNode;
                
                node.left = rightNode;
                rightNode.right = node;
            }
        }
        
        private void addToTail(LinkedNode node){
            tail.left.right = node;
            node.left = tail.left;
            
            node.right = tail;
            tail.left = node;
        }
        
        private void remove(LinkedNode node){
            node.right.left = node.left;
            node.left.right = node.right;
            node.left = null;
            node.right = null;
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            if(maps.containsKey(key)){
                LinkedNode node = maps.get(key);
                node.val++;
                if(node.val > head.right.val){
                    remove(node);
                    addToHead(node);
                }else{
                    moveToHead(node);
                }
                
            }else{
                LinkedNode node = new LinkedNode(key,1);
                maps.put(key, node);
                addToTail(node);
            }
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            if(!maps.containsKey(key)) return;
            LinkedNode node = maps.get(key);
            if(node.val == 1){
                maps.remove(key);
                remove(node);
            }else{
                node.val--;
                if(node.val < tail.left.val){
                    remove(node);
                    addToTail(node);
                }else{
                    moveToTail(node);
                }
                
            }
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            return head.right.key;
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            return tail.left.key;
        }
    }
    
    /**
     * Your AllOne object will be instantiated and called as such:
     * AllOne obj = new AllOne();
     * obj.inc(key);
     * obj.dec(key);
     * String param_3 = obj.getMaxKey();
     * String param_4 = obj.getMinKey();
     */
    
    

    Space: O(n)

    inc() O(1) worst case O(n)
    dec() O(1) worst case O(n)
    getMaxKey() O(1)
    getMinKey() O(1).

    Accept any improvement idea, thanks!


  • 0
    L

    I don't trust your "dec" function.
    If the node after head has been decreased to have a value less than the maximum, but still larger than the minimum, it will not be moved to other place, therefore, its value is still considered the maximum.

    Please try the following case:

    ["AllOne","inc","inc","inc","inc","inc","inc","inc","inc","getMaxKey","getMinKey","dec","dec","getMaxKey","getMinKey"]
    [[],["A"],["A"],["A"],["CC"],["b"],["b"],["b"],["b"],[],[],["b"],["b"],[],[]]


  • 0
    N

    Thanks for pointing out, I will fix this.


  • 0
    N

    @liu31 said in Java solution using HashMap and DoubleLinkedList:

    I don't trust your "dec" function.
    If the node after head has been decreased to have a value less than the maximum, but still larger than the minimum, it will not be moved to other place, therefore, its value is still considered the maximum.

    Please try the following case:

    ["AllOne","inc","inc","inc","inc","inc","inc","inc","inc","getMaxKey","getMinKey","dec","dec","getMaxKey","getMinKey"]
    [[],["A"],["A"],["A"],["CC"],["b"],["b"],["b"],["b"],[],[],["b"],["b"],[],[]]

    the output would be : b CC A CC.
    Hey, already fixed it, but the time complexity of inc() and dec() not strictly O(1), they both have a worst case O(n).


  • 0
    L

    @nightswatch

    I don't know how to make it O(1) either. I used HashMap and TreeMap, so it's O(nlogn).


  • 0
    D

    Try This . this is O(1) solution

    /**

    • Created by debabrata_sharma on 10/17/16.
      */
      public class AllOneDataStructure {

      public class Node {
      Node next, prev;
      private String key;
      private int val;

       public Node(String key, int val) {
           this.key = key;
           this.val = val;
       }
      

      }

      Node head, tail;
      Map<String, Node> map;

      /**

      • Initialize your data structure here.
        */
        public AllOneDataStructure() {

        map = new HashMap<String, Node>();
        head = new Node("", Integer.MAX_VALUE);
        tail = new Node("", Integer.MIN_VALUE);
        head.next = tail;
        tail.prev = head;

      }

    /**
     * Inserts a new key <Key> with value 1. Or increments an existing key by 1.
     */
    public void inc(String key) {
    
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val++;
            if(node.val>head.next.val){
                removeNode(node);
                addToHead(node);
            }
        } else {
            Node node = new Node(key, 1);
            map.put(key, node);
            addToTail(node);
        }
    }
    
    /**
     * Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
     */
    public void dec(String key) {
    
        if (map.containsKey(key)) {
            Node node = map.get(key);
            if (node.val == 1) {
                map.remove(key);
                removeNode(node);
            } else {
    
                node.val--;
    
                if( node.val<tail.prev.val ){
                    removeNode(node);
                    addToTail(node);
                }
                if(node.key==head.next.key){
                    if (node.val<=head.next.val) {
                        removeNode(node);
                        addNextToHead(node);
                    }
                }
    
            }
        } else {
            return;
        }
    
    }
    
    /**
     * Returns one of the keys with maximal value.
     */
    public String getMaxKey() {
    
        return head.next.key;
    }
    
    /**
     * Returns one of the keys with Minimal value.
     */
    public String getMinKey() {
        return tail.prev.key;
    }
    
    private void removeNode(Node node){
    
        node.prev.next=node.next;
        node.next.prev=node.prev;
        node.prev=null;
        node.next=null;
    
    }
    
    private void addToTail(Node node) {
    
        tail.prev.next = node;
        node.prev = tail.prev;
    
        node.next = tail;
        tail.prev = node;
    
    
    }
    
    private void addToHead(Node node) {
    
        head.next.prev = node;
        node.next = head.next;
        node.prev = head;
        head.next = node;
    
    
    }
    private void addNextToHead(Node node) {
    
        head.next.next.prev = node;
        node.next = head.next.next;
        node.prev = head.next;
        head.next.next = node;
    
    
    }
    

    }


Log in to reply
 

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