Range Module (Add/Remove/Query Ranges)

▶

Steps

setup

Initialize empty RangeModule

Create an empty RangeModule with no intervals and an empty starts list.

💡 Starting with an empty structure is essential to see how intervals are added and managed.

Line:

self.intervals = dict()
self.starts = []

💡 Intervals and starts are empty, so no coverage exists yet.

fill_row

Add range [10, 20) - Find insertion points

Find insertion indices i and j for left=10 and right=20 using bisect on starts list.

💡 Finding where to insert or merge intervals is the first step in addRange.

Line:

i = bisect_left(self.starts, left)
j = bisect_right(self.starts, right)

💡 No existing intervals overlap, so insertion will be at position 0.

fill_cells

Add range [10, 20) - No overlap adjustment

Since i=0, no previous interval overlaps left=10; right remains 20.

💡 Check if previous interval overlaps to adjust left boundary.

Line:

if i != 0 and self.intervals[self.starts[i-1]] >= left:
    i -= 1
    left = min(left, self.starts[i])

💡 No previous interval to merge with, so left boundary stays 10.

fill_cells

Add range [10, 20) - Adjust right boundary

Since j=0, no intervals end after right=20, so right remains 20.

💡 Adjust right boundary if overlapping intervals extend beyond right.

Line:

if j != 0:
    right = max(right, self.intervals[self.starts[j-1]])

💡 Right boundary remains unchanged as no overlapping intervals on right.

insert

Add range [10, 20) - Remove overlapping intervals and insert merged

Remove intervals in starts[i:j] (empty here), insert new interval [10,20) at position i=0.

💡 This step merges overlapping intervals and inserts the new merged interval.

Line:

for k in self.starts[i:j]:
    del self.intervals[k]
self.starts[i:j] = [left]
self.intervals[left] = right

💡 The intervals list now contains one interval [10,20).

fill_row

Remove range [14, 16) - Find removal indices

Find indices i and j for left=14 and right=16 in starts list [10].

💡 Locate intervals overlapping the removal range.

Line:

i = bisect_left(self.starts, left)
j = bisect_right(self.starts, right)

💡 Removal range overlaps with interval starting at 10.

prune

Remove range [14, 16) - Check left overlap for split

Check if interval before i overlaps left=14 to split it.

💡 Splitting intervals is necessary to remove a middle portion.

Line:

if i != 0 and self.intervals[self.starts[i-1]] > left:
    start = self.starts[i-1]
    end = self.intervals[start]
    if start < left:
        newIntervals.append((start, left))
    i -= 1

💡 Left part [10,14) remains after removal starts at 14.

prune

Remove range [14, 16) - Check right overlap for split

Check if interval before j overlaps right=16 to split it.

💡 Right split preserves interval after removal end.

Line:

if j != 0 and self.intervals[self.starts[j-1]] > right:
    start = right
    end = self.intervals[self.starts[j-1]]
    newIntervals.append((start, end))

💡 Right part [16,20) remains after removal ends at 16.

delete

Remove range [14, 16) - Remove overlapping intervals

Delete intervals in starts[i:j] which is [10], removing [10,20).

💡 Removing intervals overlapping removal range is necessary before reinserting splits.

Line:

for k in self.starts[i:j]:
    del self.intervals[k]
self.starts[i:j] = []

💡 The original interval is removed to be replaced by split intervals.

insert

Remove range [14, 16) - Insert split intervals

Insert new intervals [10,14) and [16,20) into starts and intervals.

💡 Reinserting split intervals preserves coverage outside removal range.

Line:

for start, end in newIntervals:
    self.starts.insert(i, start)
    self.intervals[start] = end
    i += 1

💡 Intervals now represent coverage excluding [14,16).

compare

Query range [10, 14) - Find floor interval

Find index i for left=10 using bisect_right and check interval coverage.

💡 Query checks if an interval fully covers the query range.

Line:

i = bisect_right(self.starts, left) - 1

💡 Floor interval found starting at 10.

compare

Query range [10, 14) - Check coverage

Check if interval [10,14) covers right=14 by comparing interval end.

💡 Coverage means interval end >= query right.

Line:

return self.intervals[self.starts[i]] >= right

💡 Query range is fully covered by interval [10,14).

compare

Query range [13, 15) - Find floor interval

Find index i for left=13 using bisect_right and check interval coverage.

💡 Find candidate interval that might cover query range.

Line:

i = bisect_right(self.starts, left) - 1

💡 Floor interval found starting at 10.

compare

Query range [13, 15) - Check coverage

Check if interval [10,14) covers right=15 by comparing interval end.

💡 Coverage means interval end >= query right.

Line:

return self.intervals[self.starts[i]] >= right

💡 Query range is not fully covered because [14,15) is missing.

compare

Query range [16, 17) - Find floor interval

Find index i for left=16 using bisect_right and check interval coverage.

💡 Find candidate interval that might cover query range.

Line:

i = bisect_right(self.starts, left) - 1

💡 Floor interval found starting at 16.

compare

Query range [16, 17) - Check coverage

Check if interval [16,20) covers right=17 by comparing interval end.

💡 Coverage means interval end >= query right.

Line:

return self.intervals[self.starts[i]] >= right

💡 Query range is fully covered by interval [16,20).

from bisect import bisect_left, bisect_right

class RangeModule:
    def __init__(self):
        self.intervals = dict()  # STEP 1
        self.starts = []        # STEP 1

    def addRange(self, left: int, right: int) -> None:
        i = bisect_left(self.starts, left)  # STEP 2
        j = bisect_right(self.starts, right)  # STEP 2

        if i != 0 and self.intervals[self.starts[i-1]] >= left:  # STEP 3
            i -= 1
            left = min(left, self.starts[i])
        if j != 0:  # STEP 4
            right = max(right, self.intervals[self.starts[j-1]])

        for k in self.starts[i:j]:  # STEP 5
            del self.intervals[k]
        self.starts[i:j] = [left]
        self.intervals[left] = right

    def queryRange(self, left: int, right: int) -> bool:
        i = bisect_right(self.starts, left) - 1  # STEP 11,13,15
        if i < 0:
            return False
        return self.intervals[self.starts[i]] >= right  # STEP 12,14,16

    def removeRange(self, left: int, right: int) -> None:
        i = bisect_left(self.starts, left)  # STEP 6
        j = bisect_right(self.starts, right)  # STEP 6

        newIntervals = []
        if i != 0 and self.intervals[self.starts[i-1]] > left:  # STEP 7
            start = self.starts[i-1]
            end = self.intervals[start]
            if start < left:
                newIntervals.append((start, left))
            i -= 1
        if j != 0 and self.intervals[self.starts[j-1]] > right:  # STEP 8
            start = right
            end = self.intervals[self.starts[j-1]]
            newIntervals.append((start, end))

        for k in self.starts[i:j]:  # STEP 9
            del self.intervals[k]
        self.starts[i:j] = []

        for start, end in newIntervals:  # STEP 10
            self.starts.insert(i, start)
            self.intervals[start] = end
            i += 1

📊

Range Module (Add/Remove/Query Ranges) - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and interval update helps you understand how overlapping intervals are merged or split, which is hard to grasp from code alone.

setup

advance

compare

compare

insert

10

advance

10

prune

10

prune

10

detach

insert

10

→

16

compare

10

→

16

compare

10

→

16

Result: true

compare

10

→

16

compare

10

→

16

Result: false

compare

10

→

16

compare

10

→

16

Result: true

Key Takeaways

✓ Intervals are stored as a sorted list of start points with corresponding ends, enabling efficient merging and splitting.

This structure is hard to visualize from code alone but becomes clear when watching intervals merge and split step-by-step.

✓ Adding a range merges all overlapping intervals into one, simplifying coverage representation.

Seeing how bisect finds indices and how intervals are removed and replaced clarifies the merging process.

✓ Removing a range can split existing intervals into two, preserving coverage outside the removed range.

The split and reinsert steps are subtle in code but become obvious when watching the intervals being pruned and reinserted.

Practice

1. You need to design a system that supports posting tweets and retrieving the 10 most recent tweets from a user's timeline, including tweets from users they follow. Which approach best balances efficient posting and retrieving the top recent tweets in real-time?

easy

A. Store all tweets in a global list and scan it entirely each time to find the top 10 recent tweets.

B. Maintain a linked list of tweets per user, a hashmap for followees, and use a max heap to merge the most recent tweets from followees efficiently.

C. Use a dynamic programming approach to precompute the top tweets for each user after every post.

D. Use a simple array per user and sort all tweets from followees every time the feed is requested.

Solution

1. Step 1: Understand the problem constraints

   The system must support fast posting and retrieving the top 10 recent tweets from a user's followees including themselves.

2. Step 2: Evaluate approaches

   Brute force scanning or sorting all tweets each time is inefficient. DP is not applicable here. Using linked lists per user and a max heap for merging recent tweets achieves O(1) posting and O(k log F) retrieval, where F is followees count.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linked list + hashmap + heap is the optimal pattern for this problem [OK]

Hint: Linked list + heap merges recent tweets efficiently [OK]

Common Mistakes:

• Thinking sorting all tweets each time is efficient
• Trying DP for a streaming feed problem

2. Consider the following Python code snippet implementing the optimized Insert Delete GetRandom O(1) with duplicates data structure. After executing the sequence of operations below, what is the return value of the final getRandom() call? Operations: insert(1), insert(1), insert(2), remove(1), getRandom()

import random

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = null
        self.next = null

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(null)
        self.tail = Node(null)
        self.head.next = self.tail
        self.tail.prev = self.head

    def append(self, val):
        node = Node(val)
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node
        return node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def is_empty(self):
        return self.head.next == self.tail

class RandomizedCollection:
    def __init__(self):
        self.nums = []
        self.idx_map = {}

    def insert(self, val: int) -> bool:
        self.nums.append(val)
        if val not in self.idx_map:
            self.idx_map[val] = set()
        self.idx_map[val].add(len(self.nums) - 1)
        return len(self.idx_map[val]) == 1

    def remove(self, val: int) -> bool:
        if val not in self.idx_map or not self.idx_map[val]:
            return false
        remove_idx = self.idx_map[val].pop()
        last_val = self.nums[-1]
        self.nums[remove_idx] = last_val
        self.idx_map[last_val].add(remove_idx)
        self.idx_map[last_val].discard(len(self.nums) - 1)
        self.nums.pop()
        if not self.idx_map[val]:
            del self.idx_map[val]
        return true

    def getRandom(self) -> int:
        return random.choice(self.nums)

rc = RandomizedCollection()
rc.insert(1)
rc.insert(1)
rc.insert(2)
rc.remove(1)
result = rc.getRandom()

easy

A. Either 1 or 2 but 1 is twice as likely

B. 2

C. Either 1 or 2 with equal probability

D. 1

Solution

1. Step 1: Trace insertions

   After insert(1), nums=[1], idx_map={1:{0}}; after insert(1), nums=[1,1], idx_map={1:{0,1}}; after insert(2), nums=[1,1,2], idx_map={1:{0,1},2:{2}}.

2. Step 2: Trace removal of one 1

   Remove one 1: remove_idx=1 (pop from idx_map[1]). Swap last element 2 into index 1: nums=[1,2], idx_map={1:{0},2:{1}}. So now nums has one 1 and one 2.

3. Step 3: Analyze getRandom probabilities

   nums=[1,2], so getRandom picks index 0 or 1 equally. But initially there were two 1's, after removal only one remains. So 1 and 2 are equally likely, but since the original had duplicates, the final collection has one 1 and one 2.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   After removal, one 1 and one 2 remain, so 1 is as likely as 2 [OK]

Hint: Track indices and swaps carefully to find final array state [OK]

Common Mistakes:

• Forgetting to update idx_map after swap
• Assuming getRandom returns only 2
• Ignoring that one 1 remains after removal

3. You need to design a cache that evicts the least frequently used item when full, and among items with the same frequency, evicts the least recently used one. Which approach guarantees O(1) average time complexity for both get and put operations?

easy

A. Using a simple hash map with frequency counts and sorting keys on each eviction

B. Maintaining a frequency map of doubly linked lists to track keys by frequency and recency

C. Using a min-heap keyed by frequency and timestamp to evict the least frequently used item

D. Using a single doubly linked list ordered by frequency and recency

Solution

1. Step 1: Understand the eviction criteria

   The cache must evict the least frequently used key, and if multiple keys share the same frequency, evict the least recently used among them.

2. Step 2: Identify data structures supporting O(1) operations

   A frequency map with doubly linked lists allows grouping keys by frequency and maintaining recency order within each frequency group, enabling O(1) updates and eviction.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Frequency map + doubly linked lists is the classic LFU O(1) approach [OK]

Hint: Frequency map + doubly linked lists enable O(1) LFU cache [OK]

Common Mistakes:

• Using sorting on eviction is too slow
• Min-heap adds O(log n) overhead
• Single list can't maintain frequency and recency efficiently

4. Given the following code snippet for SnapshotArray, what is the output of snapshotArr.get(0, 0) after executing all lines shown?

snapshotArr = SnapshotArray(3)
snapshotArr.set(0, 5)
snap_id = snapshotArr.snap()
snapshotArr.set(0, 6)
print(snapshotArr.get(0, 0))

easy

A. 5

B. 6

C. 0

D. Error due to invalid snap_id

Solution

1. Step 1: Trace set and snap operations

   Initially, data[0] = [(-1,0)]. After set(0,5), data[0] = [(-1,0),(0,5)] because snap_id=0. Then snap() increments snap_id to 1 and returns 0. Then set(0,6) appends (1,6) to data[0].

2. Step 2: Trace get(0,0)

   For snap_id=0, bisect_right finds insertion point for (0,inf) in data[0] = [(-1,0),(0,5),(1,6)]. It returns index 2, so i=1. data[0][1] = (0,5), so get returns 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Value at snap 0 is 5, not the later set 6 [OK]

Hint: Get returns value at or before snap_id using binary search [OK]

Common Mistakes:

• Returning latest value ignoring snap_id
• Off-by-one in bisect index

5. Suppose the AllOne data structure is extended to allow keys to be reused after removal (i.e., keys can be reinserted after their count reaches zero). Which modification is necessary to maintain O(1) operations and correctness?

hard

A. Do nothing special; existing code handles reuse correctly

B. Maintain a separate reuse queue to track keys that can be reinserted

C. Reset key's count to zero and keep it in the data structure to track reuse

D. Ensure keys are fully removed from all buckets and mappings upon count zero, then treat reuse as new insertion

Solution

1. Step 1: Understand reuse implications

   Keys removed at count zero must be fully deleted to avoid stale references.

2. Step 2: Ensure reuse is treated as new insertion

   On reuse, key is inserted fresh with count 1, requiring clean removal previously.

3. Step 3: Confirm O(1) operations

   Full removal and fresh insertion maintain O(1) updates and correctness.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Proper removal prevents duplicates and stale buckets [OK]

Hint: Full removal before reuse ensures correctness and O(1) ops [OK]

Common Mistakes:

• Keeping keys with zero count in data structure causes bugs