All O'One Data Structure Problem


Description

LeetCode Problem 432.

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 “”.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 * 10^4calls will be made to inc, dec, getMaxKey, and getMinKey.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class AllOne {
public:
    map<string, int> mp;
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> mini;
    priority_queue<pair<int, string>> maxi;
    
    
    AllOne(){
        
    }
    
    void inc(string key) {
        mp[key]++;
        mini.push({mp[key], key});
        maxi.push({mp[key], key});
    }
    
    void dec(string key) {
        mp[key]--;
        mini.push({mp[key], key});
        maxi.push({mp[key], key});
    }
    
    string getMaxKey() {
        while(maxi.size()){
            if(maxi.top().first == mp[maxi.top().second] && mp[maxi.top().second]){
                return maxi.top().second;
                break;
            }else{
                maxi.pop();
            }
        }return "";
    }
    
    string getMinKey() {
        while(mini.size()){
            if(mini.top().first == mp[mini.top().second] && mp[mini.top().second]){
                return mini.top().second;
                break;
            }else{
                mini.pop();
            }
        }return "";
    }
};


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




Related Posts

All O'One Data Structure Problem

LeetCode 432. Design a data structure to store the strings...

Add Two Numbers II Problem

LeetCode 445. You are given two non-empty linked lists representing...

Remove Linked List Elements Problem

LeetCode 203. Given the head of a linked list and...

Odd Even Linked List Problem

LeetCode 328. Given the head of a singly linked list,...

Linked List Random Node Problem

LeetCode 382. Given a singly linked list, return a random...