1609. Key Counter Board
A quiz show tracks how many points each team name has collected on a live scoreboard. Design KeyCounterBoard, which starts empty. inc(key) adds one point to key, creating it with 1 point if it is new. dec(key) removes one point from key; a key that drops to 0 leaves the board, and calling dec on a key that is not on the board does nothing. getMaxKey() returns the key with the highest count, and getMinKey() returns the key with the lowest count; when several keys tie, return the lexicographically smallest of them. Both return the empty string when the board is empty. Keys are 1 to 10 lowercase letters and there are at most 2000 calls. Each call should take O(log n) time, using a linked list of count buckets.
Example 1
- Input:
- operations = ["KeyCounterBoard","inc","inc","inc","getMaxKey","getMinKey","dec","getMaxKey"]arguments = [[],["ab"],["ab"],["cd"],[],[],["ab"],[]]
- Output:
- [null,null,null,null,"ab","cd",null,"ab"]
- Explanation:
ab has 2 points and cd has 1; after a dec both have 1 and the smaller key ab is returned.
Example 2
- Input:
- operations = ["KeyCounterBoard","getMaxKey","getMinKey","dec","getMaxKey"]arguments = [[],[],[],["zz"],[]]
- Output:
- [null,"","",null,""]
- Explanation:
An empty board returns empty strings, and dec on an absent key changes nothing.
Constraints
1 ≤ key.length ≤ 10, lowercase letters
at most 2000 calls
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(log n) per call
- Space
- O(n)