# All O`one Data Structure
**Difficulty:** HARD
[External](https://leetcode.com/problems/all-oone-data-structure)
Canonical: https://scaleengineer.com/dsa/problems/all-oone-data-structure
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Hash Table, Linked List, Doubly-Linked List
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Atlassian](https://scaleengineer.com/companies/atlassian), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Media.net](https://scaleengineer.com/companies/media.net), [Nextdoor](https://scaleengineer.com/companies/nextdoor)
---
## Problem
Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the `AllOne` class:

* `AllOne()` Initializes the object of the data structure.
* `inc(String key)` Increments the count of the string `key` by `1`. If `key` does not exist in the data structure, insert it with count `1`.
* `dec(String key)` Decrements the count of the string `key` by `1`. If the count of `key` is `0` after the decrement, remove it from the data structure. It is guaranteed that `key` exists in the data structure before the decrement.
* `getMaxKey()` Returns one of the keys with the maximal count. If no element exists, return an empty string `""`.
* `getMinKey()` Returns one of the keys with the minimum count. If no element exists, return an empty string `""`.

**Note** that each function must run in `O(1)` average time complexity.

**Example 1:**

**Input**
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
**Output**
[null, null, null, "hello", "hello", null, "hello", "leet"]

**Explanation**
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "hello"
allOne.inc("leet");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "leet"

**Constraints:**

* `1 <= key.length <= 10`
* `key` consists of lowercase English letters.
* It is guaranteed that for each call to `dec`, `key` is existing in the data structure.
* At most `5 * 104` calls will be made to `inc`, `dec`, `getMaxKey`, and `getMinKey`.

# Approaches
## Brute Force with HashMap
This is a straightforward brute-force approach that uses a single HashMap to store the counts of the strings. While `inc` and `dec` operations are efficient, finding the key with the minimum or maximum count requires iterating through all the keys in the map, which is too slow for the problem's constraints.
**Time:** `inc` and `dec`: O(1) average time.
`getMaxKey` and `getMinKey`: O(N) time, where N is the number of unique keys. · **Space:** O(N), where N is the number of unique keys stored in the HashMap.
**Pros:** Very simple to understand and implement.; `inc` and `dec` operations are efficient (O(1) average time).
**Cons:** The `getMaxKey()` and `getMinKey()` methods are inefficient, with a time complexity of O(N).; This approach does not meet the O(1) time complexity requirement for all functions.
### Explanation
The core of this approach is a `HashMap<String, Integer>` which maps each string `key` to its frequency `count`. 

For `inc(key)` and `dec(key)`, we can leverage the HashMap's O(1) average time complexity for get and put operations. To increment, we fetch the current count, add one, and put it back. To decrement, we do the same but subtract one, and if the count reaches zero, we remove the key from the map.

The main drawback appears in `getMaxKey()` and `getMinKey()`. Since the counts in the HashMap are not stored in any particular order, the only way to find the minimum or maximum count is to perform a linear scan over all the entries in the map. We iterate through the map, comparing each key's count with the current minimum/maximum found so far, and update it if necessary. This leads to an O(N) time complexity, where N is the number of unique keys stored.

```java
import java.util.HashMap;
import java.util.Map;

class AllOne {
    private Map<String, Integer> counts;

    public AllOne() {
        counts = new HashMap<>();
    }
    
    public void inc(String key) {
        counts.put(key, counts.getOrDefault(key, 0) + 1);
    }
    
    public void dec(String key) {
        int count = counts.get(key);
        if (count == 1) {
            counts.remove(key);
        } else {
            counts.put(key, count - 1);
        }
    }
    
    public String getMaxKey() {
        if (counts.isEmpty()) {
            return "";
        }
        String maxKey = "";
        int maxVal = 0;
        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > maxVal) {
                maxVal = entry.getValue();
                maxKey = entry.getKey();
            }
        }
        return maxKey;
    }
    
    public String getMinKey() {
        if (counts.isEmpty()) {
            return "";
        }
        String minKey = "";
        int minVal = Integer.MAX_VALUE;
        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            if (entry.getValue() < minVal) {
                minVal = entry.getValue();
                minKey = entry.getKey();
            }
        }
        return minKey;
    }
}
```
### Algorithm
- Use a `HashMap<String, Integer>` to store the count for each string key.
- **`inc(key)`**: Retrieve the count of the key, increment it, and update the map. If the key doesn't exist, add it with a count of 1. This is an O(1) average time operation.
- **`dec(key)`**: Retrieve the count of the key, decrement it, and update the map. If the new count is 0, remove the key from the map. This is an O(1) average time operation.
- **`getMaxKey()` / `getMinKey()`**: Iterate through all the entries in the `HashMap`. Keep track of the maximum/minimum count seen so far and the corresponding key. Return the key associated with the final maximum/minimum count. This requires a full scan of all unique keys, making it an O(N) operation, where N is the number of unique keys.

## HashMap and Balanced Tree
This approach improves upon the brute-force method by using a balanced binary search tree (implemented as a `TreeSet` in Java) alongside a HashMap. The `TreeSet` keeps key-count pairs sorted by count, which makes finding the min and max keys an O(1) operation. However, the trade-off is that updating a key's count (`inc` and `dec`) now requires updating the `TreeSet`, which takes O(log N) time.
**Time:** `inc` and `dec`: O(log N) time.
`getMaxKey` and `getMinKey`: O(1) time. · **Space:** O(N), where N is the number of unique keys. Both the HashMap and TreeSet store N items.
**Pros:** Achieves O(1) time complexity for `getMaxKey` and `getMinKey`.; Conceptually simpler than the fully O(1) solution.
**Cons:** `inc` and `dec` operations have a time complexity of O(log N), which does not meet the strict O(1) requirement for all functions.
### Explanation
To optimize `getMaxKey` and `getMinKey`, we need a data structure that keeps track of the order of counts. A balanced binary search tree, such as Java's `TreeSet`, is a good candidate.

We use two data structures:
1.  `HashMap<String, Integer> keyToCount`: Same as before, for O(1) lookup of a key's count.
2.  `TreeSet<Pair<Integer, String>> sortedCounts`: This set stores pairs of `(count, key)`. It's ordered by count, and then by key lexicographically to handle ties and ensure uniqueness of pairs. 

When `inc(key)` is called, we must perform the following steps:
1.  Look up the old count in `keyToCount`.
2.  If the key existed, remove the `(oldCount, key)` pair from the `TreeSet`.
3.  Increment the count and update `keyToCount`.
4.  Insert the `(newCount, key)` pair into the `TreeSet`.

Both removal and insertion in a `TreeSet` take O(log N) time. The `dec` operation follows a similar logic. Because the `TreeSet` is always sorted, `getMinKey` can be found by looking at the first element (`treeSet.first()`) and `getMaxKey` by looking at the last element (`treeSet.last()`), both in O(1) time.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

class AllOne {
    // A helper class to store count and key, and define comparison logic.
    private static class Pair implements Comparable<Pair> {
        int count;
        String key;

        Pair(int count, String key) {
            this.count = count;
            this.key = key;
        }

        @Override
        public int compareTo(Pair other) {
            if (this.count == other.count) {
                return this.key.compareTo(other.key);
            }
            return Integer.compare(this.count, other.count);
        }
    }

    private Map<String, Integer> keyToCount;
    private TreeSet<Pair> sortedCounts;

    public AllOne() {
        keyToCount = new HashMap<>();
        sortedCounts = new TreeSet<>();
    }
    
    public void inc(String key) {
        int oldCount = keyToCount.getOrDefault(key, 0);
        int newCount = oldCount + 1;

        if (oldCount > 0) {
            sortedCounts.remove(new Pair(oldCount, key));
        }
        keyToCount.put(key, newCount);
        sortedCounts.add(new Pair(newCount, key));
    }
    
    public void dec(String key) {
        int oldCount = keyToCount.get(key);
        int newCount = oldCount - 1;

        sortedCounts.remove(new Pair(oldCount, key));
        if (newCount == 0) {
            keyToCount.remove(key);
        } else {
            keyToCount.put(key, newCount);
            sortedCounts.add(new Pair(newCount, key));
        }
    }
    
    public String getMaxKey() {
        if (sortedCounts.isEmpty()) {
            return "";
        }
        return sortedCounts.last().key;
    }
    
    public String getMinKey() {
        if (sortedCounts.isEmpty()) {
            return "";
        }
        return sortedCounts.first().key;
    }
}
```
### Algorithm
- Use a `HashMap<String, Integer>` to map keys to their counts.
- Use a `TreeSet` to store `(count, key)` pairs. The `TreeSet` will automatically keep these pairs sorted based on the count, allowing for fast retrieval of min and max elements.
- **`inc(key)`**: Get the old count from the HashMap. Remove the old `(count, key)` pair from the `TreeSet`. Update the count in the HashMap. Insert the new `(count+1, key)` pair into the `TreeSet`. This involves remove and add operations on the `TreeSet`, which take O(log N) time.
- **`dec(key)`**: Similar to `inc`, remove the old pair from the `TreeSet`, update the count in the HashMap, and insert the new `(count-1, key)` pair if the new count is greater than 0. This also takes O(log N) time.
- **`getMaxKey()`**: Return the key from the last element in the `TreeSet` (`treeSet.last()`). This is an O(1) operation.
- **`getMinKey()`**: Return the key from the first element in the `TreeSet` (`treeSet.first()`). This is an O(1) operation.

## HashMap and Doubly Linked List (All O(1) Solution)
This optimal approach achieves O(1) average time complexity for all operations by combining a HashMap with a custom doubly linked list. The core idea is to group keys with the same count into 'buckets'. These buckets are nodes in a doubly linked list, sorted by count. This structure allows for moving a key from one count group to an adjacent one (e.g., from count 5 to 6) in constant time, by just updating a few pointers and hash set entries.
**Time:** `inc`, `dec`, `getMaxKey`, and `getMinKey` all have an average time complexity of O(1). · **Space:** O(N + C), where N is the number of unique keys and C is the number of unique counts. In the worst case, C can be equal to N, so the complexity is O(N).
**Pros:** Achieves O(1) average time complexity for all required operations (`inc`, `dec`, `getMaxKey`, `getMinKey`).; The most efficient solution possible for the given constraints.
**Cons:** Significantly more complex to design and implement correctly.; Higher constant factor overhead due to managing multiple complex data structures.
### Explanation
This solution is built upon two main data structures:
1.  `HashMap<String, Bucket> keyToBucketMap`: This map provides O(1) access to the `Bucket` node that a given `key` currently belongs to.
2.  A Doubly Linked List of `Bucket`s: Each `Bucket` node in the list contains `int count` and `Set<String> keys`, where the set holds all keys that have that specific count. The list is maintained in ascending order of `count`. We use dummy `head` and `tail` nodes to simplify list manipulations and provide O(1) access to the minimum and maximum count buckets.

**How operations work:**
- **`inc(String key)`**: When a key's count increases from `c` to `c+1`, we need to move it from the bucket with count `c` to the bucket with count `c+1`. We find the `c+1` bucket, which must be immediately after the `c` bucket in our sorted list. If it doesn't exist, we create it and insert it in the correct position. Then, we move the key from the old bucket's `keys` set to the new one's and update the `keyToBucketMap`. If the old bucket becomes empty, we remove it from the list. All these steps—map lookups, set operations, and linked list pointer updates—are O(1) on average.

- **`dec(String key)`**: This is the reverse of `inc`. We move the key from bucket `c` to `c-1`. If the count drops to 0, we remove the key from `keyToBucketMap`. Again, we clean up any buckets that become empty.

- **`getMinKey()` / `getMaxKey()`**: Since the list is sorted by count, the bucket with the minimum count is always `head.next`, and the one with the maximum count is `tail.prev`. We can retrieve any key from the respective bucket's `keys` set in O(1) time.

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class AllOne {
    // Bucket node for the doubly linked list
    private static class Bucket {
        int count;
        Set<String> keys;
        Bucket prev;
        Bucket next;

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

    private Map<String, Bucket> keyToBucketMap;
    private Bucket head; // Dummy head
    private Bucket tail; // Dummy tail

    public AllOne() {
        keyToBucketMap = new HashMap<>();
        head = new Bucket(0);
        tail = new Bucket(0);
        head.next = tail;
        tail.prev = head;
    }

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

    private void insertAfter(Bucket newBucket, Bucket prevBucket) {
        newBucket.prev = prevBucket;
        newBucket.next = prevBucket.next;
        prevBucket.next.prev = newBucket;
        prevBucket.next = newBucket;
    }

    public void inc(String key) {
        Bucket currentBucket = keyToBucketMap.getOrDefault(key, head);
        int newCount = currentBucket.count + 1;

        Bucket nextBucket = currentBucket.next;
        if (nextBucket.count != newCount) {
            nextBucket = new Bucket(newCount);
            insertAfter(nextBucket, currentBucket);
        }

        nextBucket.keys.add(key);
        keyToBucketMap.put(key, nextBucket);

        if (currentBucket != head) {
            currentBucket.keys.remove(key);
            if (currentBucket.keys.isEmpty()) {
                removeBucket(currentBucket);
            }
        }
    }

    public void dec(String key) {
        Bucket currentBucket = keyToBucketMap.get(key);
        currentBucket.keys.remove(key);
        int newCount = currentBucket.count - 1;

        if (newCount > 0) {
            Bucket prevBucket = currentBucket.prev;
            if (prevBucket.count != newCount) {
                prevBucket = new Bucket(newCount);
                insertAfter(prevBucket, currentBucket.prev);
            }
            prevBucket.keys.add(key);
            keyToBucketMap.put(key, prevBucket);
        } else {
            keyToBucketMap.remove(key);
        }

        if (currentBucket.keys.isEmpty()) {
            removeBucket(currentBucket);
        }
    }

    public String getMaxKey() {
        if (tail.prev == head) {
            return "";
        }
        return tail.prev.keys.iterator().next();
    }

    public String getMinKey() {
        if (head.next == tail) {
            return "";
        }
        return head.next.keys.iterator().next();
    }
}
```
### Algorithm
- Use a `HashMap<String, Bucket>` to map each key to a `Bucket` node in a doubly linked list.
- The doubly linked list contains `Bucket` nodes. Each `Bucket` represents a specific count and holds a `Set<String>` of all keys with that count.
- The list of buckets is kept sorted by count. We use `head` and `tail` dummy nodes to easily find the min and max buckets (`head.next` and `tail.prev`).
- **`inc(key)`**: 
  1. Find the key's current bucket. Let its count be `c`.
  2. Look for the bucket for count `c+1`, which should be `currentBucket.next`.
  3. If `currentBucket.next` is not for count `c+1`, create a new bucket for `c+1` and insert it.
  4. Move the key from the current bucket's set to the new bucket's set.
  5. Update the key's mapping in the HashMap to point to the new bucket.
  6. If the old bucket becomes empty, remove it from the list.
- **`dec(key)`**: Works similarly to `inc`, but moves the key to the bucket for count `c-1` (the `prev` bucket). If the count becomes 0, the key is removed entirely. Empty buckets are cleaned up.
- **`getMaxKey()`**: Return any key from the set in the bucket `tail.prev`.
- **`getMinKey()`**: Return any key from the set in the bucket `head.next`.

# Solutions
### Java

```java
class AllOne { Node root = new Node (); Map < String , Node > nodes = new HashMap <>(); public AllOne () { root . next = root ; root . prev = root ; } public void inc ( String key ) { if (! nodes . containsKey ( key )) { if ( root . next == root || root . next . cnt > 1 ) { nodes . put ( key , root . insert ( new Node ( key , 1 ))); } else { root . next . keys . add ( key ); nodes . put ( key , root . next ); } } else { Node curr = nodes . get ( key ); Node next = curr . next ; if ( next == root || next . cnt > curr . cnt + 1 ) { nodes . put ( key , curr . insert ( new Node ( key , curr . cnt + 1 ))); } else { next . keys . add ( key ); nodes . put ( key , next ); } curr . keys . remove ( key ); if ( curr . keys . isEmpty ()) { curr . remove (); } } } public void dec ( String key ) { Node curr = nodes . get ( key ); if ( curr . cnt == 1 ) { nodes . remove ( key ); } else { Node prev = curr . prev ; if ( prev == root || prev . cnt < curr . cnt - 1 ) { nodes . put ( key , prev . insert ( new Node ( key , curr . cnt - 1 ))); } else { prev . keys . add ( key ); nodes . put ( key , prev ); } } curr . keys . remove ( key ); if ( curr . keys . isEmpty ()) { curr . remove (); } } public String getMaxKey () { return root . prev . keys . iterator (). next (); } public String getMinKey () { return root . next . keys . iterator (). next (); } } class Node { Node prev ; Node next ; int cnt ; Set < String > keys = new HashSet <>(); public Node () { this ( "" , 0 ); } public Node ( String key , int cnt ) { this . cnt = cnt ; keys . add ( key ); } public Node insert ( Node node ) { node . prev = this ; node . next = this . next ; node . prev . next = node ; node . next . prev = node ; return node ; } public void remove () { this . prev . next = this . next ; this . next . prev = this . prev ; } } /** * 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(); */
```

### Python

```python
class Node : def __init__ ( self , key = '' , cnt = 0 ): self . prev = None self . next = None self . cnt = cnt self . keys = { key } def insert ( self , node ): node . prev = self node . next = self . next node . prev . next = node node . next . prev = node return node def remove ( self ): self . prev . next = self . next self . next . prev = self . prev class AllOne : def __init__ ( self ): self . root = Node () self . root . next = self . root self . root . prev = self . root self . nodes = {} def inc ( self , key : str ) -> None : root , nodes = self . root , self . nodes if key not in nodes : if root . next == root or root . next . cnt > 1 : nodes [ key ] = root . insert ( Node ( key , 1 )) else : root . next . keys . add ( key ) nodes [ key ] = root . next else : curr = nodes [ key ] next = curr . next if next == root or next . cnt > curr . cnt + 1 : nodes [ key ] = curr . insert ( Node ( key , curr . cnt + 1 )) else : next . keys . add ( key ) nodes [ key ] = next curr . keys . discard ( key ) if not curr . keys : curr . remove () def dec ( self , key : str ) -> None : root , nodes = self . root , self . nodes curr = nodes [ key ] if curr . cnt == 1 : nodes . pop ( key ) else : prev = curr . prev if prev == root or prev . cnt < curr . cnt - 1 : nodes [ key ] = prev . insert ( Node ( key , curr . cnt - 1 )) else : prev . keys . add ( key ) nodes [ key ] = prev curr . keys . discard ( key ) if not curr . keys : curr . remove () def getMaxKey ( self ) -> str : return next ( iter ( self . root . prev . keys )) def getMinKey ( self ) -> str : return next ( iter ( self . root . next . keys )) # Your AllOne object will be instantiated and called as such: # obj = AllOne() # obj.inc(key) # obj.dec(key) # param_3 = obj.getMaxKey() # param_4 = obj.getMinKey()
```