# All O(1) one Data Structure

This page explains Java solution to problem `All O(1) one Data Structure` using `HashMap` data structure.

## Problem Statement

Implement a data structure supporting the following operations:

• 1. `Inc(Key)` - Inserts a new key with value `1`. Or increments an existing key by `1`. Key is guaranteed to be a non-empty string.
• 2. `Dec(Key)` - If Key's value is `1`, remove it from the data structure. Otherwise decrements an existing key by `1`. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
• 3. `GetMaxKey()` - Returns one of the keys with maximal value. If no element exists, return an empty string "".
• 4. `GetMinKey()` - Returns one of the keys with minimal value. If no element exists, return an empty string "".

Perform all these in `O(1)` time complexity.

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class AllOOneDataStructure {
static class Bucket {
Bucket prev;
Bucket next;
int count;
HashSet<String> keys;

Bucket(int count) {
this.count = count;
keys = new HashSet<>();
}

@Override
public String toString() {
return "[ "+count+ " "+ keys+" ]";
}
}

private HashMap<String, Bucket> keyMap;

/** Initialize your data structure here. */
public AllOOneDataStructure() {
keyMap = new HashMap<>();
tail = new Bucket(-1);
}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
public void inc(String key) {
if(!keyMap.containsKey(key)) {
}
else {
}
}
else {
Bucket oldBucket = keyMap.get(key);
oldBucket.keys.remove(key);
if(oldBucket.count + 1 == oldBucket.next.count) {
keyMap.put(key, oldBucket.next);
}
else {
}
if(oldBucket.keys.size() == 0) removeBucket(oldBucket);
}
}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
public void dec(String key) {
if(keyMap.containsKey(key)) {
Bucket oldBucket = keyMap.get(key);
oldBucket.keys.remove(key);

if(oldBucket.count - 1 == 0) {
keyMap.remove(key);
if(oldBucket.keys.size() == 0) removeBucket(oldBucket);
}
else {
if(oldBucket.count - 1 == oldBucket.prev.count) {
keyMap.put(key, oldBucket.prev);
}
else {
}
if(oldBucket.keys.size() == 0) removeBucket(oldBucket);
}
}
}

/** Returns one of the keys with maximal value. */
public String getMaxKey() {
if(tail.prev != head && tail.prev.keys != null && tail.prev.keys.size() > 0)
return tail.prev.keys.iterator().next();
else return "";
}

/** Returns one of the keys with Minimal value. */
public String getMinKey() {
else return "";
}

private Bucket addBucketAfter(Bucket bucket, int val) {

Bucket next = bucket.next;

}

private void removeBucket(Bucket bucket) {
Bucket prev = bucket.prev;
Bucket next = bucket.next;

prev.next = next;
next.prev = prev;
}
}

/**
* Your AllOne object will be instantiated and called as such:
* AllOOneDataStructure obj = new AllOOneDataStructure();
* obj.inc(key);
* obj.dec(key);
* String param_3 = obj.getMaxKey();
* String param_4 = obj.getMinKey();
*/
``````

O(1)

## Space Complexity

O(N) Where
N is total number of elements in O`One Data Structure.