Java O(1) Doubly link list :: Accepted


  • 2
    D
    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * Created by debabrata_sharma on 10/17/16.
     */
    public class AllOne {
    
        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 AllOne() {
    
            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;
    
    
        }
    }
    

  • 0
    A

    In this case, where you're checking if the decremented key is the current max, shouldn't you be checking if the value of the node is less than the value to its right (not the current max, because that's itself)? Correct me if i'm wrong

    '''

    if(node.key==head.next.key){
    if (node.val<=head.next.val) {
    removeNode(node);
    addNextToHead(node);
    }
    }
    '''


  • 0
    T

    This solution is wrong:

    Input:
    ["AllOne","inc","inc","inc","inc","inc","dec","dec","getMaxKey","getMinKey"]
    [[],["a"],["b"],["b"],["b"],["b"],["b"],["b"],[],[]]
    Output:
    [null,null,null,null,null,null,null,null,"a","b"]
    Expected:
    [null,null,null,null,null,null,null,null,"b","a"]

  • 0
    J

    This case makes your code not all O(1):
    inc("a")
    inc("b")
    inc("b")
    inc("a")
    inc("a")
    inc("b")
    inc("b")
    inc("a")
    inc("a")
    ...


Log in to reply
 

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