432. All O`one Data Structure

Description

The AllOne data structure allows efficient operations to keep track of keys with integer counts. The supported operations include incrementing or decrementing the count of a key, as well as retrieving the key with the minimum and maximum count. The main challenge is to maintain the order of keys by their counts, ensuring that all operations are performed efficiently.

Intuition

The problem can be thought of as maintaining a dynamic list of keys, where each key has an associated count. The goal is to efficiently update the count of a key and maintain the order of the keys based on their count. Additionally, we need to quickly retrieve the minimum and maximum count keys.

The use of a hashmap (for counting) and a list (for ordered keys) allows us to keep track of both the count and the ordering dynamically.

Approach

1. Data Structures: - Use a hashmap (hash) to store the count of each key. - Use a list (keys) to store the keys in order based on their counts.
2. Increment Operation: - When incrementing a key, increase its count in the hashmap. - Remove the key from the current position in the ordered list and re-insert it at the correct position based on its new count using binary search.
3. Decrement Operation: - When decrementing a key, decrease its count in the hashmap. - If the count becomes zero, remove the key from the hashmap and the list. - Otherwise, remove the key from its current position in the list and re-insert it at the correct position using binary search.
4. Get Minimum/Maximum Key: - The first element of the list represents the key with the minimum count, and the last element represents the key with the maximum count. Return these accordingly.

Complexity

• Time Complexity: - inc() and dec(): Each involves removing and re-inserting a key in the list, which is done in O(log n) time using binary search. - getMinKey() and getMaxKey(): Both are O(1) operations since the minimum and maximum keys are always at the start and end of the list.
• Space Complexity: - O(n), where n is the number of unique keys being tracked. The hashmap stores counts for each key, and the list stores the ordered keys.

Code

C++

class AllOne {
    unordered_map hash;
    vector keys;

public:
    AllOne() {}

    void inc(string key) {
        if (hash.find(key) == hash.end()) {
            hash[key] = 0;
            keys.push_back(key);
        }
        hash[key]++;

        int value = hash[key];

        // Find the current key and erase it safely
        auto it = find(keys.begin(), keys.end(), key);
        if (it != keys.end()) keys.erase(it);

        // Perform binary search to insert at correct position
        int low = 0, high = keys.size();
        while (low < high) {
            int mid = (low + high) / 2;
            if (hash[keys[mid]] < value) low = mid + 1;
            else high = mid;
        }
        keys.insert(keys.begin() + low, key);
    }

    void dec(string key) {
        hash[key]--;
        if (hash[key] == 0) {
            // Erase key from both hash and keys vector
            hash.erase(key);
            auto it = find(keys.begin(), keys.end(), key);
            if (it != keys.end()) keys.erase(it);
        } else {
            int value = hash[key];

            // Find and erase the current key from vector
            auto it = find(keys.begin(), keys.end(), key);
            if (it != keys.end()) keys.erase(it);

            // Perform binary search to insert at correct position
            int low = 0, high = keys.size();
            while (low < high) {
                int mid = (low + high) / 2;
                if (hash[keys[mid]] < value) low = mid + 1;
                else high = mid;
            }
            keys.insert(keys.begin() + low, key);
        }
    }

    string getMinKey() {
        return keys.empty() ? "" : keys[0];
    }

    string getMaxKey() {
        return keys.empty() ? "" : keys.back();
    }
};

Python

class AllOne:

    def __init__(self):
        self.hash = {}
        self.keys = []

    def inc(self, key: str) -> None:
        if key not in self.hash:
            self.hash[key] = 0
            self.keys.append(key)
        self.hash[key] += 1

        value = self.hash[key]
        self.keys.remove(key)
        low, high = 0, len(self.keys)
        while low < high:
            mid = (low + high) // 2
            if self.hash[self.keys[mid]] < value:
                low = mid + 1
            else:
                high = mid
        self.keys.insert(low, key)

    def dec(self, key: str) -> None:
        self.hash[key] -= 1
        if self.hash[key] == 0:
            del self.hash[key]
            self.keys.remove(key)
        else:
            value = self.hash[key]
            self.keys.remove(key)
            low, high = 0, len(self.keys)
            while low < high:
                mid = (low + high) // 2
                if self.hash[self.keys[mid]] < value:
                    low = mid + 1
                else:
                    high = mid
            self.keys.insert(low, key)

    def getMinKey(self) -> str:
        return self.keys[0] if self.keys else ""

    def getMaxKey(self) -> str:
        return self.keys[-1] if self.keys else ""

Java

class AllOne {
    private Map hash;
    private List keys;

    public AllOne() {
        hash = new HashMap<>();
        keys = new ArrayList<>();
    }

    public void inc(String key) {
        if (!hash.containsKey(key)) {
            hash.put(key, 0);
            keys.add(key);
        }
        hash.put(key, hash.get(key) + 1);

        int value = hash.get(key);
        keys.remove(key);  // Remove the key from the current position

        // Perform binary search to insert at correct position
        int low = 0, high = keys.size();
        while (low < high) {
            int mid = (low + high) / 2;
            if (hash.get(keys.get(mid)) < value) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        keys.add(low, key);  // Insert key at the new correct position
    }

    public void dec(String key) {
        if (!hash.containsKey(key)) return;

        hash.put(key, hash.get(key) - 1);
        if (hash.get(key) == 0) {
            hash.remove(key);
            keys.remove(key);  // Safely remove the key if its value is 0
        } else {
            int value = hash.get(key);
            keys.remove(key);  // Remove the key from its current position

            // Perform binary search to insert at correct position
            int low = 0, high = keys.size();
            while (low < high) {
                int mid = (low + high) / 2;
                if (hash.get(keys.get(mid)) < value) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            keys.add(low, key);  // Reinsert the key at the correct position
        }
    }

    public String getMinKey() {
        return keys.isEmpty() ? "" : keys.get(0);  // Return the first key or an empty string if list is empty
    }

    public String getMaxKey() {
        return keys.isEmpty() ? "" : keys.get(keys.size() - 1);  // Return the last key or an empty string if list is empty
    }
}

JavaScript

class AllOne {

    constructor() {
        this.hash = {};
        this.keys = [];
    }
    
     inc(key) {
        if(!this.hash[key]) {
            this.hash[key] = 0;
            this.keys.push(key);
            
        }
        this.hash[key]++;

        var low = 0, 
        high = this.keys.length,
        value = this.hash[key];
        this.keys.splice(this.keys.indexOf(key),1);
        while (low < high) {
            var mid = low + high >>> 1;
            if (this.hash[this.keys[mid]] < value) low = mid + 1;
            else high = mid;
        }
        
        this.keys.splice(low,0,key)
    
     }

     dec(key) {
        this.hash[key]--;
        if(!this.hash[key]){
           this.hash[key] = undefined;
            this.keys.splice(this.keys.indexOf(key),1);
        } else {
                   var low = 0, 
        high = this.keys.length,
        value = this.hash[key];
        this.keys.splice(this.keys.indexOf(key),1);
        while (low < high) {
            var mid = low + high >>> 1;
            if (this.hash[this.keys[mid]] < value) low = mid + 1;
            else high = mid;
        }
        
        this.keys.splice(low,0,key)
        } 
     }

     getMinKey() {
        //console.log(this.keys)
        return this.keys[0] || '';
     }

     getMaxKey() {
        return this.keys[this.keys.length - 1] || '';
     }
}