# 98ms, Java solution using HashMap and DoubleLinkedList

• ``````
public class AllOne {

/** Initialize your data structure here. */
String key;
int val;
public LinkedNode(String key, int val){ this.key = key; this.val = val;}
}

public AllOne() {
maps = new HashMap<>();
}

while(node.val>node.left.val){

node.left = leftNode.left;
leftNode.right = node.right;

node.left.right = node;
leftNode.right.left = leftNode;

node.right = leftNode;
leftNode.left = node;
}
}

}

while(node.val<node.right.val){

node.right = rightNode.right;
rightNode.left = node.left;

node.right.left = node;
rightNode.left.right = rightNode;

node.left = rightNode;
rightNode.right = node;
}
}

tail.left.right = node;
node.left = tail.left;

node.right = tail;
tail.left = 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)){
node.val++;
remove(node);
}else{
}

}else{
maps.put(key, 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;
if(node.val == 1){
maps.remove(key);
remove(node);
}else{
node.val--;
if(node.val < tail.left.val){
remove(node);
}else{
moveToTail(node);
}

}
}

/** Returns one of the keys with maximal value. */
public String getMaxKey() {
}

/** 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!

• 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.

["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"],[],[]]

• Thanks for pointing out, I will fix this.

• 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.

["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).

• @nightswatch

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

• 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;
}
``````

}

Map<String, Node> map;

/**

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

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

}

``````/**
* 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++;
removeNode(node);
}
} else {
Node node = new Node(key, 1);
map.put(key, 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);
}
removeNode(node);
}
}

}
} else {
return;
}

}

/**
* Returns one of the keys with maximal value.
*/
public String getMaxKey() {

}

/**
* 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;

}

tail.prev.next = node;
node.prev = tail.prev;

node.next = tail;
tail.prev = node;

}

}