HardNo. 0432
All O`one Data Structure — LeetCode 432 Python Solution
- Pattern
- Linked List
- Topics
- Design, Hash Table, Linked List, Doubly-Linked List
- Reading time
- 13 min
- Source
- leetcode.com
The 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.
Example
- Input
- ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
- Output
- [null, null, null, "hello", "hello", null, "hello", "leet"]
- Explanation
- AllOne allOne = new AllOne();
Python solution
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()Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 432. All O`one Data Structure is filed here because LeetCode tags it Linked List and Doubly-Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0146 | LRU Cache | Medium |
| 0460 | LFU Cache | Hard |
| 1797 | Design Authentication Manager | Medium |
| 0355 | Design Twitter | Medium |
| 0705 | Design HashSet | Easy |
| 0706 | Design HashMap | Easy |
Frequently asked questions
- How hard is LeetCode 432. All O`one Data Structure?
LeetCode 432. All O`one Data Structure is rated Hard on LeetCode.
- What is the time complexity of LeetCode 432. All O`one Data Structure?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 432. All O`one Data Structure?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 432. All O`one Data Structure cover?
LeetCode 432. All O`one Data Structure is tagged Design, Hash Table, Linked List and Doubly-Linked List on LeetCode.