#432

Hard

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

All O`one Data Structure

Implement a data structure that tracks string counts and retrieves max or min keys efficiently in constant time.

hash table linked list design doubly linked list

Problem Statement

Design a data structure that maintains counts of string keys and allows retrieval of the string with the highest or lowest count in constant time. Implement an AllOne class supporting the following operations: inc(key), dec(key), getMaxKey(), and getMinKey().

All operations must run in average O(1) time. Keys are lowercase letters with length 1 to 10, and all calls to dec are guaranteed to target existing keys. The structure must handle up to 50,000 calls efficiently while preserving correct frequency order.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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.

Solution Approach

Use a Hash Map for Key Access

Maintain a hash map that maps each string key to its frequency node in the doubly-linked list. This ensures O(1) access for incrementing or decrementing counts without scanning the list.

Doubly-Linked List for Frequency Order

Store frequency nodes in a doubly-linked list ordered by count. Each node holds a set of keys with that count. Insert and remove nodes carefully to maintain constant-time max and min retrievals, leveraging linked-list pointer manipulation.

Handle Increment and Decrement Carefully

When incrementing, move the key to the next frequency node or create one if it doesn’t exist. When decrementing, move the key to the previous node or remove it if its count reaches zero. This ensures the list always reflects accurate frequency order for getMaxKey and getMinKey.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(N)

All operations run in O(1) average time due to hash map lookups and direct pointer adjustments in the doubly-linked list. Space complexity is O(N), proportional to the number of unique keys and frequency nodes.

What Interviewers Usually Probe

Check if candidate correctly uses both hash map and doubly-linked list to maintain O(1) operations.
Observe if pointer updates are handled safely when incrementing or decrementing keys.
Look for understanding of how frequency nodes are linked and how keys move between them.

Common Pitfalls or Variants

Common pitfalls

Updating the doubly-linked list incorrectly when moving keys between frequency nodes, causing incorrect max/min keys.
Failing to remove empty frequency nodes after a key decrement, which can break O(1) assumptions.
Using linear scans instead of pointer manipulation, leading to performance degradation.

Follow-up variants

Implement a version that also supports returning all keys with a given count in O(1) time.
Modify the data structure to allow bulk increment or decrement of multiple keys efficiently.
Design a version that maintains counts for integer keys instead of strings while keeping O(1) operations.

FAQ

What is the main challenge in All O`one Data Structure?

The primary challenge is achieving O(1) increments, decrements, and max/min key retrievals by combining hash maps with a doubly-linked list and carefully updating pointers.

Can keys be removed from the structure?

Yes, when a key's count reaches zero after a decrement, it must be removed from its frequency node and the hash map while maintaining list integrity.

Why use a doubly-linked list instead of a simple array?

A doubly-linked list allows constant-time insertion, removal, and traversal between frequency nodes, which is essential for maintaining O(1) operations.

How does pointer manipulation prevent O(N) scans?

By directly linking frequency nodes and moving keys between them, you avoid scanning all keys to find max or min counts, preserving constant-time performance.

Is the hash map necessary for this problem?

Yes, the hash map provides O(1) access to a key's current frequency node, which is required for constant-time increment and decrement operations.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

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()

Continue Practicing

#460 lfu cache #146 lru cache #355 design twitter