LeetCode 432: All O`one Data Structure Solution in Python – A Step-by-Step Guide

What Is LeetCode 432: All O`one Data Structure?

In **LeetCode 432: All Oone Data Structure**, you need to design a classAllOnewith four methods: 1. **inc(key)**: Increment the count of a key by 1 (add if new). 2. **dec(key)**: Decrement the count of a key by 1 (remove if 0). 3. **getMaxKey()**: Return a key with the maximum frequency (any if tied, "" if empty). 4. **getMinKey()**: Return a key with the minimum frequency (any if tied, "" if empty). The structure must handle these operations efficiently. For example, starting empty,inc("Alice")→ Alice:1,inc("Bob")→ Alice:1, Bob:1,inc("Alice")→ Alice:2, Bob:1,getMaxKey()returns "Alice",getMinKey()` returns "Bob". It’s like a dynamic frequency tracker with instant max/min lookups.

Problem Statement

• Input: Method calls with string keys.
• Output:
• inc, dec: None (modify structure).
• getMaxKey, getMinKey: String (key or "").
• Rules:
• Track frequency of keys.
• Efficiently update counts and retrieve max/min keys.
• Handle ties by returning any valid key.

Constraints

• Number of operations is in range [1, 10⁵].
• Key length ≤ 10.
• Keys consist of lowercase English letters.

Examples

• Input: ["AllOne","inc","inc","getMaxKey","getMinKey","inc","getMaxKey","getMinKey"]
• Args: [[]["hello"],["hello"],[],[],["world"],[],[]]
• Output: [null,null,null,"hello","hello",null,"hello","world"]
• Explanation: Empty → hello:1 → hello:2 → max "hello" → min "hello" → hello:2, world:1 → max "hello" → min "world".
• Input: ["AllOne","inc","dec","getMaxKey"]
• Args: [[]["foo"],["foo"],[]]
• Output: [null,null,null,""]
• Explanation: Empty → foo:1 → foo:0 (removed) → max "".

Understanding the Problem: Tracking Frequencies

To solve LeetCode 432: All O`one Data Structure in Python, we need a data structure that: 1. Tracks key frequencies. 2. Updates counts in O(1) or near-O(1) time. 3. Retrieves max and min frequency keys quickly. A naive idea might be a hash map with counts—but finding max/min would take O(n) each time! We’ll use:

• Best Solution (Doubly Linked List with Hash Map): O(1) time per operation, O(n) space—optimal efficiency.
• Alternative Solution (Heap with Hash Map): O(log n) for inc/dec, O(1) for getMax/getMin, O(n) space—heap-based.

Let’s dive into the doubly linked list solution with a clear, step-by-step explanation.

Best Solution: Doubly Linked List with Hash Map

Why This Is the Best Solution

The doubly linked list with hash map method is the top pick because it’s ultra-efficient—O(1) time for all operations (inc, dec, getMaxKey, getMinKey), O(n) space—and brilliantly balances frequency tracking with instant max/min access. It uses a doubly linked list of frequency buckets (nodes with count and key set), where each bucket links to the previous and next frequency, and a hash map maps keys to their bucket. This setup keeps max and min at the list’s ends, making updates and queries lightning-fast. It’s like organizing players into score groups, instantly spotting the highest and lowest scorers!

How It Works

Think of it as a scoreboard with frequency tiers:

• Structure:
• Bucket: Doubly linked node with count (frequency), keys (set of keys at this count), prev, next.
• Hash Map: Maps key to its bucket (key: bucket).
• List: Head (min freq), Tail (max freq), dummy nodes for empty cases.
• Inc(key):
• If new key, add to bucket with count 1 (after head).
• If exists, move from current bucket (count c) to next (c+1), create if needed.
• Update bucket links, remove empty buckets.
• Dec(key):
• Move from current bucket (count c) to prev (c-1), remove if 0.
• Update links, clean up empty buckets.
• GetMaxKey(): Return any key from tail’s keys.
• GetMinKey(): Return any key from head’s next bucket (if exists).

Why It Works

• O(1) updates: Hash map finds bucket, list moves key to adjacent bucket.
• O(1) max/min: Head/tail always point to min/max frequencies.
• It’s like a live leaderboard with instant updates and lookups!

Step-by-Step Example

Example: ["AllOne","inc","inc","inc","getMaxKey","dec","getMinKey"] with ["hello"],["hello"],["world"],[],["hello"],[]

• Initial: head ↔ tail, map = {}.
• Inc("hello"):
• Map: "hello" not found, head.next = bucket(1, {"hello"}), map["hello"] = bucket(1).
• head ↔ bucket(1, {"hello"}) ↔ tail.
• Inc("hello"):
• Bucket(1): Remove "hello", add to bucket(2, {"hello"}), map["hello"] = bucket(2).
• head ↔ bucket(2, {"hello"}) ↔ tail.
• Inc("world"):
• New bucket(1, {"world"}), insert after head, map["world"] = bucket(1).
• head ↔ bucket(1, {"world"}) ↔ bucket(2, {"hello"}) ↔ tail.
• GetMaxKey(): Tail.prev = bucket(2), return "hello".
• Dec("hello"):
• Bucket(2): Remove "hello", add to bucket(1), update map["hello"] = bucket(1).
• head ↔ bucket(1, {"world", "hello"}) ↔ tail.
• GetMinKey(): Head.next = bucket(1), return "world" (or "hello").
• Result: Matches expected output.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Bucket:
    def __init__(self, count):
        self.count = count
        self.keys = set()
        self.prev = None
        self.next = None

class AllOne:
    def __init__(self):
        # Step 1: Initialize dummy head and tail
        self.head = Bucket(0)  # Min sentinel
        self.tail = Bucket(float('inf'))  # Max sentinel
        self.head.next = self.tail
        self.tail.prev = self.head
        self.key_to_bucket = {}  # Map key to its bucket

    def _remove_bucket(self, bucket):
        # Remove empty bucket from list
        if not bucket.keys:
            bucket.prev.next = bucket.next
            bucket.next.prev = bucket.prev

    def _insert_bucket(self, new_bucket, after):
        # Insert new bucket after 'after'
        new_bucket.next = after.next
        new_bucket.prev = after
        after.next.prev = new_bucket
        after.next = new_bucket

    def inc(self, key: str) -> None:
        # Step 2: Increment key count
        if key not in self.key_to_bucket:
            # New key, use or create count 1 bucket
            if self.head.next.count == 1:
                self.head.next.keys.add(key)
            else:
                new_bucket = Bucket(1)
                new_bucket.keys.add(key)
                self._insert_bucket(new_bucket, self.head)
            self.key_to_bucket[key] = self.head.next
        else:
            curr_bucket = self.key_to_bucket[key]
            next_count = curr_bucket.count + 1
            curr_bucket.keys.remove(key)

            # Move to next bucket or create it
            if curr_bucket.next.count == next_count:
                curr_bucket.next.keys.add(key)
                self.key_to_bucket[key] = curr_bucket.next
            else:
                new_bucket = Bucket(next_count)
                new_bucket.keys.add(key)
                self._insert_bucket(new_bucket, curr_bucket)
                self.key_to_bucket[key] = new_bucket

            self._remove_bucket(curr_bucket)

    def dec(self, key: str) -> None:
        # Step 3: Decrement key count
        if key not in self.key_to_bucket:
            return

        curr_bucket = self.key_to_bucket[key]
        curr_bucket.keys.remove(key)

        if curr_bucket.count == 1:
            # Remove key entirely
            del self.key_to_bucket[key]
        else:
            prev_count = curr_bucket.count - 1
            if curr_bucket.prev.count == prev_count:
                curr_bucket.prev.keys.add(key)
                self.key_to_bucket[key] = curr_bucket.prev
            else:
                new_bucket = Bucket(prev_count)
                new_bucket.keys.add(key)
                self._insert_bucket(new_bucket, curr_bucket.prev)
                self.key_to_bucket[key] = new_bucket

        self._remove_bucket(curr_bucket)

    def getMaxKey(self) -> str:
        # Step 4: Get key with max frequency
        if self.tail.prev == self.head:
            return ""
        return next(iter(self.tail.prev.keys))

    def getMinKey(self) -> str:
        # Step 5: Get key with min frequency
        if self.head.next == self.tail:
            return ""
        return next(iter(self.head.next.keys))

• Line 1-6: Bucket class:
• count: Frequency value.
• keys: Set of keys at this frequency.
• prev, next: Doubly linked pointers.
• Line 9-15: __init__:
• Dummy head (0), tail (inf) for min/max ends.
• Link head ↔ tail.
• key_to_bucket: Map keys to buckets.
• Line 17-20: _remove_bucket:
• Remove empty bucket from list.
• Line 22-26: _insert_bucket:
• Insert new bucket after specified node.
• Line 28-53: inc(key):
• Line 30-36: New key → bucket(1).
• Line 38-52: Existing key → move to next count, update map, clean up.
• Line 55-77: dec(key):
• Line 58-61: Remove if count = 1.
• Line 62-76: Move to prev count, update map, clean up.
• Line 79-83: getMaxKey:
• Return any key from tail.prev (max freq), "" if empty.
• Line 85-89: getMinKey:
• Return any key from head.next (min freq), "" if empty.
• Time Complexity: O(1) per operation—constant-time updates and lookups.
• Space Complexity: O(n)—buckets and map store n keys.

This is like a live frequency leaderboard with instant updates!

Alternative Solution: Heap with Hash Map

Why an Alternative Approach?

The heap with hash map method uses two heaps (max and min) to track frequencies, paired with a hash map for counts. It’s O(log n) for inc/dec (heap operations), O(1) for getMax/getMin, and O(n) space—less optimal but leverages heap properties. It’s like sorting scores in real-time with a priority queue!

How It Works

• Structure:
• Max heap: (count, key) for max freq.
• Min heap: (count, key) for min freq.
• Hash map: key → count.
• Inc: Update map, push to heaps.
• Dec: Update map, push to heaps, remove if 0.
• GetMax/Min: Pop invalid entries, return top key.

Step-by-Step Example (Simplified)

Example: inc("a"), inc("b"), inc("a")

• Map: a:1, b:1 → a:2, b:1.
• Max Heap: [(2,"a"),(1,"b")], Min Heap: [(1,"b"),(2,"a")].
• GetMax: "a", GetMin: "b".

Code for Heap Approach (Simplified)

Copy codefrom heapq import heappush, heappop

class AllOne:
    def __init__(self):
        self.counts = {}  # key -> count
        self.max_heap = []  # (-count, key)
        self.min_heap = []  # (count, key)

    def inc(self, key: str) -> None:
        self.counts[key] = self.counts.get(key, 0) + 1
        heappush(self.max_heap, (-self.counts[key], key))
        heappush(self.min_heap, (self.counts[key], key))

    def dec(self, key: str) -> None:
        if key in self.counts:
            self.counts[key] -= 1
            if self.counts[key] == 0:
                del self.counts[key]
            else:
                heappush(self.max_heap, (-self.counts[key], key))
                heappush(self.min_heap, (self.counts[key], key))

    def getMaxKey(self) -> str:
        while self.max_heap and (-self.max_heap[0][0], self.max_heap[0][1]) not in self.counts.items():
            heappop(self.max_heap)
        return self.max_heap[0][1] if self.max_heap else ""

    def getMinKey(self) -> str:
        while self.min_heap and (self.min_heap[0][0], self.min_heap[0][1]) not in self.counts.items():
            heappop(self.min_heap)
        return self.min_heap[0][1] if self.min_heap else ""

• Time Complexity: O(log n) inc/dec, O(1) getMax/getMin (amortized).
• Space Complexity: O(n)—heaps and map.

It’s a heap-driven tracker!

Comparing the Two Solutions

• Doubly Linked List with Hash Map (Best):
• Pros: O(1) all operations, O(n) space, optimal.
• Cons: Complex structure.
• Heap with Hash Map (Alternative):
• Pros: O(log n) updates, O(1) queries, simpler concept.
• Cons: Slower updates, heap cleanup.

Linked list wins for speed.

Additional Examples and Edge Cases

• Empty: "" for max/min.
• Single key: Same key for max/min.
• Ties: Any key valid.

Linked list handles all.

Complexity Breakdown

• Linked List: Time O(1), Space O(n).
• Heap: Time O(log n) inc/dec, O(1) queries, Space O(n).

Linked list is superior.

Key Takeaways

• Linked List: Instant everything!
• Heap: Priority power!
• Frequencies: Structure matters.
• Python Tip: Sets rock—see [Python Basics](/python/basics).

Final Thoughts: Master That Structure

LeetCode 432: All O`one Data Structure in Python is a frequency-tracking adventure. Doubly linked list with hash map nails it fast, while heap with hash map prioritizes it steady. Want more data structure fun? Try LeetCode 146: LRU Cache or LeetCode 295: Find Median from Data Stream. Ready to track? Head to Solve LeetCode 432 on LeetCode and master that structure today!