Leetcode #432: All O`one Data Structure
In this guide, we solve Leetcode #432 All O`one Data Structure in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Hard
- Premium: No
- Tags: Design, Hash Table, Linked List, Doubly-Linked List
Intuition
Fast membership checks and value lookups are the heart of this problem, which makes a hash map the natural choice.
By storing what we have already seen (or counts/indexes), we can answer the question in one pass without backtracking.
Approach
Scan the input once, using the map to detect when the condition is satisfied and to update state as you go.
This keeps the solution linear while remaining easy to explain in an interview setting.
Steps:
- Initialize a hash map for seen items or counts.
- Iterate through the input, querying/updating the map.
- Return the first valid result or the final computed value.
Example
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"
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
The time complexity is O(n). The space complexity is O(n).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.