All O(1) Data Structure (Max/Min Count)

▶

Steps

setup

Initialize the Data Structure

Create head and tail sentinel buckets with counts -inf and +inf, linked to each other. Initialize empty maps for keys and counts.

💡 Sentinel buckets simplify edge cases by always existing at the ends of the list.

Line:

self.head = Bucket(float('-inf'))
self.tail = Bucket(float('inf'))
self.head.next = self.tail
self.tail.prev = self.head

💡 The doubly linked list is ready to hold count buckets between head and tail.

insert

Increment 'hello' First Time - Create Bucket 1

Since 'hello' is new, check if bucket with count 1 exists. It does not, so create bucket 1 and insert it after head.

💡 Buckets are created lazily only when needed to keep the list minimal.

Line:

if 1 not in self.count_to_bucket:
    new_bucket = Bucket(1)
    self._insert_bucket_after(new_bucket, self.head)

💡 New keys start at count 1, so bucket 1 must exist to hold them.

insert

Add 'hello' to Bucket 1

Add 'hello' to the keys set of bucket 1 and map 'hello' to bucket 1.

💡 Tracking which bucket a key belongs to enables O(1) updates later.

Line:

self.count_to_bucket[1].keys.add(key)
self.key_to_bucket[key] = self.count_to_bucket[1]

💡 'hello' now has count 1 and is stored in bucket 1.

insert

Increment 'hello' Second Time - Prepare to Move to Bucket 2

'hello' is currently in bucket 1. Calculate next count 2 and check if bucket 2 exists.

💡 Incrementing a key moves it to the next higher count bucket.

Line:

curr_bucket = self.key_to_bucket[key]
curr_count = curr_bucket.count
next_count = curr_count + 1
if next_count not in self.count_to_bucket:

💡 Buckets are created only when needed for the new count.

insert

Create Bucket 2 After Bucket 1

Insert new bucket with count 2 after bucket 1 to hold keys with count 2.

💡 Buckets are kept in ascending order by count in the linked list.

Line:

new_bucket = Bucket(next_count)
self._insert_bucket_after(new_bucket, curr_bucket)

💡 The linked list structure supports efficient insertion of new buckets.

insert

Move 'hello' from Bucket 1 to Bucket 2

Remove 'hello' from bucket 1's keys and add it to bucket 2's keys. Update key_to_bucket mapping.

💡 Moving keys between buckets updates their counts efficiently.

Line:

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

💡 'hello' now correctly reflects count 2 in the data structure.

delete

Remove Bucket 1 as it Became Empty

Bucket 1 has no keys left after moving 'hello', so remove it from the linked list and count_to_bucket map.

💡 Removing empty buckets keeps the list minimal and efficient.

Line:

if len(curr_bucket.keys) == 0:
    self._remove_bucket(curr_bucket)

💡 The data structure dynamically shrinks to only buckets with keys.

traverse

getMaxKey() Returns 'hello'

Max key is from the bucket before tail, which is bucket 2. Return any key from bucket 2's keys, here 'hello'.

💡 Max key retrieval is O(1) by accessing tail.prev bucket.

Line:

max_bucket = self.tail.prev
return next(iter(max_bucket.keys)) if max_bucket != self.head else ""

💡 Max key is the key with highest count in the last bucket before tail.

traverse

getMinKey() Returns 'hello'

Min key is from the bucket after head, which is bucket 2. Return any key from bucket 2's keys, here 'hello'.

💡 Min key retrieval is O(1) by accessing head.next bucket.

Line:

min_bucket = self.head.next
return next(iter(min_bucket.keys)) if min_bucket != self.tail else ""

💡 Min key is the key with lowest count in the first bucket after head.

insert

Decrement 'hello' - Move to Bucket 1

'hello' is in bucket 2 with count 2. Calculate previous count 1. Bucket 1 does not exist, so create it after head.

💡 Decrementing moves keys to lower count buckets, creating them if needed.

Line:

curr_bucket = self.key_to_bucket[key]
curr_count = curr_bucket.count
prev_count = curr_count - 1
if prev_count not in self.count_to_bucket:
    new_bucket = Bucket(prev_count)
    self._insert_bucket_after(new_bucket, self.head)

💡 Buckets are created on demand for decrements as well.

insert

Move 'hello' from Bucket 2 to Bucket 1

Remove 'hello' from bucket 2's keys and add it to bucket 1's keys. Update key_to_bucket mapping.

💡 Keys move down buckets on decrement to reflect new counts.

Line:

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

💡 'hello' count is now 1 and tracked in bucket 1.

delete

Remove Bucket 2 as it Became Empty

Bucket 2 has no keys left after moving 'hello', so remove it from the linked list and count_to_bucket map.

💡 Empty buckets are removed immediately to keep the list minimal.

Line:

if len(curr_bucket.keys) == 0:
    self._remove_bucket(curr_bucket)

💡 The list only contains buckets with keys after operations.

traverse

getMaxKey() Returns 'hello' After Decrement

Max key is from bucket before tail, now bucket 1. Return 'hello' from bucket 1's keys.

💡 Max key updates dynamically as counts change.

Line:

max_bucket = self.tail.prev
return next(iter(max_bucket.keys)) if max_bucket != self.head else ""

💡 Max key retrieval always reflects current highest count.

traverse

getMinKey() Returns 'hello' After Decrement

Min key is from bucket after head, bucket 1. Return 'hello' from bucket 1's keys.

💡 Min key retrieval remains O(1) and consistent.

Line:

min_bucket = self.head.next
return next(iter(min_bucket.keys)) if min_bucket != self.tail else ""

💡 Min key retrieval reflects current lowest count.

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

class AllOne:
    def __init__(self):
        self.head = Bucket(float('-inf'))  # STEP 1
        self.tail = Bucket(float('inf'))   # STEP 1
        self.head.next = self.tail         # STEP 1
        self.tail.prev = self.head         # STEP 1
        self.key_to_bucket = {}            # STEP 1
        self.count_to_bucket = {}          # STEP 1

    def _insert_bucket_after(self, new_bucket, prev_bucket):
        new_bucket.prev = prev_bucket       # STEP 5
        new_bucket.next = prev_bucket.next # STEP 5
        prev_bucket.next.prev = new_bucket # STEP 5
        prev_bucket.next = new_bucket      # STEP 5
        self.count_to_bucket[new_bucket.count] = new_bucket  # STEP 5

    def _remove_bucket(self, bucket):
        bucket.prev.next = bucket.next      # STEP 7,12
        bucket.next.prev = bucket.prev      # STEP 7,12
        del self.count_to_bucket[bucket.count]  # STEP 7,12

    def inc(self, key: str) -> None:
        if key not in self.key_to_bucket:  # STEP 2
            if 1 not in self.count_to_bucket:  # STEP 2
                new_bucket = Bucket(1)           # STEP 2
                self._insert_bucket_after(new_bucket, self.head)  # STEP 2
            self.count_to_bucket[1].keys.add(key)  # STEP 3
            self.key_to_bucket[key] = self.count_to_bucket[1]  # STEP 3
        else:
            curr_bucket = self.key_to_bucket[key]  # STEP 4
            curr_count = curr_bucket.count          # STEP 4
            next_count = curr_count + 1             # STEP 4
            if next_count not in self.count_to_bucket:  # STEP 4
                new_bucket = Bucket(next_count)          # STEP 5
                self._insert_bucket_after(new_bucket, curr_bucket)  # STEP 5
            curr_bucket.keys.remove(key)               # STEP 6
            self.count_to_bucket[next_count].keys.add(key)  # STEP 6
            self.key_to_bucket[key] = self.count_to_bucket[next_count]  # STEP 6
            if len(curr_bucket.keys) == 0:              # STEP 7
                self._remove_bucket(curr_bucket)          # STEP 7

    def dec(self, key: str) -> None:
        if key not in self.key_to_bucket:  # Not shown in trace
            return
        curr_bucket = self.key_to_bucket[key]  # STEP 10
        curr_count = curr_bucket.count          # STEP 10
        prev_count = curr_count - 1             # STEP 10
        if prev_count == 0:                      # Not shown in trace
            del self.key_to_bucket[key]          # Not shown
            curr_bucket.keys.remove(key)         # Not shown
            if len(curr_bucket.keys) == 0:       # Not shown
                self._remove_bucket(curr_bucket)  # Not shown
            return
        if prev_count not in self.count_to_bucket:  # STEP 10
            new_bucket = Bucket(prev_count)           # STEP 10
            self._insert_bucket_after(new_bucket, self.head)  # STEP 10
        curr_bucket.keys.remove(key)               # STEP 11
        self.count_to_bucket[prev_count].keys.add(key)  # STEP 11
        self.key_to_bucket[key] = self.count_to_bucket[prev_count]  # STEP 11
        if len(curr_bucket.keys) == 0:              # STEP 12
            self._remove_bucket(curr_bucket)          # STEP 12

    def getMaxKey(self) -> str:
        max_bucket = self.tail.prev  # STEP 8,13
        if max_bucket == self.head:
            return ""
        return next(iter(max_bucket.keys))  # STEP 8,13

    def getMinKey(self) -> str:
        min_bucket = self.head.next  # STEP 9,14
        if min_bucket == self.tail:
            return ""
        return next(iter(min_bucket.keys))  # STEP 9,14

📊

All O(1) Data Structure (Max/Min Count) - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the data structure maintains O(1) operations by dynamically creating and removing buckets and updating pointers, which is hard to grasp from code alone.

setup

-inf

→

+inf

insert

-inf

→

1

→

+inf

insert

-inf

→

1

→

+inf

compare

-inf

→

1

→

+inf

insert

-inf

→

1

→

2

→

+inf

connect

-inf

→

1

→

2

→

+inf

detach

-inf

→

2

→

+inf

traverse

-inf

→

2

→

+inf

Result: "hello"

traverse

-inf

→

2

→

+inf

Result: "hello"

insert

-inf

→

1

→

2

→

+inf

connect

-inf

→

1

→

2

→

+inf

detach

-inf

→

1

→

+inf

traverse

-inf

→

1

→

+inf

Result: "hello"

traverse

-inf

→

1

→

+inf

Result: "hello"

Key Takeaways

✓ The doubly linked list of buckets maintains counts in ascending order, enabling O(1) max and min key retrieval.

This structure is hard to visualize from code alone because it involves dynamic pointer updates and bucket creation/removal.

✓ Keys move between buckets on increments and decrements, and buckets are created or removed lazily to keep the list minimal.

Watching keys move step-by-step clarifies how the data structure avoids scanning all keys.

✓ Sentinel head and tail buckets simplify edge cases by always existing at the ends of the list.

This design detail prevents null pointer errors and makes insertion/removal logic uniform.

Practice

1. You need to design a system that tracks passengers checking in and out of stations, and efficiently calculates average travel times between stations. Which approach best balances time and space efficiency for frequent queries?

easy

A. Use hash maps to store running totals of travel times and counts per route.

B. Store all trips explicitly and scan them to compute averages on demand.

C. Use dynamic programming to precompute all possible route averages.

D. Use a priority queue to keep track of the shortest travel times per route.

Solution

1. Step 1: Understand the problem requirements

   The system must support frequent check-ins, check-outs, and quick average time queries between stations.

2. Step 2: Evaluate approaches

   Storing all trips (B) leads to slow queries. Dynamic programming (C) is not applicable as routes are dynamic and not fixed. Priority queues (D) do not help compute averages efficiently. Hash maps with running totals (A) allow O(1) updates and queries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash maps maintain running sums and counts for O(1) average time queries [OK]

Hint: Running totals enable O(1) average queries [OK]

Common Mistakes:

• Thinking storing all trips is efficient for queries

2. You need to design a data structure that supports adding intervals, removing intervals, and querying whether a given range is fully covered by the added intervals. Which approach guarantees efficient updates and queries with logarithmic time complexity per operation?

easy

A. Use a balanced binary search tree (e.g., TreeMap) to store and merge intervals, enabling logarithmic time operations.

B. Use a brute force list of intervals and scan all intervals for each operation.

C. Use dynamic programming to precompute coverage for all possible ranges.

D. Use a greedy algorithm that always merges intervals only when queried.

Solution

1. Step 1: Understand the problem requirements

   The data structure must support add, remove, and query operations on intervals efficiently.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n) per operation, which is inefficient. DP is not suitable for dynamic interval updates. Greedy merging only on query delays merging and leads to inefficient queries. Balanced BST with interval merging maintains sorted intervals and merges overlapping ones, supporting O(log n) operations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Balanced BST with merging -> O(log n) per operation [OK]

Hint: Balanced BST with merging enables efficient interval operations [OK]

Common Mistakes:

• Thinking DP or greedy solves dynamic interval updates efficiently

3. Examine the following buggy code snippet for the MedianFinder class. Which line contains the subtle bug that can cause incorrect median calculation?

medium

A. Condition 'if self.low_size > self.high_size:' for balancing heaps

B. Line that pushes to high heap and increments high_size

C. Line that pushes to low heap and increments low_size

D. Condition 'elif self.high_size > self.low_size + 1:' for balancing heaps

Solution

1. Step 1: Understand balancing condition

   The heaps must be balanced so that their sizes differ by at most 1.

2. Step 2: Identify incorrect condition

   The condition 'if self.low_size > self.high_size:' moves an element from low to high even when sizes differ by only 1, causing imbalance.

3. Step 3: Correct condition

   The condition should be 'if self.low_size > self.high_size + 1:' to ensure size difference is more than 1 before balancing.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Balancing condition must check if low_size > high_size + 1 [OK]

Hint: Balance heaps only if size difference > 1 [OK]

Common Mistakes:

• Balancing heaps too aggressively
• Incorrect size difference checks

4. What is the amortized time complexity of the put operation in the optimal LFU Cache implementation using a frequency map of doubly linked lists and hash maps?

medium

A. O(n), where n is the number of keys in the cache

B. O(f), where f is the number of distinct frequencies

C. O(log n), due to maintaining frequency order

D. O(1), amortized constant time

Solution

1. Step 1: Analyze data structures used

   Hash maps provide O(1) access to keys and frequencies. Doubly linked lists allow O(1) insertion and deletion of keys within frequency groups.

2. Step 2: Consider operations in put

   Eviction and frequency updates involve O(1) operations on hash maps and linked lists. Frequency increments and min frequency updates are also O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal LFU cache achieves O(1) amortized put [OK]

Hint: Hash maps + linked lists enable O(1) put [OK]

Common Mistakes:

• Assuming O(n) due to scanning keys
• Thinking frequency updates cost O(log n)
• Confusing distinct frequencies with n

5. What is the time complexity of the get operation in the optimal SnapshotArray implementation that uses a hash map per index with binary search, assuming m snapshots and k set operations?

medium

A. O(1) because values are stored directly per index and snap_id

B. O(k) because get must scan all set operations for the index

C. O(m) because linear search is needed over all snapshots

D. O(log m) because binary search is performed on at most m entries per index

Solution

1. Step 1: Identify data structure for get

   Each index stores a sorted list of (snap_id, value) pairs, with length up to number of set operations k but bounded by m snapshots.

2. Step 2: Analyze get operation

   Get uses binary search on this list to find the value for the requested snap_id, which takes O(log m) time since at most one entry per snapshot per index.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search on sorted snapshot list yields O(log m) [OK]

Hint: Binary search on snapshots per index yields O(log m) get time [OK]

Common Mistakes:

• Assuming get is O(1) due to direct indexing
• Confusing linear search with binary search