Introduction

In this blog post, we will explore how to solve the LeetCode problem "432" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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. 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 "". Note that each function must run in O(1) average time complexity. Example 1: 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 * 104 calls will be made to inc, dec, getMaxKey, and getMinKey.

Explanation

Here's a solution to the AllOne problem with O(1) average time complexity for all operations, along with an explanation of the approach and complexity analysis.

High-Level Approach:

• Doubly Linked List of Buckets: Use a doubly linked list where each node (bucket) stores strings with the same count. This allows for quick updates when incrementing or decrementing counts.
• Hash Maps for String Counts and Bucket Lookup: Employ two hash maps: one to store the count of each string and another to store the bucket in which a given string resides. This provides O(1) average time access for string counts and bucket retrieval.
• Efficient Bucket Management: When incrementing/decrementing counts, move strings between buckets or create/delete buckets as needed, maintaining the sorted order of buckets based on count.

Complexity:

• Runtime Complexity: O(1) average time for inc, dec, getMaxKey, and getMinKey.
• Storage Complexity: O(N), where N is the number of unique strings added to the data structure.

Code

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

class AllOne:

    def __init__(self):
        self.key_counts = {}  # string -> count
        self.key_buckets = {}  # string -> Bucket
        self.head = Bucket(float('-inf'))
        self.tail = Bucket(float('inf'))
        self.head.next = self.tail
        self.tail.prev = self.head

    def inc(self, key: str) -> None:
        if key not in self.key_counts:
            self.key_counts[key] = 0

        self.key_counts[key] += 1
        count = self.key_counts[key]

        if key in self.key_buckets:
            old_bucket = self.key_buckets[key]
            old_bucket.keys.remove(key)

            if count in self.key_buckets:
                new_bucket = self.key_buckets[count]
            else:
                new_bucket = Bucket(count)
                self._add_bucket_after(new_bucket, old_bucket)
                self.key_buckets[count] = new_bucket

            new_bucket.keys.add(key)
            self.key_buckets[key] = new_bucket

            if not old_bucket.keys:
                self._remove_bucket(old_bucket)
        else:
            if 1 in self.key_buckets:
                new_bucket = self.key_buckets[1]
            else:
                new_bucket = Bucket(1)
                self._add_bucket_after(new_bucket, self.head)
                self.key_buckets[1] = new_bucket
            new_bucket.keys.add(key)
            self.key_buckets[key] = new_bucket


    def dec(self, key: str) -> None:
        count = self.key_counts[key]

        old_bucket = self.key_buckets[key]
        old_bucket.keys.remove(key)

        if count == 1:
            del self.key_counts[key]
            del self.key_buckets[key]
        else:
            self.key_counts[key] -= 1
            new_count = count - 1
            if new_count in self.key_buckets:
                new_bucket = self.key_buckets[new_count]
            else:
                new_bucket = Bucket(new_count)
                self._add_bucket_after(new_bucket, old_bucket.prev)
                self.key_buckets[new_count] = new_bucket

            new_bucket.keys.add(key)
            self.key_buckets[key] = new_bucket
            self.key_counts[key] = new_count

        if not old_bucket.keys:
            self._remove_bucket(old_bucket)

    def _add_bucket_after(self, bucket, prev_bucket):
        bucket.prev = prev_bucket
        bucket.next = prev_bucket.next
        prev_bucket.next.prev = bucket
        prev_bucket.next = bucket

    def _remove_bucket(self, bucket):
        del self.key_buckets[bucket.count]
        bucket.prev.next = bucket.next
        bucket.next.prev = bucket.prev


    def getMaxKey(self) -> str:
        if self.tail.prev == self.head:
            return ""

        bucket = self.tail.prev
        for key in bucket.keys:
            return key

    def getMinKey(self) -> str:
        if self.head.next == self.tail:
            return ""

        bucket = self.head.next
        for key in bucket.keys:
            return key