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. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list:
Node1(val=1) -> Node2(val=2) -> Node3(val=3), where Node1.random = Node3, Node2.random = Node1, Node3.random = null.
After Step 2 (assigning random pointers), what is the value of copy_curr.random.val when copy_curr points to the copied node of Node2?

easy

A. None (null)

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace Step 1 (interleaving nodes)

   Original list: 1 -> 2 -> 3 becomes 1 -> 1' -> 2 -> 2' -> 3 -> 3'.

2. Step 2: Trace Step 2 (assign random pointers)

   Node2.random = Node1, so copied Node2 (2') random = Node1.next = 1'. Thus, copy_curr.random.val = 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   copy_curr.random points to copied Node1 with val=1 [OK]

Hint: Copied node's random points to original.random.next [OK]

Common Mistakes:

• Confusing original and copied nodes when assigning random pointers
• Off-by-one errors in stepping through interleaved list
• Assuming random pointer points to original node's val

2. The following code attempts to implement the optimal CustomStack with lazy increments. Identify the line containing the subtle bug that causes incorrect increment propagation.

class CustomStack:
    def __init__(self, maxSize: int):
        self.stack = []
        self.inc = [0] * maxSize
        self.maxSize = maxSize

    def push(self, x: int) -> None:
        self.stack.append(x)  # Line 8

    def pop(self) -> int:
        if not self.stack:
            return -1
        i = len(self.stack) - 1
        if i > 0:
            self.inc[i-1] += self.inc[i]
        res = self.stack.pop() + self.inc[i]
        self.inc[i] = 0
        return res

    def increment(self, k: int, val: int) -> None:
        limit = min(k, len(self.stack))
        if limit > 0:
            self.inc[limit-1] += val

medium

A. Line 8: push appends without checking maxSize

B. Line 13: returning -1 when stack is empty

C. Line 16: incrementing inc[i-1] by inc[i] during pop

D. Line 20: increment method updates inc array at limit-1

Solution

1. Step 1: Check push method

   Line 8 appends element without checking if stack size is less than maxSize, violating constraints and allowing overflow.

2. Step 2: Verify other lines

   Returning -1 on empty pop is correct; increment propagation and inc array updates are correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Push must check maxSize to avoid overflow [OK]

Hint: Push must respect maxSize limit to avoid overflow [OK]

Common Mistakes:

• Forgetting maxSize check in push
• Incorrect increment propagation on pop

3. What is the time complexity of performing addRange, removeRange, or queryRange operations in the optimal RangeModule implementation using a balanced BST with interval merging, assuming n intervals stored?

medium

A. O(n) per operation because intervals must be scanned to merge overlaps.

B. O(log n + k) where k is the number of overlapping intervals merged or removed.

C. O(log n) per operation due to balanced BST operations and interval merging.

D. O(1) amortized due to efficient data structure caching.

Solution

1. Step 1: Identify main operations

   Each operation uses binary search (O(log n)) to find affected intervals and merges or removes overlapping intervals.

2. Step 2: Consider merging/removal cost

   The number of intervals merged or removed, k, affects the cost linearly. So total cost is O(log n + k).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Logarithmic search plus linear merging -> O(log n + k) [OK]

Hint: Operations cost depends on search plus number of intervals merged [OK]

Common Mistakes:

• Assuming always O(log n) ignoring merging cost
• Assuming linear scan O(n) always

4. Consider the following buggy code snippet for merging two skylines. Which line contains the subtle bug that can cause incorrect skyline output?

medium

A. Line where merged.append([x, max_h]) is called unconditionally

B. Line where x, h1 = left[i] inside first if

C. Line where max_h is computed with max(h1, h2)

D. Line where i and j are incremented in the else block

Solution

1. Step 1: Identify difference from correct code

   The bug is that merged.append is called every iteration without checking if height changed, causing redundant points.

2. Step 2: Understand impact of redundant points

   Appending points even when max_h equals previous height leads to unnecessary key points, failing correctness checks.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct code appends only if height changes [OK]

Hint: Appending only on height change avoids redundant points [OK]

Common Mistakes:

• Appending every iteration regardless of height change
• Incorrect pointer increments

5. Suppose you want to extend the LRU Cache to support a "reuse" operation that marks an existing key as recently used without retrieving its value. Which modification to the optimal LRU Cache implementation is correct to support this efficiently?

hard

A. On reuse, remove the key from the cache and re-insert it with the same value.

B. Do nothing; reuse is equivalent to get, so no code change is needed.

C. Use a queue instead of a doubly linked list to track usage order for easier reuse.

D. Add a new method that calls _remove and _add on the node corresponding to the key.

Solution

1. Step 1: Understand reuse operation

   Reuse means marking a key as recently used without returning its value, so usage order must be updated.

2. Step 2: Efficiently update usage order

   Calling _remove and _add on the node moves it to the front in O(1) time, correctly updating usage.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Reuse requires usage update without value retrieval, done by repositioning node [OK]

Hint: Reuse updates usage order like get but without returning value [OK]

Common Mistakes:

• Re-inserting wastes time
• Queue can't reorder efficiently
• Assuming reuse needs no code change